Asymmetric edge-coloring of graphs with simple automorphism group

Abstract

The distinguishing index $D^{\prime }(\Gamma )$ of a graph $\Gamma$ is the least number $k$ such that $\Gamma$ 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 $\Gamma$ is simple, then its distinguishing index $D^{\prime }(\Gamma )=2$.