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 条
[1]  
Albertson MO., 1996, The Electronic Journal of Combinatorics electronic only, V3, pR18, DOI DOI 10.37236/1242
[2]  
Andersen L. D., 1980, AEQUATIONES MATH, V20, P244
[3]   ASYMMETRIC TREES WITH 2 PRESCRIBED DEGREES [J].
BABAI, L .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1977, 29 (1-2) :193-200
[4]  
Babai L., 2015, PREPRINT
[5]  
Broere I, 2017, ARS MATH CONTEMP, V13, P15
[6]  
Broere I, 2015, ELECTRON J COMB, V22
[7]  
Dirac G., 1974, INDAG MATH, V77, P406
[8]  
Jech T., 2003, SET THEORY
[9]   Distinguishing graphs by edge-colourings [J].
Kalinowski, Rafal ;
Pilsniak, Monika .
EUROPEAN JOURNAL OF COMBINATORICS, 2015, 45 :124-131
[10]  
Kwany J., 2022, PREPRINT