Distinguishing numbers of finite 4-valent vertex-transitive graphs

Florian Lehner; Gabriel Verret

doi:10.26493/1855-3974.1849.148

Distinguishing numbers of finite 4-valent vertex-transitive graphs

Florian Lehner, Gabriel Verret

Institute of Discrete Mathematics (5050)

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	173-187
Number of pages	15
Journal	Ars Mathematica Contemporanea
Volume	19
Issue number	2
DOIs	https://doi.org/10.26493/1855-3974.1849.148
Publication status	Published - 1 Jan 2020

Keywords

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

Access to Document

10.26493/1855-3974.1849.148Licence: CC BY 4.0

Cite this

@article{c6892ac2183b49b19204880b4b7095ab,

title = "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 = "Distinguishing number, Symmetry breaking in graph, Vertex colouring, Vertex-transitive graphs",

author = "Florian Lehner and Gabriel Verret",

year = "2020",

month = jan,

day = "1",

doi = "10.26493/1855-3974.1849.148",

language = "English",

volume = "19",

pages = "173--187",

journal = "Ars Mathematica Contemporanea",

issn = "1855-3966",

publisher = "DMFA Slovenije",

number = "2",

}

TY - JOUR

T1 - Distinguishing numbers of finite 4-valent vertex-transitive graphs

AU - Lehner, Florian

AU - Verret, Gabriel

PY - 2020/1/1

Y1 - 2020/1/1

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

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

KW - Distinguishing number

KW - Symmetry breaking in graph

KW - Vertex colouring

KW - Vertex-transitive graphs

UR - http://www.scopus.com/inward/record.url?scp=85097206262&partnerID=8YFLogxK

U2 - 10.26493/1855-3974.1849.148

DO - 10.26493/1855-3974.1849.148

M3 - Article

SN - 1855-3966

VL - 19

SP - 173

EP - 187

JO - Ars Mathematica Contemporanea

JF - Ars Mathematica Contemporanea

IS - 2

ER -

Distinguishing numbers of finite 4-valent vertex-transitive graphs

Abstract

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Fingerprint

FWF - Groups - Graphs and Groups

Cite this

Distinguishing numbers of finite 4-valent vertex-transitive graphs

Abstract

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Fingerprint

Projects

FWF - Groups - Graphs and Groups

Cite this