Packing of Hexagonal Networks

Abstract

In cellular radio communication systems, the concept of maximum packing is used for dynamic channel assignment. An $H$-packing of a graph $G$ is a set of vertex-disjoint subgraphs of $G$, each of which is isomorphic to a fixed graph $H$. The maximum $H$-packing problem is to find the maximum number of vertex-disjoint copies of $H$ in $G$, called the packing number, denoted by $\lambda (G,H)$. In this paper, we determine the maximum $H$-packing number of hexagonal networks when $H$ is isomorphic to $P_6$ as well as $K_{1,3}$.