The distinguishing stability bound for simple connected graphs

About 10 years old · traced to

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.

References

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.