Characterization of the stability number of connected graphs

From papers

Let GG be a connected graph. Write γst(G)\gamma_{st}(G) for its strong domination number, stγst(G)\operatorname{st}_{\gamma_{st}}(G) for the stability value of γst\gamma_{st}, and κ(G)\kappa(G) for its vertex connectivity. A vertex set is called critical for maintaining γst\gamma_{st} when its removal changes the strong domination number as specified by the stability value.

Stability characterization conjecture. For every integer p1p\ge 1,

stγst(G)=p+1\operatorname{st}_{\gamma_{st}}(G)=p+1

if and only if all of the following hold:

  1. κ(G)p\kappa(G)\ge p;
  2. GG has at least p+1p+1 vertices whose removal does not change γst\gamma_{st};
  3. every set of pp vertices is contained in some minimum strong dominating set of GSG-S for some set SS with Sp|S|\le p; and
  4. there exists a set of p+1p+1 vertices that is critical for maintaining γst\gamma_{st}.

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

No solutions have been posted yet.