Packings in bipartite prisms and hypercubes

Abstract

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 }^{\mathrm{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 }^{\mathrm{o}}(G\square 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 }^{\mathrm{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.

11 pages, 2 figures, 1 table