Stability of 2-domination number of a graph

2025/07/24 by Mazharuddin Mehraban, Mehraban, Mazharuddin, ‎Saeid Alikhani +1
Computer Science · #Advanced Graph Theory Research #Optimization and Search Problems #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2507.18535

Abstract

This paper delves into the stability of the 2-domination number in simple undirected graphs. The 2-domination number of a graph G, γ₂(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_γ2(G), as the smallest number of vertices whose removal causes a change in γ₂(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.

Citations

• On independent domination in direct products
• On the edge chromatic vertex stability number of graphs
• On the independent domination polynomial of a graph
• Bounds on the 2-domination number
• Stabilizing on the distinguishing number of a graph

Related

• Bounds on the 2-domination number
• On the equality of domination number and 2 -domination number
• Independent domination stability in graphs
• Domination and 2-degree-packing numbers in graphs
• The sub-k-domination number of a graph with applications to k-domination