Distinguishing numbers of finite 4-valent vertex-transitive graphs - Lehner, Florian (Ars mathematica contemporanea, 2020)
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: barvanje točk; distinguishing number; razlikovalno število; symmetry breaking in graph; vertex colouring; vertex-transitive graphs; vozliščno tranzitivni grafi; zlom simetrije v grafu