← All problems

Piśniak's distinguishing-index conjecture for 2-connected graphs

9 years old · traced to

Let GG be a simple connected graph. Its distinguishing index D′(G)D'(G) is the least number of labels in an edge labeling preserved only by the identity automorphism. Write Δ(G)\Delta(G) for its maximum degree.

Piśniak's conjecture. If GG is a 22-connected graph, then

D′(G)≤1+⌈Δ(G)⌉.D'(G)\leq 1+\lceil \sqrt{\Delta(G)}\rceil.

This conjecture gives a substantially sharper upper bound for the distinguishing index of 2-connected graphs than the general maximum-degree bounds discussed in the paper.

References

Status

  • Solved: Wilfried Imrich, Rafał Kalinowski, Monika Pilśniak, and Mariusz Woźniak. The distinguishing index of connected graphs without pendant edges (Ars Mathematica Contemporanea, 2020) https://doi.org/10.26493/1855-3974.1852.4f7

Source: Saeid Alikhani and Samaneh Soltani, “An upper bound on the distinguishing index of graphs with minimum degree at least two”, arXiv:1702.03524 (2017).

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.