The Distinguishing Index of $2$-connected Graphs

Not scheduled
UP FHS (Koper)



Titov trg 5,Koper


Rafal Kalinowski (AGH University)


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.

Primary author

Rafal Kalinowski (AGH University)


Mariusz Wozniak (AGH University) Monika Pilsniak (AGH University, Krakow, Poland) Wilfried Imrich (Montanuniversitaet Leoben)

Presentation Materials

There are no materials yet.