Computational Analysis of Certified Reinforcement Numbers Across Specialized Graph Classes

Article Sidebar

PDF
DOI: https://doi.org/10.28924/2291-8639-23-2025-211
Published: Aug 25, 2025
Cite as:
G. Navamani, N. Sumathi, N. Vijaya, R. Arasu, Lalitha Ramachandran, M. Balamurugan, Computational Analysis of Certified Reinforcement Numbers Across Specialized Graph Classes, Int. J. Anal. Appl., 23 (2025), 211.

Main Article Content

G. Navamani, N. Sumathi, N. Vijaya, R. Arasu, Lalitha Ramachandran, M. Balamurugan

Abstract

A certified dominating set D of a graph G is a dominating set in which every vertex in D must have either no neighbors or at least two neighbors in V\D, where V denotes the set of all vertices in G. A certified domination number of G represented by γcer(G) is defined as the smallest size of such a certified dominating set of G. The reinforcement number r(G) is defined to be the cardinality of minimum number of edges F ⊂ E(Gˉ) such that γ(G + F) < γ(G), broadened this parameter to encompass certified domination and we define certified reinforcement number of a graph G, rcer(G) to be the cardinality of the minimum number of edges F ⊂ E(¯G) such that γcer(G + F) < γcer(G) that is minimum number of edges to be added to decrease the certified domination number of G at least by one. In this paper, we characterize the graph G for which rcer(G) = 1 and determine the values of certified reinforcement number for various classes of graphs.

Article Details

References

  1. A. Abinaya, K. Gomathi, P. Sivagami, R. Ramya, Domination of Graph Theory and its Applications, Int. J. Adv. Eng. Manag. 5 (2023), 741–744.
  2. V. Ayta{c{c}}, T. Turac{i}, Exponential Domination and Bondage Numbers in Some Graceful Cyclic Structure, Nonlinear Dyn. Syst. Theory 17 (2017), 139–149.
  3. M. Dettlaff, M. Lemańska, M. Miotk, J. Topp, R. Ziemann, P. Żyliński, Graphs with Equal Domination and Certified Domination Numbers, arXiv:1710.02059 (2017). http://arxiv.org/abs/1710.02059v2.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. T.W. Haynes, S. Hedetniemi, P. Slater, Fundamentals of Domination in Graphs, CRC Press, 2013. https://doi.org/10.1201/9781482246582.
  10. F. Harary, Graph Theory (On Demand Printing of 02787), CRC Press, 2018. https://doi.org/10.1201/9780429493768.
  11. J.R. Blair, W. Goddard, S.T. Hedetniemi, S. Horton, P. Jones, G. Kubicki, On Domination and Reinforcement Numbers in Trees, Discret. Math. 308 (2008), 1165–1175. https://doi.org/10.1016/j.disc.2007.03.067.
  12. I.S. Hamid, S.A. Prabhavathy, Majority Reinforcement Number, Discret. Math. Algorithms Appl. 08 (2016), 1650014. https://doi.org/10.1142/s1793830916500142.
  13. 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.
  14. G. Muhiuddin, N. Sridharan, D. Al-Kadi, S. Amutha, M.E. Elnair, Reinforcement Number of a Graph with Respect to Half-Domination, J. Math. 2021 (2021), 6689816. https://doi.org/10.1155/2021/6689816.
  15. G. Navamani, N. Sumathi, Certified Domination Subdivision Number of Trees, NeuroQuantology 20 (2022), 6161–6166.
  16. S.D. Raj, S.G.S. Kumari, Certified Domination Number in Product of Graphs, Turk. J. Comput. Math. Educ. 11 (2020), 1166–1170.
  17. 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.
  18. H.A. Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam, S.M. Sheikholeslami, Total Roman Reinforcement in Graphs, Discuss. Math. Graph Theory 39 (2019), 787–803. https://doi.org/10.7151/dmgt.2108.
  19. J. Kok, C.M. Mynhardt, Reinforcement in Graphs, Congr. Numer. 79 (1990), 225–231.
  20. G. Navamani, Certified Bondage Number for Circulant Graphs, Adv. Nonlinear Var. Inequal. 28 (2024), 501–509. https://doi.org/10.52783/anvi.v28.3119.