A bound for the distinguishing index of regular graphs

被引：6

作者：

Lehner, Florian ^{[1
]}

Pilsniak, Monika ^{[2
]}

Stawiski, Marcin ^{[2
]}

机构：

[1] Graz Univ Technol, Inst Discrete Math, Steyrergasse 30, A-8010 Graz, Austria

[2] AGH Univ Sci & Technol, Dept Discrete Math, Al Mickiewicza 30, PL-30059 Krakow, Poland

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2020年 / 89卷

基金：

奥地利科学基金会;

关键词：

CARTESIAN PRODUCTS; FINITE;

D O I：

10.1016/j.ejc.2020.103145

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An edge-colouring of a graph is distinguishing if the only auto-morphism 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 kappa such that every connected kappa-regular graph has a distinguishing edge-colouring with two colours. (C) 2020 Elsevier Ltd. All rights reserved.

引用

页数：9

共 18 条

[1]

Albertson MO., 1996, The Electronic Journal of Combinatorics electronic only, V3, pR18, DOI DOI 10.37236/1242

[2] ASYMMETRIC TREES WITH 2 PRESCRIBED DEGREES [J].