Vaš brskalnik ne omogoča JavaScript!
JavaScript je nujen za pravilno delovanje teh spletnih strani. Omogočite JavaScript ali pa uporabite sodobnejši brskalnik.
Nacionalni portal odprte znanosti
Odprta znanost
DiKUL
slv
|
eng
Iskanje
Brskanje
Novo v RUL
Kaj je RUL
V številkah
Pomoč
Prijava
Packings in bipartite prisms and hypercubes
ID
Brešar, Boštjan
(
Avtor
),
ID
Klavžar, Sandi
(
Avtor
),
ID
Rall, Douglas F.
(
Avtor
)
PDF - Predstavitvena datoteka,
prenos
(231,57 KB)
MD5: BC4297894DBBF84BEE1923433A1D0D53
URL - Izvorni URL, za dostop obiščite
https://www.sciencedirect.com/science/article/pii/S0012365X24000062
Galerija slik
Izvleček
The $2$-packing number $\rho_2(G)$ of a graph $G$ is the cardinality of a largest $2$-packing of $G$ and the open packing number $\rho^{\rm o}(G)$ is the cardinality of a largest open packing of $G$, where an open packing (resp. $2$-packing) is a set of vertices in $G$ no two (closed) neighborhoods of which intersect. It is proved that if $G$ is bipartite, then $\rho^{\rm o}(G\Box K_2) = 2\rho_2(G)$. For hypercubes, the lower bounds $\rho_2(Q_n) \ge 2^{n - \lfloor \log n\rfloor -1}$ and $\rho^{\rm o}(Q_n) \ge 2^{n - \lfloor \log (n-1)\rfloor -1}$ are established. These findings are applied to injective colorings of hypercubes. In particular, it is demonstrated that $Q_9$ is the smallest hypercube which is not perfect injectively colorable. It is also proved that $\gamma_t(Q_{2^k}\times H) = 2^{2^k-k}\gamma_t(H)$, where $H$ is an arbitrary graph with no isolated vertices.
Jezik:
Angleški jezik
Ključne besede:
2-packing number
,
open packing number
,
bipartite prism
,
hypercube
,
injective coloring
,
total domination number
Vrsta gradiva:
Članek v reviji
Tipologija:
1.01 - Izvirni znanstveni članek
Organizacija:
FMF - Fakulteta za matematiko in fiziko
Status publikacije:
Objavljeno
Različica publikacije:
Objavljena publikacija
Leto izida:
2024
Št. strani:
6 str.
Številčenje:
Vol. 347, iss. 4, art. 113875
PID:
20.500.12556/RUL-154513
UDK:
519.17
ISSN pri članku:
0012-365X
DOI:
10.1016/j.disc.2024.113875
COBISS.SI-ID:
181387523
Datum objave v RUL:
19.02.2024
Število ogledov:
583
Število prenosov:
32
Metapodatki:
Citiraj gradivo
Navadno besedilo
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Kopiraj citat
Objavi na:
Gradivo je del revije
Naslov:
Discrete mathematics
Skrajšan naslov:
Discrete math.
Založnik:
Elsevier
ISSN:
0012-365X
COBISS.SI-ID:
1118479
Licence
Licenca:
CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
Povezava:
http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:
Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.
Sekundarni jezik
Jezik:
Slovenski jezik
Ključne besede:
2-pakirno število
,
odprto pakirno število
,
dvodelna prizma
,
hiperkocke
,
injektivno barvanje
,
celotno dominacijsko število
Projekti
Financer:
ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:
BI-US/22-24-038
Naslov:
Domination in graphs, digraphs and their products
Financer:
ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:
P1-0297
Naslov:
Teorija grafov
Financer:
ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:
J1-2452
Naslov:
Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov
Financer:
ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:
N1-0285
Naslov:
Metrični problemi v grafih in hipergrafih
Financer:
ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:
J1-3002
Naslov:
Prirejanja in barvanja povezav v kubičnih grafih
Podobna dela
Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:
Nazaj