The distinguishing stability bound for simple connected graphs

Let GG be a simple connected graph. Write D(G)D(G) for its distinguishing number and stD(G)st_D(G) for its distinguishing stability, namely the least number of vertices whose deletion changes the distinguishing number.

Distinguishing stability conjecture.

stD(G)D(G)+1.st_D(G)\leqslant D(G)+1.

The authors state this bound because it holds for the examples they have considered, but report that attempts to prove it have failed. Its general validity remains open.

Sources & referencesView supporting material

Primary source

Saeid Alikhani and Samaneh Soltani, “Stabilizing on the distinguishing number of a graph”, arXiv:1609.07345 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.