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

Institut für Diskrete Mathematik (5050)

Publikation: Beitrag in einer Fachzeitschrift › Artikel › Begutachtung

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.

Originalsprache	englisch
Seiten (von - bis)	173-187
Seitenumfang	15
Fachzeitschrift	Ars Mathematica Contemporanea
Jahrgang	19
Ausgabenummer	2
DOIs	https://doi.org/10.26493/1855-3974.1849.148
Publikationsstatus	Veröffentlicht - 1 Jan. 2020

ASJC Scopus subject areas

Theoretische Informatik
Diskrete Mathematik und Kombinatorik
Geometrie und Topologie
Algebra und Zahlentheorie

Fields of Expertise

Information, Communication & Computing

Zugriff auf Dokument

10.26493/1855-3974.1849.148Lizenz: CC BY 4.0

Andere Dateien und Links

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

FWF - Groups - Graphen und Gruppen
Lehner, F.
1/04/19 → 31/12/20
Projekt: Forschungsprojekt

Dieses zitieren

@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

ASJC Scopus subject areas

Fields of Expertise

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Projekte

FWF - Groups - Graphen und Gruppen

Dieses zitieren