Distinguishing numbers of finite 4-valent vertex-transitive graphs
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
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