A bound for the distinguishing index of regular graphs

Florian Lehner; Monika Pilsniak; Marcin Stawiski

doi:10.1016/j.ejc.2020.103145

A bound for the distinguishing index of regular graphs

Florian Lehner^*, Monika Pilsniak, Marcin Stawiski

^*Corresponding author for this work

Institute of Discrete Mathematics (5050)

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

Abstract

An edge-colouring of a graph is distinguishing if the only automorphism that preserves the colouring is the identity. It has been conjectured that all but finitely many connected, finite, regular graphs admit a distinguishing edge-colouring with two colours. We show that all such graphs except K ₂ admit a distinguishing edge-colouring with three colours. This result also extends to infinite, locally finite graphs. Furthermore, we are able to show that there are arbitrary large infinite cardinals κ such that every connected κ-regular graph has a distinguishing edge-colouring with two colours.

Original language	English
Article number	103145
Number of pages	9
Journal	European Journal of Combinatorics
Volume	89
DOIs	https://doi.org/10.1016/j.ejc.2020.103145
Publication status	Published - Oct 2020

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1016/j.ejc.2020.103145

Cite this

@article{12d89cbde92046a480c0c16015163e7f,

title = "A bound for the distinguishing index of regular graphs",

abstract = "An edge-colouring of a graph is distinguishing if the only automorphism that preserves the colouring is the identity. It has been conjectured that all but finitely many connected, finite, regular graphs admit a distinguishing edge-colouring with two colours. We show that all such graphs except K 2 admit a distinguishing edge-colouring with three colours. This result also extends to infinite, locally finite graphs. Furthermore, we are able to show that there are arbitrary large infinite cardinals κ such that every connected κ-regular graph has a distinguishing edge-colouring with two colours. ",

author = "Florian Lehner and Monika Pilsniak and Marcin Stawiski",

year = "2020",

month = oct,

doi = "10.1016/j.ejc.2020.103145",

language = "English",

volume = "89",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A bound for the distinguishing index of regular graphs

AU - Lehner, Florian

AU - Pilsniak, Monika

AU - Stawiski, Marcin

PY - 2020/10

Y1 - 2020/10

N2 - An edge-colouring of a graph is distinguishing if the only automorphism that preserves the colouring is the identity. It has been conjectured that all but finitely many connected, finite, regular graphs admit a distinguishing edge-colouring with two colours. We show that all such graphs except K 2 admit a distinguishing edge-colouring with three colours. This result also extends to infinite, locally finite graphs. Furthermore, we are able to show that there are arbitrary large infinite cardinals κ such that every connected κ-regular graph has a distinguishing edge-colouring with two colours.

AB - An edge-colouring of a graph is distinguishing if the only automorphism that preserves the colouring is the identity. It has been conjectured that all but finitely many connected, finite, regular graphs admit a distinguishing edge-colouring with two colours. We show that all such graphs except K 2 admit a distinguishing edge-colouring with three colours. This result also extends to infinite, locally finite graphs. Furthermore, we are able to show that there are arbitrary large infinite cardinals κ such that every connected κ-regular graph has a distinguishing edge-colouring with two colours.

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

U2 - 10.1016/j.ejc.2020.103145

DO - 10.1016/j.ejc.2020.103145

M3 - Article

SN - 0195-6698

VL - 89

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103145

ER -

A bound for the distinguishing index of regular graphs

Abstract

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Fingerprint

FWF - Groups - Graphs and Groups

Corrigendum to “A bound for the distinguishing index of regular graphs”: “A bound for the distinguishing index of regular graphs” (European Journal of Combinatorics (2020) 89, (103145), (S0195669820300664), (10.1016/j.ejc.2020.103145))

Cite this

A bound for the distinguishing index of regular graphs

Abstract

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Fingerprint

Projects

FWF - Groups - Graphs and Groups

Research output

Corrigendum to “A bound for the distinguishing index of regular graphs”: “A bound for the distinguishing index of regular graphs” (European Journal of Combinatorics (2020) 89, (103145), (S0195669820300664), (10.1016/j.ejc.2020.103145))

Cite this