Distinguishing numbers for graphs and groups

2004/06/30 by Julianna S. Tymoczko · 1 citation
Mathematics · #math.CO #math.GR #msc:05C15 #msc:05C25 #msc:20D60

paper · pdf

published as Electronic Journal of Combinatorics, 11 (1) (2004), #R63 · 13 pages; final version

arxiv created 2005/03/17 · arxiv updated 2009/12/01

Abstract

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.

Cited by

• On Distinguishing Graphs and Cost Number using Automorphism Representations

Related

• Distinguishing Numbers and Generalizations
• Distinguishing actions of symmetric groups and related graphs
• The distinguishing number of groups based on the distinguishing number of subgroups
• Distinguishing simple groups
• Stabilizing on the distinguishing number of a graph