Number of colors needed to break symmetries of a graph by an arbitrary edge coloring

Abstract

A coloring is distinguishing (or symmetry breaking) if no non-identity automorphism preserves it. The distinguishing threshold of a graph $G$, denoted by $\theta (G)$, is the minimum number of colors $k$ so that every $k$-coloring of $G$ is distinguishing. We generalize this concept to edge-coloring by defining an alternative index ${\theta }^{\prime }(G)$. We consider ${\theta }^{\prime }$ for some families of graphs and find its connection with edge-cycles of the automorphism group. Then we show that ${\theta }^{\prime }(G)=2$ if and only if $G\simeq K_{1,2}$ and ${\theta }^{\prime }(G)=3$ if and only if $G\simeq P_4,K_{1,3}$ or $K_3$. Moreover, we prove some auxiliary results for graphs whose distinguishing threshold is 3 and show that although there are infinitely many such graphs, but they are not line graphs. Finally, we compute ${\theta }^{\prime }(G)$ when $G$ is the Cartesian product of simple prime graphs.

15 pages

References in corpus (4)

• Number of Distinguishing Colorings and Partitions
• Distinguishing threshold of graphs
• The Cost of Edge-distinguishing of the Cartesian Product of Connected Graphs
• Distinguishing threshold for some graph operations