The distinguishing number of complete bipartite and crown graphs
Lei Chen, Alice Devillers, Luke Morgan, Friedrich Rober · 2026
Read The distinguishing number of complete bipartite and crown graphs by Lei Chen, Alice Devillers, Luke Morgan, Friedrich Rober (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-15913.txt.
Introduction
Lei Chen, Alice Devillers, Luke Morgan, and Friedrich Rober count colorings that break symmetry in a 2026 arXiv paper. The distinguishing number of a permutation group is defined plainly. It is the fewest colors needed to color the underlying set. The coloring must leave the identity as the only color-preserving group element. Any nontrivial symmetry must disturb some color. The authors compute this number for two graph families.
Complete bipartite graphs and crown graphs are their targets. Both are highly symmetric, so breaking all symmetry with few colors is a puzzle. The fewer the colors, the stronger the result. Distinguishing numbers connect group theory with graph coloring. They also model real tasks, like tagging items so that only the true arrangement looks unchanged.
Catalog record
| CREATOR | Lei Chen, Alice Devillers, Luke Morgan, Friedrich Rober |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-15913
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The distinguishing number of complete bipartite and crown graphs Thanks: Acknowledgements : We thank the Centre for the Mathematics of Symmetry and Computation at The University of Western Australia for organising the annual research retreat of 2023 at which this research project began. The research of Alice Devillers and of Luke Morgan was supported by the Australian Research Council via the Discovery Project grants DP200100080 and DP230101268, respectively. The research of Lei Chen is supported by the Deutsch Forschungsgemeinschaft (DFG), German Research Foundation, Project-ID: 491392403-TRR 358. The research of Friedrich Rober is supported by the Deutscher Akademischer Austauschdienst (DAAD), German Academic Exchange Service, Project-ID: 57647563. Lei Chen, Alice Devillers, Luke Morgan, Friedrich Rober Abstract . The distinguishing number of a permutation group G ⩽ Sym ( Ω ) G\leqslant\Sym(\Omega) is the minimum number of colours needed to colour Ω \Omega in such a way that the only colour preserving element of G 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 K_{n,n} and the crown graphs K n , n − n K 2 K_{n,n}-nK_{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 ) \Alt(n) or Sym ( n ) \Sym(n) . We show that, if G G is a ‘large’ group of automorphisms of K n , n K_{n,n} , then n − 1 ⩽ D ( G ) ⩽ n + 1 n-1\leqslant D(G)\leqslant n+1 . Similarly, if G G is a ‘large’ group of automorphisms of a crown graph, then ⌈ n − 1 ⌉ ⩽ D ( G ) ⩽ ⌊ n ⌋ + 1 \lceil\sqrt{n-1}\rceil\leqslant D(G)\leqslant\lfloor\sqrt{n}\rfloor+1 . Keywords: complete bipartite graph; crown graph; distinguishing number; symmetric group; alternating group 1. Introduction A vertex colouring of a graph \Gamma is a labelling of the vertices of \Gamma . The distinguishing number D(\Gamma) of a graph \Gamma is the smallest integer k such that \Gamma has a colouring with k labels that is only preserved by the identity. The investigation of distinguishing number has its roots in the following problem: given a ring of seemingly identical keys, how many colours are needed to colour the keys so that the position of each key on the ring is distinguishable? In mathematical terms, this becomes a question about the distinguishing number of cycles. The distinguishing number was generalised to the context of group actions by Tymoczko [ 10 ] : for a group G acting on a set \Omega , the distinguishing number D(G) of G is the smallest integer k such that there exists a partition \Pi=\{P_{1},\ldots,P_{k}\} of \Omega with G_{(\Pi)}=\bigcap_{i=1}^{k}G_{P_{i}}=1 . Note that the two definitions of distinguishing numbers D(\Gamma) and D(G) for a graph \Gamma and a group G acting on \Gamma coincide when G=\Aut(\Gamma) . The distinguishing number has been studied for many families of graphs, such as complete bipartite graphs, cycles, paths and trees (see [ 3 ] and citations thereof). Many group actions have been studied, such as the imprimitive actions [ 2 ] and the action of the general linear group on vectors [ 6 ] . For primitive groups, Cameron, Neumann and Saxl [ 1 ] proved that all but finitely many groups have distinguishing number two. Groups with certain restrictions on stabilisers or motion were considered by Conder and Tucker [ 4 ] who generalised the ‘motion lemma’ of Russell and Sundaram [ 9 ] to show that many graphs and maps have distinguishing number two. In fact, Conder and Tucker state that “having distinguishing number two is a generic property”. From the point of view of global symmetry, the distinguishing number of non-bipartite 2 -arc-transitive graphs was considered in [ 5 ] where it was shown that (aside from complete graphs) all but finitely many graphs have distinguishing number two. As a continuation of that project we focus on families of graphs that have large automorphism groups and unbounded distinguishing number. In this paper, we focus on two important families of bipartite graphs, the complete bipartite graphs K_{n,n} which have automorphism group \Sym(n)\wr\Sym(2) and the so-called ‘crown graphs’ K_{n,n}-nK_{2} (graphs obtained by deleting a perfect matching from a complete bipartite graph) which have automorphism group \Sym(n)\times\Sym(2) . A closely related concept to distinguishing number is that of the distinguishing chromatic number \chi_{D}(\Gamma) of \Gamma , defined to be the smallest integer k such that there exists a vertex-colouring of \Gamma with k colours that is both distinguishing and proper (adjacent vertices must have different colours). It was previously shown that D(K_{n,n})=n+1 [ 3 , Theorem 2.4] and \chi_{D}(K_{n,n})=2n [ 3 , Theorem 2.3] , and in [ 7 ] it was proved that \chi_{D}(K_{n,n}-nK_{2})=\lceil 2\sqrt{n}\rceil . We complete the results on the distinguishing number of the crown graphs by proving: Theorem 1.1 . Let \Gamma=K_{n,n}-nK_{2} . Then D(\Gamma)=\lfloor\sqrt{n}\rfloor+1 In comparison with the results in [ 7 , Theorem 1] , we observe that \chi_{D}(\Gamma)\approx 2D(\Gamma) for \Gamma=K_{n,n}-nK_{2} , which presents a similar pattern to that of \Gamma=K_{n,n} . The above theorem is a consequence of a more detailed study on the value of D(G) where G\leqslant\Aut(\Gamma) and \Gamma=K_{n,n} or K_{n,n}-nK_{2} . The groups G we consider can be viewed as the ‘large’ subgroups of \Aut(\Gamma) . In the theorem below, we denote by G^{+} the unique index two subgroup of G that preserves the bipartition of \Gamma . Theorem 1.2 . Let \Gamma=K_{n,n} or K_{n,n}-nK_{2} and let G\leqslant\Aut(\Gamma) be such that G^{+} appears in Table 1 . Then the value of D(G) is given in the corresponding column of Table 1 . In an investigation into the distinguishing number of 2 -arc-transitive graphs [ CDMR ] , the groups and graphs considered in Theorem 1.2 have turned out to be rather special. Our interest in them is justified by the following classification theorem. We require one further definition. Let \Gamma be a bipartite graph with vertex-transitive group of automorphisms G\leqslant\Aut(\Gamma) , and let \Delta and \Delta^{\prime} denote the two parts of V\Gamma . Letting n be the size of \Delta (which equals the size of \Delta^{\prime} ), G^{+} induces a permutation group on \Delta , denoted by (G^{+})^{\Delta} , which may be viewed as a subgroup of \Sym(n) . Theorem 1.3 . Let \Gamma be a connected bipartite G -vertex transitive and G -edge transitive graph where G\leqslant\Aut(\Gamma) . Let \Delta denote one of the two parts of \Gamma , of size n say, and suppose that \Alt(n)\leqslant(G^{+})^{\Delta}\leqslant\Sym(n) . Then \Gamma=K_{n,n} or K_{n,n}-nK_{2} and, up to conjugation in \Sym(n)\times\Sym(n) , G^{+} appears in Table 1 . \Gamma G^{+} D(G) K_{n,n} \Alt(n)\times\Alt(n) n-1 K_{n,n} \langle\Alt(n)\times\Alt(n),((1,2),(1,2))\rangle n K_{n,n} \Sym(n)\times\Sym(n) n+1 K_{n,n}-nK_{2} \Diag(\Sym(n)\times\Sym(n)) \lfloor\sqrt{n}\rfloor+1 K_{n,n}-nK_{2} \Diag(\Alt(n)\times\Alt(n)) \lceil\sqrt{n-1}\rceil K_{6,6} \Diag_{\varphi}(H\times H) 3 K_{4,4} \langle V_{4}\times V_{4},\Diag(H\times H)\rangle 3 Table 1. Values of D(G) where G\leqslant\Aut(\Gamma) , H=\Alt(n) or \Sym(n) and \varphi is a certain outer automorphism of \Sym(6) specified in Proposition 2.2 . We remark that the subgroup G^{+}