Graphs with small distinguishing index

Not scheduled
UP FHS (Koper)



Titov trg 5,Koper


Monika Pilsniak (AGH University, Krakow, Poland)


\titleoftalk{Graphs with small distinguishing index} \speaker{{Monika} {Pil\'sniak}} \university{Department of~Discrete Mathematics\\AGH University, Krakow, Poland} \email{} \ \begin{abstract}The distinguishing index of~a graph $G$, denoted by $D'(G)$, is the~least number of~colours in a general edge colouring of~$G$ not preserved by any non-trivial automorphism. The definition of~$D'(G)$ was introduced in 2015 in [3] as an analogue of the distinguishing number defined by Albertson and Collins for vertex colouring, the concept of which spawned more than a hundred of papers. For connected graphs in general, we showed in [3] that $D'(G)\leq \Delta(G)$ unless $G$ is $C_3$, $C_4$ or $C_5$. It was proved in [5], that the equality $D'(G)= \Delta(G)$ holds only for cycles of~length at least 6, for $K_4$, $K_{3,3}$ and for all symmetric and bisymmetric trees, i.e., $D'(G)< \Delta(G)$ for all other connected graphs. %\vspace{.3cm} Interestingly, there are some wide classes of graphs with the distinguishing index bounded by a small constant, e.g., traceable graphs, planar graphs, claw-free graphs [5], Cartesian powers [2], and the Cartesian product of denumerable graphs [1]. \vspace{0.3cm} An analogous concept was also investigated for proper total colourings in [4]. We proved in particular that if $G$ is a~connected graph such that its total chromatic index $\chi''(G)$ satisfies $\chi''(G)\geq\Delta(G) +2$, then the total distinguishing chromatic index equals $\chi''(G)$. \vspace{25pt} \setlength{\parindent}{0cm}{\textbf{References:} % Journal paper [1] I. Broere, M. Pil\'sniak, {\it The distinguishing index of the Cartesian product of countable graphs}, Ars Math. Contemp. 13 (2017) 15--21. [2] A. Gorzkowska, R. Kalinowski, M. Pil\'sniak, {\it The distinguishing index of the Cartesian product of graphs}, Ars Math. Contemp. 12 (2017) 77–-87. [3] R.~Kalinowski and M.~Pil\'sniak, {\it Distinguishing graphs by edge colourings}, {European J. Combin.} {45} (2015) 124--131. [4] R. Kalinowski, M. Pil\'sniak, M. Wo\'zniak, {\it Distinguishing graphs by total colourings}, {Ars Math. Contemp.}, (2016) 11:79–-89. [5] M.~Pil\'sniak, {\it Improving Upper Bounds for the~Distinguishing Index}, {Ars Math. Contemp.} 13 (2017) 259--274. } %%% ***************** \end{abstract}

Primary author

Monika Pilsniak (AGH University, Krakow, Poland)

Presentation Materials

There are no materials yet.