Distinguishing labellings of group action on vector spaces and graphs

Suppose Gamma is a group acting on a set X. A k-labeling of X is a mapping c: X -> {1, 2,...,k}. A labeling c of X is distinguishing (with respect to the action of Gamma) if for any g is an element of Gamma, g not equal id(X), there exists an element x is an element of X such that c(x) not equal c(g(x)). The distinguishing number, D-Gamma(X), of the action of Gamma 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 GL(n)(K) over a field K acting on the vector space K-n 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 D-GLn(K)(K-n) 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) = S-n and each orbit of Aut(G) has size less than ((n)(2)), then D(G) = [n(1/k)] for some positive integer k. A Brooks type theorem for the distinguishing number is obtained: for any graph G, D(G) <= Delta(G), unless G is a complete graph, regular complete bipartite graph, or C-5. We introduce the notion of uniquely distinguishable graphs and study the distinguishing number of disconnected graphs. (c) 2006 Elsevier Inc. All rights reserved.