Using determining sets to distinguish Kneser graphs (Q870080)

Summary: This work introduces the technique of using a carefully chosen determining set to prove the existence of a distinguishing labeling using few labels. A graph \(G\) is said to be \(d\)-distinguishable if there is a labeling of the vertex set using \(1, \dots, d\) so that no nontrivial automorphism of \(G\) preserves the labels. A set of vertices \(S\subseteq V(G)\) is a determining set for \(G\) if every automorphism of \(G\) is uniquely determined by its action on \(S\). We prove that a graph is \(d\)-distinguishable if and only if it has a determining set that can be \((d-1)\)-distinguished. We use this to prove that every Kneser graph \(K_{n:k}\) with \(n\geq6\) and \(k\geq2\) is 2-distinguishable.