The optimal general upper bound for the distinguishing index of infinite graphs. Issue 4 (16th August 2019)

• Record Type: Journal Article
• Authors: Pilśniak, Monika; Stawiski, Marcin
• Is Part Of: Journal of graph theory. Volume 93:Issue 4(2020)
• Page Start: 463
• Page End: 469
• Publication Date: 2019-08-16
• Subjects: automorphism -- distinguishing index -- edge‐coloring -- infinite graph -- symmetry breaking in graph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22496
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: The distinguishing index D ′ ( G ) of a graph G is the least cardinal number d such that G has an edge‐coloring with d colors, which is preserved only by the trivial automorphism. We prove a general upper bound D ′ ( G ) ≤ Δ − 1 for any connected infinite graph G with finite maximum degree Δ ≥ 3 . This is in contrast with finite graphs since for every Δ ≥ 3 there exist infinitely many connected, finite graphs G with D ′ ( G ) = Δ . We also give examples showing that this bound is sharp for any maximum degree Δ .