Asymmetric edge-coloring of graphs with simple automorphism group

2021/07/20 by Mariusz Grech, Grech, Mariusz, Andrzej Kisielewicz +1
Computer Science · #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2107.09452

Abstract

The distinguishing index D'(Γ) of a graph Γ is the least number k such that Γ has an edge-coloring with k colors preserved only by the trivial automorphism. In this paper we prove that if the automorphism group of a finite graph Γ is simple, then its distinguishing index D'(Γ)=2.

Related

• A class of graphs with distinguishing index \bf D' ≤ 3
• Breaking graph symmetries by edge colourings
• The distinguishing index of graphs with infinite minimum degree
• The chromatic distinguishing index of certain graphs
• An upper bound on the distinguishing index of graphs with minimum degree at least two