The distinguishing number of complete bipartite and crown graphs

Abstract

The distinguishing number of a permutation group $G\leqslant\Sym(Ω)$ is the minimum number of colours needed to colour $\hat{I}\text{c◯}$ 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 \textit{Keywords:} complete bipartite graph; crown graph; distinguishing number; symmetric group; alternating group