Mathematics and Computational Sciences

An induced P3 packing k-partition number for Benzenoid system

Document Type : Original Article

Authors

Santiagu Theresal 1
Arul Amirtha Raja Susai 2
Antonysamy Leema Rose 3

1 Department of Mathematics, Auxilium College of Arts and Science for Women, Affiliated to Bharathithasan University, Pudukottai 622 302, India.

2 Department of Mathematics, St. Joseph's College of Engineering, OMR, Chennai-600119

3 Department of Mathematics, Auxilium College of Arts and Science for Women, Affiliated to Bharathithasan University, Pudukottai 622 302, India

https://doi.org/10.30511/mcs.2025.2076209.1582
Abstract
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 P3- packing number and an induced P3-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, algorithms
are 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

P3-Packing
Perfect P3-packing
Near Perfect P-packing
Rhombic Benzenoid System
and Zigzag Benzenoid System

Subjects

[1] Al Mutairi, A., Ali, B., & Manuel, D. P. (2015). Packing in carbon nanotubes. Journal of Combinatorial Mathematics and Combinatorial Computing, 92, 195–206. 
[2] Alon, N., Caro, Y., & Yuster, R. (1998). Packing and covering dense graphs. Journal of Combinatorial Designs, 6(6), 451–472. 
[3] Felzenbaum, A. (1993). Packing lines in a hypercube. Discrete Mathematics, 117, 107–112. 
[4] Bar-Yehuda, R., Halldorsson, M., Naor, J., Shachnai, H., & Shapira, I. (2002). Scheduling split intervals. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 732–741). 
[5] Bejar, R., Krishnamachari, B., Gomes, C., & Selman, B. (2001). Distributed constraint satisfaction in a wireless sensor tracking system. In Workshop on Distributed Constraint Reasoning, IJCAI. 
[6] Brewster, R. C., Hell, P., Pantel, S. H., Rizzi, R., & Yeo, A. (2003). Packing paths in digraphs. Journal of Graph Theory, 44(2), 81–94. 
[7] Cameron, K. (1989). Induced matchings. Discrete Applied Mathematics, 24, 97–102. 
[8] Kwun, Y. C., Zahid, M. A., Nazeer, W., Ali, A., Ahmad, M., & Kang, S. M. (2018). On the Zagreb polynomials of benzenoid systems. Open Physics, 16(1), 734–740.
[9] Dobson, E. (1997). Packing almost stars into the complete graph. Journal of Graph Theory, 25(2), 169–172. 
[10] Hardesty, L. (2010). Self-assembling computer chips. MIT News Office, Cambridge, MA.
[11] Hell, P., & Kirkpatrick, D. (1978). On the complexity of a generalized matching problem. In Proceedings of the 10th ACM Symposium (pp. 309–318).
[12] Jafari, H., Salehfard, S., & Aqababaei Dehkordi, D. (2024). Introducing a simple method for detecting the path between two different vertices in graphs. Mathematics and Computational Sciences, 4(4), 10–16. 
[13] Raja, S. M. J., Xavier, A., & Rajasingh, I. (2017). Induced H-packing k-partition problem in interconnection networks. International Journal of Computer Mathematics: Computer Systems Theory, 2, 136–146. 1, 1.2, 
[14] Kelmans, A. K. (1997). Optimal packing of induced stars in a graph. Discrete Mathematics, 173(1–3), 97–127. 
[15] Kakimura, N., Kawarabayashi, K., & Marx, D. (2011). Packing cycles through prescribed vertices. Journal of Combinatorial Theory, Series B, 101(5), 378–381.
[16] Kosowski, A., Małafiejski, M., & Zyli´ nski, P. (2006). An approximation algorithm for maximum P 3 -packing in subcubic graphs. Information Processing Letters, 99, 230–233.
[17] Kind, J., Niessen, T., & Mathar, R. (1998). Theory of maximum packing and related channel assignment strategies for cellular radio networks. Mathematical Methods of Operations Research, 48, 1–16. 
[18] Kwun, Y. C., Zahid, M. A., Nazeer, W., Ali, A., Ahmad, M., & Kang, S. M. (2018). On the Zagreb polynomials of benzenoid systems. Open Physics, 16(1), 734–740. 
[19] Lal, S., Sharma, K., & Bhat, V. K. (2022). On k-distance degree based topological indices of benzenoid systems. arXiv preprint arXiv:2212.04200. 
[20] Muthumalai, A., Rajasingh, I., & Shanthi, A. S. (2011). Packing of hexagonal networks. Journal of Combinatorial Mathematics and Combinatorial Computing, 79, 121–127. 
[21] Manuel, P., Rajasingh, I., Rajan, B., & Muthumalai, A. (2006). On induced matching partitions of certain interconnection networks. In Proceedings of the International Conference on Foundations of Computer Science (pp. 57–63), Las Vegas. 
[22] Rajasingh, I., Muthumalai, A., Bharati, R., & Shanthi, A. S. (2012). Packing in honeycomb networks. Journal of Mathematical Chemistry, 50(5), 1200–1209.
[23] Raja, S. M. J., Rajasingh, I., & Xavier, A. (2020). Induced H-packing k-partition of graphs. International Journal of Computer Mathematics: Computer Systems Theory, 1–18. 
[24] Theresal, S., Xavier, A., & Raja, S. M. J. (2019). Induced H-packing k-partition problem in certain networks. International Journal of Recent Technology and Engineering, 8(3), 1003–1010.
[25] Xavier, A., Theresal, S., & Raja, S. M. J. (2019). Induced H-packing k-partition number for certain graphs. International Journal of Computer Sciences and Engineering, 7(9), 91–95. 
[26] Xavier, A., Theresal, S., & Raja, S. M. J. (2020). Induced H-packing k-partition number for certain nanotubes and chemical graphs. Journal of Mathematical Chemistry, 58, 1177–1196. 
[27] Yap, H. (1988). Packing of graphs–A survey. Discrete Mathematics, 72(1–3), 395–404. 
[28] Yuan, J., & Wang, Q. (2003). Partition the vertices of a graph into induced matchings. Discrete Mathematics, 263, 323–329.
Mathematics and Computational Sciences
Volume 7, Issue 1
Winter 2026
Pages 152-161

  • Receive Date 30 October 2025
  • Revise Date 09 December 2025
  • Accept Date 23 December 2025

Home

Submit Manuscript

Reviewers

Contact Us