Distinguishing threshold of graphs

Mohammad Hadi Shekarriz, Bahman Ahmadi, Seyed Alireza Talebpoor Shirazi Fard, Mohammad Hasan Shirdareh Haghighi

Published 2021-07-30Version 1

A vertex coloring of a graph $G$ is called distinguishing if no non-identity automorphisms of $G$ can preserve it. The distinguishing number of $G$, denoted by $D(G)$, is the minimum number of colors required for such coloring. The distinguishing threshold of $G$, denoted by $\theta(G)$, is the minimum number $k$ of colors such that every $k$-coloring of $G$ is distinguishing. In this paper, we study $\theta(G)$, find its relation to the cycle structure of the automorphism group and prove that $\theta(G)=2$ if and only if $G$ is isomorphic to $K_2$ or $\overline{K_2}$. Moreover, we study graphs that have the distinguishing threshold equal to 3 or more and prove that $\theta(G)=D(G)$ if and only if $G$ is asymmetric, $K_n$ or $\overline{K_n}$. Finally, we consider Johnson scheme graphs for their distinguishing number and threshold concludes the paper.