Stability of 2-Domination Number of a Graph

Document Type : Original Scientific Paper

Authors

Department of Mathematical Sciences, ‎Yazd University‎, ‎89195-741‎ ‎Yazd‎, ‎Iran

10.22052/mir.2025.257573.1540

Abstract

‎This paper delves into the stability of the 2-domination number in simple undirected graphs‎. ‎The 2-domination number of a graph G‎, ‎$\gamma_2(G)$‎, ‎represents the minimum size of a vertex subset where every other vertex in the graph is adjacent to at least two members of the subset‎. ‎We define the $2$-domination stability‎, ‎$st_{\gamma_2}(G)$‎, ‎as the smallest number of vertices whose removal causes a change in $\gamma_2(G)$‎. ‎Our primary contributions include computing this parameter for specific graphs‎, ‎establishing various bounds for this stability‎, ‎and determining its behavior under certain graph operations combining two graphs‎.

Keywords

Main Subjects


[1] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, NewYork, 1998.
[2] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York (1998).
[3] D. P. Sumner and P. Blitch, Domination critical graphs, J. Combin. Theory Ser. B 34 (1983) 65-76, https://doi.org/10.1016/0095-8956(83)90007-2.
[4] J. Fulman, D. Hanson and G. Macgillivray, Vertex domination-critical graphs, Networks 25 (1995) 41-43, https://doi.org/10.1002/net.3230250203.
[5] D. P. Sumner, Critical concepts in domination, Discrete Math. 86 (1990) 33-46, https://doi.org/10.1016/0012-365X(90)90347-K.
[6] 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.
[7] N. Jafari Rad, E. Sharifi and M. Krzywkowski, Domination stability in graphs, Discrete Math. 339 (2016) 1909-1914,
https://doi.org/10.1016/j.disc.2015.12.026.
[8] G. Asemian, N. Jafari Rad, A. Tehranian and H. Rasouli, On the total Roman domination stability in graphs, AKCE Int. J. Graphs Comb. 18 (2021) 166-172, https://doi.org/10.1080/09728600.2021.1992257.
[9] A. Gorzkowska, M. A. Henning, M. Pilsniak and E. Tumidajewicz, Paired domination stability in graphs, Ars Math. Contemp. 22 (2022) #P2.04, https://doi.org/10.26493/1855-3974.2522.eb3.
[10] M. A. Henning and M. Krzywkowski, Total domination stability in graphs, Discrete Appl. Math. 236 (2018) 246-255,
https://doi.org/10.1016/j.dam.2017.07.022.
[11] Z. Li, Z. Shao and S.-j. Xu, 2-rainbow domination stability of graphs, J. Comb. Optim. 38 (2019) 836-845, https://doi.org/10.1007/s10878-019-00414-0.
[12] M. Mehryar and S. Alikhani, Weakly connected domination stability in graphs, Adv. Appl. Math. Sci. 16 (2016) 79-87.
[13] S. Alikhani and M. R. Piri, On the edge chromatic vertex stability number of graphs, AKCE Int. J. Graphs Comb. 20 (2023) 29-34, https://doi.org/10.1080/09728600.2022.2149367.
[14] S. Alikhani and S. Soltani, Stabilizing the distinguishing number of a graph, Comm. Algebra 46 (2018) 5460-5468,
https://doi.org/10.1080/00927872.2018.1469031.
[15] M. Edwards, A. Finbow, G. MacGillivray and S. Nasserasr, Independent domination bicritical graphs, Australas. J. Combin. 72 (2018) 446-471.
[16] F. Movahedi, M. H. Akhbari and S. Alikhani, The number of 2-dominating sets, and 2-domination polynomial of a graph, Lobachevskii J. Math. 42 (2021) 751-759, https://doi.org/10.1134/S1995080221040156.
[17] P. Erdos, A. Rényi and V. T. Sós, On a problem of graph theory, Stud. Sci. Math. Hung. 1 (1966) 215-235.
[18] S. Jahari and S. Alikhani, More on the enumeration of some kind of dominating sets in cactus chains, Math. Interdisc. Res. 7 (2022) 217-237, https://doi.org/10.22052/MIR.2022.246437.1352.
[19] C. Bujtás and S. Jaskó, Bounds on the 2-domination number, Discrete Appl. Math. 242 (2018) 4-15, https://doi.org/10.1016/j.dam.2017.05.014.
[20] L. Volkmann, A Nordhaus-Gaddum-type result for the 2-domination number, J. Combin. Math. Combin. Comput. 64 (2008) 227-235.
[21] S. Jahari and S. Alikhani, On the independent domination polynomial of a graph, Discrete Appl. Math. 289 (2021) 416 -426, https://doi.org/10.1016/j.dam.2020.10.019.