Distinguishing threshold of graphs.

A vertex coloring of a graph G $G$ is called distinguishing if no nonidentity automorphisms of G $G$ can preserve it. The distinguishing number of G $G$, denoted by D(G) $D(G)$, is the minimum number of colors required for such a coloring, and the distinguishing threshold of G $G$, denoted by θ(G) $\theta (G)$, is the minimum number k $k$ such that every k $k$‐coloring of G $G$ is distinguishing. As an alternative definition, θ(G) $\theta (G)$ is one more than the maximum number of cycles in the cycle decomposition of automorphisms of G $G$. In this paper, we characterize θ(G) $\theta (G)$ when G $G$ is disconnected. Afterwards, we prove that, although for every positive integer k≠2 $k\ne 2$ there are infinitely many graphs whose distinguishing thresholds are equal to k $k$, we have θ(G)=2 $\theta (G)=2$ if and only if ∣V(G)∣=2 $| V(G)| =2$. Moreover, we show that if θ(G)=3 $\theta (G)=3$, then either G $G$ is isomorphic to one of the four graphs on three vertices or it is of order 2p $2p$, where p≠3,5 $p\ne 3,5$ is a prime number. Furthermore, we prove that θ(G)=D(G) $\theta (G)=D(G)$ if and only if G $G$ is asymmetric, Kn ${K}_{n}$ or Kn¯ $\bar{{K}_{n}}$. Finally, we consider all generalized Johnson graphs, J(n,k,i) $J(n,k,i)$, which are the graphs on all k $k$‐subsets of {1,...,n} $\{1,\ldots ,n\}$ where two vertices A $A$ and B $B$ are adjacent if ∣A∩B∣=k−i $| A\cap B| =k-i$. After studying their automorphism groups and distinguishing numbers, we calculate their distinguishing thresholds as θ(J(n,k,i))=nk−n−2k−1+1 $\theta (J(n,k,i))=\left(\genfrac{}{}{0ex}{}{n}{k}\right)-\left(\genfrac{}{}{0ex}{}{n-2}{k-1}\right)+1$, unless k=n2 $k=\frac{n}{2}$ and i∈{k2,k} $i\in \{\frac{k}{2},k\}$ in which case we have θ(J(n,k,i))=nk $\theta (J(n,k,i))=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. [ABSTRACT FROM AUTHOR]