Induced \(H\)-packing \(k\)-partition problem in certain carbon based nanostructures (Q2038934)

Let \(H\) be a fixed graph. An \(H\)-packing in a graph \(G = (V, E)\) is a collection of pairwise vertex-disjoint subgraphs of \(G\) that are isomorphic to \(H\). The largest number of vertex disjoint copies of \(H\) in \(G\) is called the packing number of \(G\) (with respect to \(H\)). An \(H\)-packing of a graph \(G\) is perfect if every vertex of \(V(G)\) belongs to one \(H\)-subgraph of this \(H\)-packing. Let a graph \(G\) admits a perfect (or a so-called almost perfect) \(H\)-packing denoted by \(\mathcal{H}\). A set of induced \(H\)-subgraphs of \(G\) is independent if a pair \(H_i, H_j\) of \(H\)-subgraphs of this set does not have a common vertex, and \(E(G)\) does not admit an edge \(e\) such that one end-vertex of \(e\) belongs to \(H_i\) and the other to \(H_j\). A partition of \(\mathcal{H}\) into \(k\) independent sets of \(H\)-subgraphs such that \(k\) is minimal is called the induced \(H\)-packing \(k\)-partition problem of \(G\), while the minimal \(k\) is called the induced \(H\)-packing \(k\)-partition number. Carbon nanotubes consist of carbon atoms linked in hexagonal shapes, with each carbon atom covalently bonded to three other carbon atoms. They form a tube shape where carbon atoms are located at apexes of regular hexagons on two-dimensional surfaces. Carbon nanotubes admit several different shapes such as armchair, chiral and zigzag configurations. Various surface nanotemplates that are naturally or artificially designed at the nanometre scale have been used to form periodic nanostructure arrays. The process of setting up specific patterns is equivalent to packing in the corresponding molecular graph (a finite graph consisting of the carbon-atom skeleton of an organic molecule). The paper considers \(H\)-packings and establishes the corresponding packing and induced \(H\)-packing \(k\)-partition number for several armchair, zigzag and other carbon nanotubes with \(H\) isomorphic to \(P_3\).