Distinguishing numbers of finite 4-valent vertex-transitive graphs

DOI10.26493/1855-3974.1849.148MaRDI QIDQ4993953zbMATH OpenOpenAlexFDO

Authors Florian Lehner, Gabriel Verret

Publication date 11 June 2021

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.01522

zbMATH Keywords

distinguishing numbersymmetry breaking in graphvertex colouringvertex-transitive graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Group actions on combinatorial structures (05E18)

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$.

Recommendations

• Distinguishing graphs of maximum valence 3
• Vertex transitive graphs \(G\) with \(\chi_D (G)>\chi(G)\) and small automorphism group
• The distinguishing numbers of 4-regular quadrangulations on the torus
• Symmetry breaking in graphs
• On distinquishing numbers

Cites work

• Asymmetric graphs
• Distinguishing graphs of maximum valence 3
• Distinguishing labellings of group action on vector spaces and graphs
• Graph theory
• Improving upper bounds for the distinguishing index
• On cyclic edge-connectivity of transitive graphs
• On groups with no regular orbits on the set of subsets
• On symmetries of edge and vertex colourings of graphs
• On the vertex-stabiliser in arc-transitive digraphs
• Primitive Groups with no Regular Orbits on the Set of Subsets
• Symmetry breaking in graphs
• Tetravalent edge-transitive graphs of girth at most 4
• The distinguishing chromatic number
• The distinguishing number of the hypercube
• Zu einem Isomorphiesatz von H. Whitney für Graphen

Cited in

(7)

• On asymmetric colourings of claw-free graphs
• On the number of fixed points of automorphisms of vertex-transitive graphs
• Distinguishing graphs of maximum valence 3
• The distinguishing numbers of 4-regular quadrangulations on the torus
• Finite and infinite vertex-transitive cubic graphs and their distinguishing cost and density
• Vertex transitive graphs \(G\) with \(\chi_D (G)>\chi(G)\) and small automorphism group
• Distinguishing infinite graphs with bounded degrees

This page was built for publication: Distinguishing numbers of finite 4-valent vertex-transitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993953)