Distinguishing numbers of finite 4-valent vertex-transitive graphs

Florian Lehner, Gabriel Verret

Abstract


The distinguishing number of a graph G is the smallest k such that G admits a k-colouring for which the only colour-preserving automorphism of G is the identity. We determine the distinguishing number of finite 4-valent vertex-transitive graphs. We show that, apart from one infinite family and finitely many examples, they all have distinguishing number 2.


Keywords


Vertex colouring, symmetry breaking in graph, distinguishing number, vertex-transitive graphs

Full Text:

MANUSCRIPT


DOI: https://doi.org/10.26493/1855-3974.1849.148

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