The distinguishing number of Cartesian products of complete graphs

The distinguishing number D(G)D(G) of a graph GG is the least integer dd such that GG has a labeling with dd labels that is preserved only by a trivial automorphism. We prove that Cartesian products of relatively prime graphs whose sizes do not differ too much can be distinguished with a small number of colors. We determine the distinguishing number of the Cartesian product Kk□Kn for all kk and nn, either explicitly or by a short recursion. We also introduce column-invariant sets of vectors and prove a switching lemma that plays a key role in the proofs.