Extending Certified Domination: Bondage Numbers in Generalized Petersen Graphs

Article Sidebar

PDF
DOI: https://doi.org/10.28924/2291-8639-23-2025-273
Published: Nov 5, 2025
Cite as:
G. Navamani, N. Sumathi, A. Ramachandran, N. Vijaya, A. Vijayalakshmi, S. Annadurai, Extending Certified Domination: Bondage Numbers in Generalized Petersen Graphs, Int. J. Anal. Appl., 23 (2025), 273.

Main Article Content

G. Navamani, N. Sumathi, A. Ramachandran, N. Vijaya, A. Vijayalakshmi, S. Annadurai

Abstract

The paper extends the concept of bondage numbers to certified domination, introducing the certified bondage number of a graph. A certified dominating set R is a dominating set of a graph H, if every vertex in R has either zero or at least two neighbours in V\R, where V is the vertex set of H. The minimum cardinality of certified dominating set of H is the certified domination number of H denoted by γcer(H). The bondage number b(H) is defined to be the cardinality of least number of edges F ⊂ E(H) such that γ(H − F) > γ(H). Motivated by this parameter, we extended this concept on certified domination number and defined certified bondage number of a graph H, b+cer(H) [b−cer(H)] to be the cardinality of the least number of edges F ⊂ E(H) such that γcer(H−F) > γcer(H) [γcer(H−F) < γcer(H)] that is minimum number of edges to be removed to increase (or decrease) the certified domination number of H. In this paper, we establish the values of certified bondage number for generalised Petersen graphs P(n, k), where k = 1, 2, as well as for certain classes of graphs.

Article Details

References

  1. L. Pei, X. Pan, The Bondage Number of Generalized Petersen Graphs P(n, 2), Discret. Dyn. Nat. Soc. 2020 (2020), 7607856. https://doi.org/10.1155/2020/7607856.
  2. A.A. khalil, Determination and Testing the Domination Numbers of Helm Graph, Web Graph and Levi Graph Using MATLAB, J. Educ. Sci. 24 (1999), 103–116. https://doi.org/10.33899/edusj.1999.58719.
  3. R. Kooij, On Generalized Windmill Graphs, Linear Algebr. Appl. 565 (2019), 25–46. https://doi.org/10.1016/j.laa.2018.11.025.
  4. J. Blue, Domination and Dominion of Some Graphs, Ph.D. Dissertation, Elizabeth City State University, 2020.
  5. M. Dettlaff, M. Lemańska, J. Topp, R. Ziemann, P. Żyliński, Certified Domination, AKCE Int. J. Graphs Comb. 17 (2020), 86–97. https://doi.org/10.1016/j.akcej.2018.09.004.
  6. T.W. Haynes, S. Hedetniemi, P. Slater, Fundamentals of Domination in Graphs, CRC Press, 2013. https://doi.org/10.1201/9781482246582.
  7. A.T. Rolito G. Eballe, R.G. Eballe, Domination Defect for the Join and Corona of Graphs, Appl. Math. Sci. 15 (2021), 615–623. https://doi.org/10.12988/ams.2021.914597.
  8. E. Enriquez, G. Estrada, C. Loquias, R.J. Bacalso, L. Ocampo, Domination in Fuzzy Directed Graphs, Mathematics 9 (2021), 2143. https://doi.org/10.3390/math9172143.
  9. F. Harary, Graph Theory, Addison-Wesley Publishing Company, 1969.
  10. S.D. Raj, S.G.S. Kumari, A.M. Anto, Certified Domination Number in Subdivision of Graphs, Int. J. Mech. Eng. 6 (2021), 4324–4327.
  11. S.D. Raj, S.G.S. Kumari, Certified Domination Number in Product of Graphs, Turk. J. Comput. Math. Educ. 11 (2020), 1166–1170.
  12. M. Dettlaff, M. Lemańska, M. Miotk, J. Topp, R. Ziemann, et al., Graphs with Equal Domination and Certified Domination Numbers, arXiv:1710.02059 (2017). http://arxiv.org/abs/1710.02059v2.
  13. T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, D. Jacobs, J. Knisely, et al., Domination Subdivision Numbers, Discuss. Math. Graph Theory 21 (2001), 239–253. https://doi.org/10.7151/dmgt.1147.
  14. P.R.L. Pushpam, G. Navamani, Eternal m-Security in Certain Classes of Graphs, J. Comb. Math. Comb. Comput. 92 (2015), 25–38.
  15. J.F. Fink, M.S. Jacobson, L.F. Kinch, J. Roberts, The Bondage Number of a Graph, Discret. Math. 86 (1990), 47–57. https://doi.org/10.1016/0012-365x(90)90348-l.
  16. J. Xu, On Bondage Numbers of Graphs: A Survey with Some Comments, Int. J. Comb. 2013 (2013), 595210. https://doi.org/10.1155/2013/595210.
  17. B.L. Hartnell, D.F. Rall, Bounds on the Bondage Number of a Graph, Discret. Math. 128 (1994), 173–177. https://doi.org/10.1016/0012-365x(94)90111-2.
  18. A. Abinaya, K. Gomathi, P. Sivagami, R. Ramya, Domination of Graph Theory and its Applications, Int. J. Adv. Eng. Manag. 5 (2023), 741–744.
  19. Seyedeh M.M. Majd, H.R. Maimani, A. Tehranian, On the Grundy Bondage Numbers of Graphs, Facta Univ. Ser. Math. Inform. 38 (2023), 91–96.
  20. A.N. Hayyu, Dafik, I.M. Tirta, R. Adawiyah, R.M. Prihandini, Resolving Domination Number of Helm Graph and It’s Operation, J. Phys.: Conf. Ser. 1465 (2020), 012022. https://doi.org/10.1088/1742-6596/1465/1/012022.
  21. S. Nagarajan, Hop Domination Number of Tadpole Graph $T_{m,n}$, Dogo Rangsang Res. J. 12 (2022), 89–105.
  22. B. Javad Ebrahimi, N. Jahanbakht, E. Mahmoodian, Vertex Domination of Generalized Petersen Graphs, Discret. Math. 309 (2009), 4355–4361. https://doi.org/10.1016/j.disc.2009.01.018.
  23. G. Navamani, N. Sumathi, Certified Domination Subdivision Number of Trees, NeuroQuantology 20 (2022), 6161–6166.
  24. E.P. Inza, N. Vakhania, J.M.S. Almira, F.A.H. Mira, Algorithms for the Global Domination Problem, Comput. Oper. Res. 173 (2025), 106876. https://doi.org/10.1016/j.cor.2024.106876.
  25. T.W. Haynes, M.A. Henning, A Characterization of Graphs Whose Vertex Set Can Be Partitioned Into a Total Dominating Set and an Independent Dominating Set, Discret. Appl. Math. 358 (2024), 457–467. https://doi.org/10.1016/j.dam.2024.08.008.
  26. T. Turacı, G. Koçay, On the Average Lower Bondage Number of Graphs Under Join and Corona Operations, Numer. Methods Partial. Differ. Equ. 38 (2020), 654–665. https://doi.org/10.1002/num.22675.
  27. N. De Neef, V. Coppens, W. Huys, M. Morrens, Bondage-Discipline, Dominance-Submission and Sadomasochism (BDSM) from an Integrative Biopsychosocial Perspective: A Systematic Review, Sex. Med. 7 (2019), 129–144. https://doi.org/10.1016/j.esxm.2019.02.002.
  28. W. Zhao, H. Zhang, Upper Bounds on the Bondage Number of the Strong Product of a Graph and a Tree, Int. J. Comput. Math. 95 (2017), 511–527. https://doi.org/10.1080/00207160.2017.1291931.
  29. S. Karthikeyan, S. Donganont, C. Park, K. Tamilvanan, Y. Wang, Hyperstability of Functional Equation Deriving from Quintic Mapping in Banach Space by Fixed Point Method, Eur. J. Pure Appl. Math. 18 (2025), 5757. https://doi.org/10.29020/nybg.ejpam.v18i1.5757.
  30. N. Vijaya, P. Suganthi, E.A. Bagyam, M. Balamurugan, N. Prabaharan, et al., Fixed Point Technique: Hyers-Ulam Stability Results Deriving from Cubic Mapping in Fuzzy Normed Spaces, Commun. Math. Appl. 15 (2024), 855–864. https://doi.org/10.26713/cma.v15i2.2679.
  31. K. Tamilvanan, B. Deepa, S. Muthu selvi, R. Prakash, R. Sathish Kumar, Intuitionistic Fuzzy Stability Results of Additive Functional Equation by Two Different Approaches, J. Phys.: Conf. Ser. 1964 (2021), 022024. https://doi.org/10.1088/1742-6596/1964/2/022024.