Home > Timetable > Contribution details

Contribution

The Distinguishing Index of $2$-connected Graphs

Speakers

  • Rafal KALINOWSKI

Primary authors

Co-authors

Content

The distinguishing index $D'(G)$ of a graph $G$ is the least number of colours of an edge colouring that is not preserved by any non-trivial automorphism.

The following result was proved by Pil\'sniak in [1].

Theorem. If $G$ is a connected graph, then $(1)$ $D'(G)=\Delta(G)+1$ iff $G$ is a cycle of length less than $6$, $(2)$ $D'(G)=\Delta(G)$ iff $G$ is a symmetric or a bisymmetric tree, a cycle of length at least $6$, or $K_4$ or $K_{3,3}$, $(3)$ $D'(G)\leq\Delta(G)-1$ otherwise.

In the same paper, Pil\'sniak formulated the following conjecture.

Conjecture. If a graph $G$ is $2$-connected, then $$D'(G)\leq \left\lceil\sqrt{\Delta(G)}\right\rceil+1.$$

In this talk, we prove this conjecture in a bit stronger form, and show some of its consequences.

Reference:

[1] M. Pil\'sniak, Improving upper bounds for the distinguishing index, Ars Math. Contemp. 13 (2017) 259--274.