2023/09/10 by Brešar, Boštjan, Klavžar, Sandi, Rall, Douglas F. · 2 citations
#05C69 #05C76 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2309.04963
The 2-packing number ρ2(G) of a graph G is the cardinality of a largest 2-packing of G and the open packing number ρ\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 ρ\rm o(G\Box K2) = 2ρ2(G). For hypercubes, the lower bounds ρ2(Qn) ≥ 2n - \lfloor log n\rfloor -1 and ρ\rm o(Qn) ≥ 2n - \lfloor log (n-1)\rfloor -1 are established. These findings are applied to injective colorings of hypercubes. In particular, it is demonstrated that Q9 is the smallest hypercube which is not perfect injectively colorable. It is also proved that γt(Q2k× H) = 22k-kγt(H), where H is an arbitrary graph with no isolated vertices.