Independent domination stability in graphs
*Saeid AlikhaniCorresponding authoralikhani@yazd.ac.irDepartment of Mathematical SciencesYazd UniversityYazd, 89195-741, Iran0000-0002-1801-203XView full profile → , M. MehrabanMazharmehraban2020@gmail.comDepartment of Mathematical SciencesYazd UniversityYazd, 89195-741, Iran0009-0008-4012-723XView full profile → , H. Golmohammadih.golmohammadi@g.nsu.ruSiberian State University of Telecommunications and Information SciencesNovosibirsk, Russia0000-0003-0767-0755View full profile → , A. Zakharova.zakharov3@g.nsu.ruNovosibirsk State UniversityNovosibirsk, 630090, Russia0009-0003-0630-6887View full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Nov 2023
- Published Online:
- 23 Mar 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JDMSC-2344
- Pages:
- 2673–2683
Abstract
A non-empty subset S ⊆ V of the vertex set of a simple graph G = (V, E) is called an independent dominating set if every vertex not in S is adjacent to at least one vertex in S, and no two vertices in S are adjacent to each other. The independent domination number of G, denoted by γi (G), is the smallest possible size of such a set. The independent domination stability (or simply id-stability) of G is defined as the minimum number of vertices that must be removed from the graph to alter its independent domination number. In this paper, we explore various properties of independent domination stability in graphs. Specifically, we establish several bounds and determine the id-stability for certain graph operations involving two graphs.
Keywords
Subject Classifications
References
[1] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs. New York, NY, USA: Marcel Dekker (1998).
[2] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Domination in Graphs: Advanced Topics. New York, NY, USA: Marcel Dekker (1998).
[3] M. A. Henning and M. Krzywkowski, “Total domination stability in graphs,” Discrete Applied Mathematics, vol. 236, pp. 246–255 (2018).
[4] V. R. Kulli, B. Chaluvaraju, and M. Kumara, “Graphs with equal secure total domination and inverse secure total domination numbers,” Journal of Information and Optimization Sciences, vol. 39, no. 2, pp. 467–473 (2018).
[5] H. Yang and X. Zhang, “The independent domination numbers of strong product of two cycles,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 21, nos. 7–8, pp. 1495–1507 (2018).
[6] D. P. Sumner and P. Blitch, “Domination critical graphs,” Journal of Combinatorial Theory, Series B, vol. 34, pp. 65–76 (1983).
[7] J. Fulman, D. Hanson, and G. MacGillivray, “Vertex domination-critical graphs,” Networks, vol. 25, no. 2, pp. 41–43 (1995).
[8] D. P. Sumner, “Critical concepts in domination,” Discrete Mathematics, vol. 86, pp. 33–46 (1990).
[9] D. Bauer, F. Harary, J. Nieminen, and C. L. Suffel, “Domination alteration sets in graphs,” Discrete Mathematics, vol. 47, nos. 2–3, pp. 153–161 (1983).
[10] N. Jafari Rad, E. Sharifi, and M. Krzywkowski, “Domination stability in graphs,” Discrete Mathematics, vol. 339, pp. 1909–1914 (2016).
[11] G. Asemian, N. Jafari Rad, A. Tehranian, and H. Rasouli, “On the total Roman domination stability in graphs,” AKCE International Journal of Graphs and Combinatorics, vol. 18, no. 3, pp. 166–172 (2021).
[12] A. Gorzkowska, M. A. Henning, M. Pilśniak, and E. Tumidajewicz, “Paired domination stability in graphs,” Ars Mathematica Contemporanea, vol. 22, p. P2.04 (2022).
[13] Z. Li, Z. Shao, and S.-J. Xu, “2-rainbow domination stability of graphs,” Journal of Combinatorial Optimization, vol. 38, pp. 836–845 (2019).
[14] M. Mehryar and S. Alikhani, “Weakly connected domination stability in graphs,” Advances in Applied Mathematics and Sciences, vol. 16, no. 2, pp. 79–87 (2016).
[15] S. Alikhani and M. R. Piri, “On the edge chromatic vertex stability number of graphs,” AKCE International Journal of Graphs and Combinatorics, vol. 20, no. 1, pp. 29–34 (2023).
[16] S. Alikhani and S. Soltani, “Stabilizing the distinguishing number of a graph,” Communications in Algebra, vol. 46, no. 12, pp. 5460–5468 (2018).
[17] M. Edward, A. Finbow, G. MacGillivray, and S. Nasserasr, “Independent domination bicritical graphs,” Australasian Journal of Combinatorics, vol. 72, pp. 446–471 (2018).
[18] W. Goddard and M. A. Henning, “Independent domination in graphs: A survey and recent results,” Discrete Mathematics, vol. 313, no. 7, pp. 839–854 (2013).
[19] K. Kuenzel and D. F. Rall, “On independent domination in direct products,” Graphs and Combinatorics, vol. 39, no. 7 (2023).
[20] P. Wu, H. Jiang, S. Nazari-Moghaddam, S. M. Sheikholeslami, Z. Shao, and L. Volkmann, “Independent domination stable trees and unicyclic graphs,” Mathematics, vol. 7, no. 820, pp. 1–17 (2019).
[21] P. Erdős, A. Rényi, and V. T. Sós, “On a problem of graph theory,” Studia Scientiarum Mathematicarum Hungarica, vol. 1, pp. 215–235 (1966).
[22] S. Jahari and S. Alikhani, “On the independent domination polynomial of a graph,” Discrete Applied Mathematics, vol. 289, pp. 416–426 (2021).
