Distinguishing threshold of graphs
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 a coloring, and the distinguishing threshold of G, denoted by θ(G), is the minimum number k such that every k-coloring of G is distinguishing. As an alternative definition, θ(G) is one more than the maximum number of cycles in the cycle decomposition of automorphisms of G. In this paper, we characterize θ(G) when G is disconnected. Afterwards, we prove that, although for every positive integer k=2 there are infinitely many graphs whose distinguishing thresholds are equal to k, we have θ(G)=2 if and only if ∣V(G)∣=2. Moreover, we show that if θ(G)=3, then either G is isomorphic to one of the four graphs on~3 vertices or it is of order 2p, where p=3,5 is a prime number. Furthermore, we prove that θ(G)=D(G) if and only if G is asymmetric, Kn or Kn. Finally, we consider all generalized Johnson graphs, J(n,k,i), which are the graphs on all k-subsets of {1,…,n} where two vertices A and B are adjacent if ∣A∩B∣=k−i. After studying their automorphism groups and distinguishing numbers, we calculate their distinguishing thresholds as θ(J(n,k,i))=(kn)−(k−1n−2)+1, unless k=2n and i∈{2k,k} in which case we have θ(J(n,k,i))=(kn).
