The distinguishing index of connected graphs without pendant edges

Wilfried Imrich, Rafał Kalinowski, Monika Pilśniak, Mariusz Woźniak

Abstract


We consider edge colourings, not necessarily proper. The distinguishing index D′(G) of a graph G is the least number of colours in an edge colouring that is preserved only by the identity automorphism. It is known that D′(G) ≤ Δ for every countable, connected graph G with finite maximum degree Δ except for three small cycles. We prove that $D'(G)\leq \lceil\sqrt{\Delta}\rceil+1$ if additionally G does not have pendant edges.


Keywords


Symmetry breaking in graphs, distinguishing index, Nordhaus-Gaddum type inequalities, Lovász Conjecture

Full Text:

MANUSCRIPT


DOI: https://doi.org/10.26493/1855-3974.1852.4f7

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