The distinguishing number of complete bipartite and crown graphs

The distinguishing number of a permutation group $G⩽\text{Sym}(\mathrm{\Omega })$ is the minimum number of colours needed to colour $\mathrm{\Omega }$ in such a way that the only colour preserving element of $G$ is the identity. The distinguishing number of a graph is the distinguishing number of its automorphism group (as a permutation group on vertices). We determine the distinguishing number of the complete bipartite graphs $K_{n,n}$ and the crown graphs $K_{n,n}-n{K}_2$, as well as the distinguishing number of some large' subgroups of their automorphism groups, that is, the subgroups that are vertex- and edge-transitive and such that the induced action on each bipart is $\Alt(n)$ or $\Sym(n)$. We show that, if $G$ is a large’ group of automorphisms of $K_{n,n}$, then $n-1⩽D(G)⩽n+1$. Similarly, if $G$ is a `large’ group of automorphisms of a crown graph, then $\lceil \sqrt{n-1}\rceil ⩽D(G)⩽\lfloor \sqrt{n}\rfloor +1$. \smallskip $\mathit{\text{Keywords:}}$ complete bipartite graph; crown graph; distinguishing number; symmetric group; alternating group