Distinguishing numbers of finite 4-valent vertex-transitive graphs
Keywords:Vertex colouring, symmetry breaking in graph, distinguishing number, vertex-transitive graphs
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.
Articles in this journal are published under Creative Commons Attribution 4.0 International License