The distinguishing index of graphs with infinite minimum degree

Abstract

The distinguishing index $D^{\prime }(G)$ of a graph $G$ is the least number of colors necessary to obtain an edge coloring of $G$ that is preserved only by the trivial automorphism. We show that if $G$ is a connected $\alpha$-regular graph for some infinite cardinal $\alpha$ then $D^{\prime }(G)\le 2$, proving a conjecture of Lehner, Pilśniak, and Stawiski. We also show that if $G$ is a graph with infinite minimum degree and at most $2^{\alpha }$ vertices of degree $\alpha$ for every infinite cardinal $\alpha$, then $D^{\prime }(G)\le 3$. In particular, $D^{\prime }(G)\le 3$ if $G$ has infinite minimum degree and order at most $2^{{\aleph }_0}$.