Distinguishing numbers for graphs and groups
Abstract
Description
A graph G is distinguished if its vertices are labelled by a map ϕ: V(G) \longrightarrow {1,2,...,k} so that no graph automorphism preserves ϕ. The distinguishing number of G is the minimum number k necessary for ϕto distinguish the graph. It is one measure of the complexity of the graph.
We extend these definitions to an arbitrary group action of G on a set X. A labelling ϕ: X \longrightarrow {1,2,...,k} is distinguishing if no nontrivial element of G preserves ϕexcept those in the stabilizer of X. The distinguishing number of the group action on X is the minimum k needed for ϕto distinguish the group action. We show that distinguishing group actions is a more general problem than distinguishing graphs.
We completely characterize actions of the symmetric group S_n on a set with distinguishing number n.
13 pages; final version
13 pages; final version