The distinguishing-index conjecture for connected finite regular graphs

About 7 years old · traced to

Let GG be a connected, finite, regular graph, and let D′(G)D'(G) denote the least number of colours needed to colour the edges of GG so that the only colour-preserving automorphism is the identity. The regular-graph distinguishing-index conjecture. Then D′(G)≤2D'(G)\leq 2, unless GG is either KnK_n for n≤5n\leq 5, Kn,nK_{n,n} for n≤3n\leq 3, or C5C_5. This would improve the general bound for distinguishing indices in the regular case; the paper proves the weaker general estimate but presents this sharper assertion as conjectural.

References

Primary source

Florian Lehner, Monika Pilśniak and Marcin Stawiski, “A bound for the distinguishing index of regular graphs”, arXiv:1911.11105 (2020).

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.