Distinguishing labellings of group action on vector spaces and graphs

Suppose Γ is a group acting on a set X. A k-labeling of X is a mapping . A labeling c of X is distinguishing (with respect to the action of Γ) if for any g∈Γ, g≠idX, there exists an element x∈X such that c(x)≠c(g(x)). The distinguishing number, DΓ(X), of the action of Γ on X is the minimum k for which there is a k-labeling which is distinguishing. This paper studies the distinguishing number of the linear group GLn(K) over a field K acting on the vector space Kn and the distinguishing number of the automorphism group Aut(G) of a graph G acting on V(G). The latter is called the distinguishing number of the graph G and is denoted by D(G). We determine the value of DGLn(K)(Kn) for all fields K and integers n. For the distinguishing number of graphs, we study the possible value of the distinguishing number of a graph in terms of its automorphism group, its maximum degree, and other structure properties. It is proved that if Aut(G)=Sn and each orbit of Aut(G) has size less than , then D(G)=⌈n1/k⌉ for some positive integer k. A Brooks type theorem for the distinguishing number is obtained: for any graph G, D(G)⩽Δ(G), unless G is a complete graph, regular complete bipartite graph, or C5. We introduce the notion of uniquely distinguishable graphs and study the distinguishing number of disconnected graphs.