20.500.12556/DKUM-87124 Packings in bipartite prisms and hypercubes Pakiranja v dvodelnih prizmah in hiperkockah ▫$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šč. 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. 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 2-pakirno število odprto pakirno število dvodelna prizma hiperkocke injektivno barvanje celotno dominacijsko število true true false Angleški jezik Slovenski jezik Članek v reviji 2024-02-21 07:02:32 2024-02-28 13:37:15 2024-02-28 13:37:21 0000-00-00 00:00:00 2024 0 0 6 str. ǂiss. ǂ4, [article no.] 113875 ǂVol. ǂ347 Apr. 2024 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 181387523 10.1016/j.disc.2024.113875 0012-365X https://www.sciencedirect.com/science/article/pii/S0012365X24000062 1 cde1758e-d07e-11ee-bf60-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=176332 Fakulteta za naravoslovje in matematiko 0 0 0