Packing in honeycomb networks (Q714696)

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 packing number, denoted as \(\lambda(G,H)\), is then defined as the maximum number of vertex disjoint copies of \(H\) in \(G\). Moreover, an \(H\)-packing is called perfect if it covers all vertices of \(G\). It is obvious that when \(H=K_2\), the problem of determining the packing number becomes the maximum matching problem. In the present paper, authors study various packings for a special family of important chemical graphs known as honeycomb networks (which belong to the well known family of benzenoid graphs). In particular, the family of graphs \(HC(n)\), \(n \geq 1\), is defined in the following way: \(HC(1)\) is just a hexagon and \(HC(n)\) is obtained from \(HC(n-1)\) by adding a layer of hexagons around the boundary of \(HC(n-1)\). Note that the graphs \(HC(n)\) are also called coronenes or circumcoronenes. In Section 3, it is shown that there exists a perfect \(P_6\)-packing of \(HC(n)\) with \(n^2\) copies of \(P_6\). In the next section, an algorithm is described to pack \(HC(n)\) with \(C_6\) and therefore, a lower bound for \(\lambda(HC(n),C_6)\) is obtained. Moreover, the packing of a honeycomb torus network with copies of \(C_6\) is investigated in Section 5, and an algorithm for a \(K_{1,3}\)-packing of \(HC(n)\) is developed in Section 6. Finally, in the last section a procedure for an \(H\)-packing of \(HC(n)\) is described where \(H\) is a \(1,3\)-dimethyl cyclohexane.