Computing a maximal clique of graphs of cofinite submonoids

Anam Shahzadi and Muhammad Ahsan Binyamin
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 32, 2026, Number 1, Pages 23–42
DOI: 10.7546/nntdm.2026.32.1.23-42
Full paper (PDF, 312 Kb)

Details

Authors and affiliations

Anam Shahzadi
Department of Mathematics, Government College University Faisalabad
Jhung Road, Faisalabad, Pakistan

Muhammad Ahsan Binyamin
Department of Mathematics, Government College University Faisalabad
Jhung Road, Faisalabad, Pakistan

Abstract

A graph G_{\mathfrak{S}} is called an \mathfrak{S}(\tau,\mathfrak{e})-graph if there exists a numerical semigroup \mathfrak{S} with multiplicity \tau and embedding dimension \mathfrak{e} such that V(G_{\mathfrak{S}})=\{v_{\alpha}:\alpha \in \N_{0}\setminus \mathfrak{S} \} and E(G_{\mathfrak{S}})=\{v_{\alpha}v_{\beta}\Leftrightarrow \alpha+\beta \in \mathfrak{S}\}. In this article, we give an algorithmic way to compute the clique~number and the minimum degree of \mathfrak{S}(\tau,3)-graphs, where \mathfrak{S} is a class of symmetric numerical semigroups with arbitrary multiplicity and embedding dimension 3. On this basis, we give some bounds for the atom bond connectivity index of graphs G_{\mathfrak{S}} in terms of Randić connectivity index, the first and second Zagreb indices, the maximum and minimum degrees, and the clique number.

Keywords

  • Symmetric numerical semigroup
  • Gaps
  • Multiplicity
  • Frobenius number
  • Embedding dimension
  • Complete graphs
  • Minimum and maximum degree
  • Clique number

2020 Mathematics Subject Classification

  • 05C25
  • 06A11
  • 11D72

References

  1. Alali, A. S., Binyamin, M. A., & Mehtab, M. (2024). A conjecture for the clique number of graphs associated with symmetric numerical semigroups of arbitrary multiplicity and embedding dimension. Symmetry, 16(7), Article ID 854.
  2. Anderson, D. F., & Livingston, P. S. (1999). The zero-divisor graph of a commutative ring. Journal of Algebra, 217, 434–447.
  3. Balaban, A. T. (1985). Applications of graph theory in chemistry. Journal of Chemical Information and Computer Sciences, 25(3), 334–343.
  4. Baloda, B., & Kumar, J. (2024). Upper ideal relation graphs associated to rings. Soft Computing, 28, 10815–10826.
  5. Bianchi, M., Cornaro, A., Palacios, J. L., & Torriero, A. (2016). New upper bounds for the ABC index. MATCH Communications in Mathematical and in Computer Chemistry, 76(1), 117–130.
  6. Binyamin, M. A., Ali, W., Aslam, A., & Mahmood, H. (2022). A complete classification of planar graphs associated with the ideal of the numerical semigroup. Iranian Journal of Science and Technology. Transection Science, 46, 491–498.
  7. Binyamin, M. A., Siddiqui, H. M. A., Khan, N. M., Aslam, A., & Rao, Y. (2019).
    Characterization of graphs associated with numerical semigroups. Mathematics, 7(6), Article ID 557.
  8. Biswas, B., & Kar, S. (2024). Some properties of generalized comaximal graph of commutative ring. Soft Computing, 28(5), 3783–3791.
  9. Bonchev, D. (1991). Chemical Graph Theory: Introduction and Fundamentals. CRC Press, Boca Raton.
  10. Bondy, J. A., & Murty, U. S. R. (1976). Graph Theory with Applications. Macmillan, Ontario.
  11. Cambie, S., Wagner, S., & Wang, H. (2021). On the maximum mean subtree order of trees. European Journal of Combinatorics, 97, Article ID 103388.
  12. Das, K. C., Rodr´ıguez, J. M., & Sigarreta, J. M. (2020). On the maximal general ABC index of graphs with given maximum degree. Applied Mathematics and Computation, 386, Article ID 125531.
  13. Diudea, M. V., Gutman, I., & Jantschi, L. (2001). Molecular Topology. Nova Science Publishers, Huntington, NY, USA.
  14. Estrada, E. (2008). Atom–bond connectivity and the energetic of branched alkanes. Chemical Physics Letters, 463(4–6), 422–425.
  15. Estrada, E. (2017). The ABC matrix. Journal of Mathematical Chemistry, 55, 1021–1033.
  16. Estrada, E., Torres, L., Rodriguez, L., & Gutman, I. (1998). An atom-bond connectivity index: modelling the enthalpy of formation of alkanes. Indian Journal of Chemistry. Sect. A: Inorganic, Physical, Theoretical & Analytical, 37, 849–855.
  17. Gan, L., Hou, H., & Liu, B. (2011). Some results on atom-bond connectivity index of graphs. MATCH Communications in Mathematical and in Computer Chemistry, 66(2), 669–680.
  18. García-Sánchez, P. A., & Rosales, J. C. (1999). Numerical semigroups generated by intervals. Pacific Journal of Mathematics, 191(1), 75–83.
  19. Gutman, I., & Trinajstić, N. (1972). Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons. Chemical Physics Letters, 17(4), 535–538.
  20. Halaš, R., & Pócs, J. (2024). On zero-divisor graphs of infinite posets. Soft Computing, 28, 12113–12118.
  21. Hashemi, E., Alhevaz, A., & Yoonesian, E. (2016). On zero divisor graph of unique product monoid rings over Noetherian reversible ring. Categories and General Algebraic Structures with Applications, 4(1), 95–114.
  22. Hua, H., Das, K. C., & Wang, H. (2019). On atom-bond connectivity index of graphs. Journal of Mathematical Analysis and Applications, 479(1), 1099–1114.
  23. Knor, M., Sedlar, J., & Škrekovski, R. (2026). The subpath number of cactus graphs. Applied Mathematics and Computation, 509, Article ID 129646.
  24. Knor, M., Sedlar, J., Škrekovski, R., & Yang, Y. (2026). Invitation to the subpath number. Applied Mathematics and Computation, 509, Article ID 129646.
  25. Kumar, B. D., Ajay, S., & Rahul, D. (2021). Nilpotent graph. Theory and Applications of Graphs, 8(1), Article ID 2.
  26. Mason, O., & Verwoerd, M. (2007). Graph theory and networks in biology. IET Systems Biology, 1(2), 89–119.
  27. Meier, J. (2008). Groups Graphs and Trees: An Introduction to the Geometry of Infinite Groups. Cambridge University Press, Cambridge, UK.
  28. Poonkuzhali, S., & Jayagopal, R. (2024). Dominated coloring in certain networks. Soft Computing, 28, 7003–7011.
  29. Randić, M. (1975). Characterization of molecular branching. Journal of the American Chemical Society, 97(23), 6609–6615.
  30. Rao, Y., Binyamin, M. A., Aslam, A., Mehtab, M., & Fazal, S. (2023). On the planarity of graphs associated with symmetric and pseudo symmetric numerical semigroups. Mathematics, 11(7), Article ID 1681.
  31. Reba, K., Guid, M., Rozman, K., Janežič, D., & Konc, J. (2021). Exact maximum clique algorithm for different graph types using machine learning. Mathematics, 10(1), Article ID 97.
  32. Shen, R. (2010). Intersection graphs of subgroups of finite groups. Czechoslovak Mathematical Journal, 60(4), 945–950.
  33. Shirinivas, S. G., Vetrivel, S., & Elango, N. M. (2010). Applications of graph theory in computer science an overview. International Journal of Engineering Science and Technology, 2(9), 4610–4621.
  34. Todeschini, R., & Consonni, V. (2008). Handbook of Molecular Descriptors. John Wiley & Sons.
  35. Turán, P. (1941). An extremal problem in graph theory. Középiskolai Matematikai és Fizikai Lapok, 48, 436–452.
  36. Wang, R. (2024). On the difference of mean subtree orders under edge contraction. Journal of Combinatorial Theory, Series B, 169, 45–62.
  37. Yang, Y., Jin, B. B.,& Lu, M. (2023). Computing the expected subtree number of random hexagonal and phenylene chains based on probability matrices. Discrete Applied Mathematics, 339, 184–201.
  38. Yang, Y., Jin, B. B.,& Sun, X. (2025). Exact counting of subtrees with diameter no more than d in trees: A generating function approach. Information and Computation, 307, Article ID 105353.
  39. Yaraneri, E. (2013). Intersection graph of a module. Journal of Algebra and Its Applications, 12(05), Article ID 1250218.

Manuscript history

  • Received: 18 April 2025
  • Revised: 23 November 2025
  • Accepted: 10 December 2025
  • Online First: 19 February 2026

Copyright information

Ⓒ 2026 by the Authors.
This is an Open Access paper distributed under the terms and conditions of the Creative Commons Attribution 4.0 International License (CC BY 4.0).

Related papers

Cite this paper

Shahzadi, A., & Binyamin, M. A. (2026). Computing a maximal clique of graphs of cofinite submonoids. Notes on Number Theory and Discrete Mathematics, 32(1), 23-42, DOI: 10.7546/nntdm.2026.32.1.23-42.

Comments are closed.