Alikhani–Soltani distinguishing-index conjecture for Mycielskians

About 6 years old · traced to

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.

References

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.