Distinguishing numbers of finite 4-valent vertex-transitive graphs

Florian Lehner, Gabriel Verret

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)173-187
Number of pages15
JournalArs Mathematica Contemporanea
Issue number2
Publication statusPublished - 1 Jan 2020


  • Distinguishing number
  • Symmetry breaking in graph
  • Vertex colouring
  • Vertex-transitive graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Geometry and Topology
  • Algebra and Number Theory

Fields of Expertise

  • Information, Communication & Computing


Dive into the research topics of 'Distinguishing numbers of finite 4-valent vertex-transitive graphs'. Together they form a unique fingerprint.

Cite this