Distinguishing labellings of group action on vector spaces and graphs (Q2509274): Difference between revisions

Suppose \(\Gamma\) is a group acting on a set \(X\). A \(k\)-labelling of \(X\) is a mapping \(c:X\to\{1,2,\dots,k\}\). A labelling \(c\) of \(X\) is distinguishing (with respect to the action of \(\Gamma\)) if for any \(g\in\Gamma\setminus\{\text{id}_x\}\), there exists an element \(x\in X\) such that \(c(x)\neq c(g(x))\). The distinguishing number, \(D_{\Gamma}(X)\), of the action of \(\Gamma\) on \(X\) is the minimum number \(k\) for which there is a \(k\)-labelling which is distinguishing. The authors study the distinguishing numbers of the general linear group \(\text{GL}_n(K)\) over a field \(K\) acting on the vector space \(K^n\) and of the the automorphism group \(\text{Aut}(G)\) of a graph \(G\) acting on \(V(G)\). The latter, denoted \(D(G)\), is referred to as the distinguishing number of the graph \(G\). They determine the value of \(D_{\text{GL}_n(K)}(K^n)\) for all fields \(K\) and integers \(n\). For the distinguishing numbers of graphs, they study the possible value of the distinguishing number of a graph in terms of its automorphism group, its maximum degree, and other structural properties. It is proved that if \(\text{Aut}(G)=S_n\) and each orbit of \(\text{Aut}(G)\) has size less than \(\binom n2\), then \(D(G)=\lceil n^{\frac 1k}\rceil\) for some positive integer \(k\). A Brooks theorem for the distinguishing number is obtained: for any graph \(G\), \(D(G)\leq \varDelta(G)\), unless \(G\) is a complete graph, regular bipartite graph, or \(C_5\). They also introduce the notion of uniquely distinguishable graphs and study the distinguishing number of disconnected graphs.