Nordhaus-Gaddum type inequalities for the distinguishing index
Monika Pilśniak · Ars Mathematica Contemporanea · 2021
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 K2 as a connected component and without two isolated vertices, and such a graph is called admissible. We prove the Nordhaus-Gaddum type relation:2 ≤ D′(G) + D′(Ḡ) ≤ Δ(G) + 2for every admissible connected graph G of order |G| ≥ 7 such that Ḡ is also admissible.