Characterization of the stability number of connected graphs
Characterization of the stability number of connected graphs
Let be a connected graph. Write for its strong domination number, for the stability value of , and for its vertex connectivity. A vertex set is called critical for maintaining when its removal changes the strong domination number as specified by the stability value.
Stability characterization conjecture. For every integer ,
if and only if all of the following hold:
- ;
- has at least vertices whose removal does not change ;
- every set of vertices is contained in some minimum strong dominating set of for some set with ; and
- there exists a set of vertices that is critical for maintaining .
The conjecture proposes a structural characterization of graphs with prescribed stability value. The source states that the problem of characterizing graphs with a given stability value remains open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Saeid Alikhani, Mazharuddin Mehraban and Hossein Shojaaldini Ardakani, “Stability of the Strong Domination Number of Graphs”, arXiv:2601.03891 (2026).
Additional references
11 papers in this index state this conjecture (2017–2026). The statement above is taken from the most recent of them; the others are arXiv:2503.02116, arXiv:2402.14093, arXiv:2402.01006, arXiv:2304.11462, arXiv:2201.04380, arXiv:2102.11179, arXiv:2012.07737, arXiv:1811.09765, arXiv:1710.00640, arXiv:1702.03439.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.