An induced P۳ packing k-partition number for Benzenoid system

Benzenoid systems are formed by collections of congruent hexagons arranged in the plane such that any two hexagons are either disjoint or share a common edge. These structures are naturally studied through graph-theoretic packing parameters. For a fixed graph H, an H-packing of a graph G is a family of vertex-disjoint subgraphs of G, each is isomorphic to H. In this work, we determine the P۳- packing number and an induced P۳-packing k-partition number for three standard benzenoid families: the triangular benzenoid system, the rhombic benzenoid system, and the zigzag benzenoid system. For each class, algorithmsare provided for computing these parameters, together with justification of their correctness. The results yield exact values for the corresponding packing and partition numbers in these benzenoid structures.

Keywords:

P۳-Packing , Perfect P۳-packing , Near Perfect P-packing , Rhombic Benzenoid System , and Zigzag Benzenoid System