Asymmetric edge-coloring of graphs with simple automorphism group

DOI10.1016/J.EJC.2021.103414arXiv2107.09452MaRDI QIDQ6373282

Andrzej Kisielewicz, Mariusz Grech

Publication date: 20 July 2021

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$.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Group actions on combinatorial structures (05E18)

This page was built for publication: Asymmetric edge-coloring of graphs with simple automorphism group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6373282)