Packings in bipartite prisms and hypercubes

Brešar, Boštjan; Klavžar, Sandi; Rall, Douglas F.

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Packings in bipartite prisms and hypercubes
Avtorji:	ID Brešar, Boštjan (Avtor) ID Klavžar, Sandi (Avtor) ID Rall, Douglas F. (Avtor)
Datoteke:	https://www.sciencedirect.com/science/article/pii/S0012365X24000062
Jezik:	Angleški jezik
Vrsta gradiva:	Članek v reviji
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	FNM - Fakulteta za naravoslovje in matematiko
Opis:	▫$2$▫-pakirno število ▫$\rho_2(G)$▫ grafa ▫$G$▫ je kardinalnost največjega ▫$2$▫-pakiranja grafa ▫$G$▫, odprto pakirno število ▫$\rho^{\rm o}(G)$▫ pa kardinalnost največjega odprtega pakiranja grafa ▫$G$▫, kjer je odprto pakiranje (oz. ▫$2$▫ pakiranje) množica vozlišč grafa ▫$G$▫, katerih dve (zaprti) soseščini se ne sekata. Dokazano je, da če je ▫$G$▫ dvodelen, potem je ▫$\rho^{\rm o}(G\Box K_2) = 2\rho_2(G)$▫. Za hiperkocke sta določeni spodnji meji ▫$\rho_2(Q_n) \ge 2^{n - \lfloor \log n\rfloor -1}$▫ in ▫$\rho^{\rm o}(Q_n) \ge 2^{n - \lfloor \log (n-1)\rfloor -1}$▫. Te ugotovitve so uporabljene za injektivna barvanja hiperkock. Dokazano je, da je ▫$Q_9$▫ najmanjša hiperkocka, ki ni popolno injektivno obarvljiva. Dokazano je tudi, da je ▫$\gamma_t(Q_{2^k}\times H) = 2^{2^k-k}\gamma_t(H)$▫, kjer je ▫$H$▫ poljuben graf brez izoliranih vozlišč.
Ključne besede:	2-pakirno število, odprto pakirno število, dvodelna prizma, hiperkocke, injektivno barvanje, celotno dominacijsko število, 2-packing number, open packing number, bipartite prism, hypercube, injective coloring, total domination number
Leto izida:	2024
Št. strani:	6 str.
Številčenje:	ǂVol. ǂ347, ǂiss. ǂ4, [article no.] 113875
PID:	20.500.12556/DKUM-87124
UDK:	519.17
COBISS.SI-ID:	181387523
DOI:	10.1016/j.disc.2024.113875
ISSN pri članku:	0012-365X
Datum objave v DKUM:	28.02.2024
Število ogledov:	470
Število prenosov:	13
Metapodatki:
Področja:	Ostalo
:	Kopiraj citat

Skupna ocena:	(0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:	Discrete mathematics
Skrajšan naslov:	Discrete math.
Založnik:	North-Holland
ISSN:	0012-365X
COBISS.SI-ID:	1118479

Sekundarni jezik

Jezik:	Slovenski jezik
Naslov:	Pakiranja v dvodelnih prizmah in hiperkockah
Opis:	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.
Ključne besede:	2-pakirno število, odprto pakirno število, dvodelna prizma, hiperkocke, injektivno barvanje, celotno dominacijsko število

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj