آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 122 |
| تعداد مقالات | 1,538 |
| تعداد مشاهده مقاله | 1,628,316 |
| تعداد دریافت فایل اصل مقاله | 1,525,855 |
Eternal Domination Stability in Graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 16 آبان 1404 اصل مقاله (387.59 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.30729.2595 | ||
| نویسنده | ||
| P. Roushini Leely Pushpam* | ||
| Department of Mathematics, D.B. Jain College, Chennai 600 097, Tamil Nadu, India | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Domination؛ Eternal Domination؛ Stability | ||
| مراجع | ||
|
[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 | ||
|
آمار تعداد مشاهده مقاله: 81 تعداد دریافت فایل اصل مقاله: 40 |
||