Eternal Domination Stability in Graphs

Articles in Press

Document Type : Original paper

Author

Department of Mathematics, D.B. Jain College, Chennai 600 097, Tamil Nadu, India

Abstract

The concept of domination stability in graphs was introduced in 1983 by Bauer, Harary, Nieminen and Suffel and has been further studied by Nader Jafari Rad, Elahe Sharifi, Marcin Krzywkowski. The $\gamma^+$-stability of $G$, denoted by $\gamma^+(G)$, is the minimum number of vertices whose removal from $G$ increases the domination number. The $\gamma^-$-{\it stability} of $G$, denoted by $\gamma^-(G)$, is the minimum number of vertices whose removal from $G$ decreases the domination number. The {\it domination stability} of $G$, denoted by $st_\gamma(G)$, is the minimum number of vertices whose removal changes the domination number. In this paper the concept of domination stability is extended to $m$-eternal domination. {\it Eternal domination} of a graph requires the vertices of a graph to be protected, against infinitely long sequences of attacks, by guards located at vertices (at most one guard in each vertex), and a guard must move from a neighboring vertex to an attacked vertex with the requirement that the configuration of guards induces a dominating set at all times. Two models of the problem, one in which only one guard moves at a time and one in which more than one guard may move simultaneously are studied in the literature. The model of eternal domination in which more than one guard move simultaneously is called the $m$-eternal domination. The $m$-eternal domination number, $\gamma_m^\infty(G)$ of a graph $G$ is the minimum number of guards needed to defend $G$ against any such sequence of attacks.

Keywords

Main Subjects

References

[1] G. Bagan, A. Joffard, and H. Kheddouci, Eternal dominating sets on digraphs and orientations of graphs, Discrete Appl. Math. 291 (2021), 99–115. https://doi.org/10.1016/j.dam.2020.10.024
[2] D. Bauer, F. Harary, J. Nieminen, and C.L. Suffel, Domination alteration sets in graphs, Discrete Math. 47 (1983), 153–161. https://doi.org/10.1016/0012-365X(83)90085-7
[3] R.C. Brigham, P.Z. Chinn, and R.D. Dutton, Vertex domination-critical graphs, Networks 18 (1988), no. 3, 173–179.
https://doi.org/10.1002/net.3230180304
[4] A.P. Burger, E.J. Cockayne, W.R. Grundlingh, C.M. Mynhardt, J.H. Van Vuuren, and W. Winterbach, Finite order domination in graphs, J. Combin. Math. Combin. Comput. 49 (2004), 159–176.
[5] A.P. Burger, E.J. Cockayne, W.R. Grundlingh, C.M. Mynhardt, J.H. van Vuuren, and W. Winterbach, Infinite order domination in graphs, J. Combin. Math. Combin. Comput. 50 (2004), 179–194.
[6] E.J. Cockayne, P.J.P. Grobler, W.R. Grundlingh, J. Munganga, and J.H. Van Vuuren, Protection of a graph, Util. Math. 67 (2005), 19–32.
[7] Stephen Finbow and Martin F van Bommel, The eternal domination number for 3 × n grid graphs., Australas. J Comb. 76 (2020), no. 1, 1–23.
[8] A. Gagnon, A. Hassler, J. Huang, A. Krim-Yee, F. Mc Inerney, A. ZacarÍas, B. Seamone, and V. Virgile, A method for eternally dominating strong grids, Discrete Math. Theor. Comput. Sci. 22 (2020), no. 2, #8.
[9] W. Goddard, S.M. Hedetniemi, and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005), no. 1, 169–180.
[10] F. Harary, Graph Theory, Addison Wesley, Reading, Mass, 1969.
[11] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Taylor & Francis, 1998.
[12] N. Jafari Rad, E. Sharifi, and M. Krzywkowski, Domination stability in graphs, Discrete Math. 339 (2016), no. 7, 1909–1914. https://doi.org/10.1016/j.disc.2015.12.026
[13] W.F. Klostermeyer and G. MacGillivray, Eternal domination in trees, J. Combin. Math. Combin. Comput. 91 (2014), 31–50.
[14] W.F. Klostermeyer and C.M. Mynhardt, Eternal total domination in graphs, Ars Combin. 107 (2012), 473–492.
[14] F. Mc Inerney, N. Nisse, and S. P´erennes, Eternal domination: D-dimensional cartesian and strong grids and everything in between, Algorithmica 83 (2021), no. 5, 1459–1492. https://doi.org/10.1007/s00453-020-00790-8
[15] C.M. Mynhardt, Eternal total domination in graphs, Ars Combin. 107 (2012), 473–492.
[16] P.R.L. Pushpam and G. Navamani, Eternal $m$-security in certain classes of graphs, J. Combin. Math. Combin. Comput. 92 (2015), 25–38.
[17] P.R.L Pushpam and P.A. Shanthi, Changing and unchanging in $m$-eternal total domination in graphs, Electron. Notes Discrete Math. 53 (2016), 181–198.  https://doi.org/10.1016/j.endm.2016.05.017
[18] R.L Pushpam and P.A. Shanthi, m-eternal total domination in graphs, Discrete Math. Algorithms Appl. 8 (2016), no. 3, 1650055. https://doi.org/10.1142/S1793830916500555
[19] D.P. Sumner, Critical concepts in domination, Discrete Math. 86 (1990), no. 1–3, 33–46. https://doi.org/10.1016/0012-365X(90)90347-K
[20] D.P. Sumner and P. Blitch, Domination critical graphs, J. Combin. Theory Ser. B 34 (1983), no. 1, 65–76. https://doi.org/10.1016/0095-8956(83)90007-2
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 07 November 2025

Files

Share

How to cite

Statistics