Nordhaus-Gaddum type inequalities for the distinguishing index

Monika Pilsniak


The distinguishing index of~a~graph $G$, denoted by $D'(G)$, is the~least number of~colours in~an edge colouring of~$G$ not preserved by any nontrivial automorphism. This invariantĀ  is defined for any graph without $K_2$ as a~connected component and without two isolated vertices, and such a~graph is called admissible graph. We prove the~Nordhaus-Gaddum type relation: $$2\leq D'(G)+D'(\overline{G})\leq \Delta(G)+2$$ for every admissible connected graph of~order $|G|\geq 7$ such that $\overline{G}$ is also admissible.


symmetry breaking in~graphs, distinguishing index, Nordhaus-Gaddum type bounds

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications