The distinguishing index of graphs with infinite minimum degree

被引:0
作者
Stawiski, Marcin [1 ,3 ]
Wilson, Trevor M. [2 ]
机构
[1] AGH Univ Sci & Technol, Fac Appl Math, Krakow, Poland
[2] Miami Univ, Dept Math, Oxford, OH USA
[3] AGH Univ Sci & Technol, Fac Appl Math, Al Mickiewicza 30, PL-30059 Krakow, Poland
关键词
distinguishing colorings; distinguishing index; infinite graphs; regular graphs; EDGE; SYMMETRIES;
D O I
10.1002/jgt.23013
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The distinguishing index D & PRIME;(G) $D<^>{\prime} (G)$ of a graph G $G$ is the least number of colors necessary to obtain an edge coloring of G $G$ that is preserved only by the trivial automorphism. We show that if G $G$ is a connected & alpha; $\alpha $-regular graph for some infinite cardinal & alpha; $\alpha $ then D & PRIME;(G)& LE;2 $D<^>{\prime} (G)\le 2$, proving a conjecture of Lehner, Pilsniak, and Stawiski. We also show that if G $G$ is a graph with infinite minimum degree and at most 2 & alpha; ${2}<^>{\alpha }$ vertices of degree & alpha; $\alpha $ for every infinite cardinal & alpha; $\alpha $, then D & PRIME;(G)& LE;3 $D<^>{\prime} (G)\le 3$. In particular, D & PRIME;(G)& LE;3 $D<^>{\prime} (G)\le 3$ if G $G$ has infinite minimum degree and order at most 2 & ALEPH;0 ${2}<^>{{\aleph }_{0}}$.
引用
收藏
页码:61 / 67
页数:7
相关论文
共 13 条
[11]   A bound for the distinguishing index of regular graphs [J].
Lehner, Florian ;
Pilsniak, Monika ;
Stawiski, Marcin .
EUROPEAN JOURNAL OF COMBINATORICS, 2020, 89
[12]   On symmetries of edge and vertex colourings of graphs [J].
Lehner, Florian ;
Smith, Simon M. .
DISCRETE MATHEMATICS, 2020, 343 (09)
[13]   Breaking graph symmetries by edge colourings [J].
Lehner, Florian .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 127 :205-214