Alikhani–Soltani distinguishing-index conjecture for Mycielskians

Let GG be a connected graph with at least three vertices. Let Dist(G)\operatorname{Dist}'(G) denote the distinguishing index of GG, namely the least number of colors in a distinguishing edge coloring, and let Dist(μ(G))\operatorname{Dist}'(\mu(G)) denote the distinguishing index of its Mycielskian.

Alikhani–Soltani's conjecture. For all but a finite number of connected graphs GG with at least three vertices,

Dist(μ(G))Dist(G).\operatorname{Dist}'(\mu(G)) \leq \operatorname{Dist}'(G).

This conjecture predicts that the Mycielskian preserves the distinguishing index for all but finitely many connected graphs. The source gives an upper bound for twin-free graphs under additional hypotheses, but does not identify the finite exceptional family.

Sources & referencesView supporting material

Primary source

Debra Boutin, Sally Cockburn, Lauren Keough, Sarah Loeb, K. E. Perry and Puck Rombach, “Symmetry Parameters for Mycielskian Graphs”, arXiv:2103.05417 (2021).

Additional references

2 papers in this index state this conjecture (2020–2021). The statement above is taken from the most recent of them; the others are arXiv:2006.03739.

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.