Distinguishing numbers for graphs and groups

Julianna Tymoczko

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

A graph $G$ is distinguished if its vertices are labelled by a map $\phi: V(G) \longrightarrow \{1,2,\ldots, k\}$ so that no non-trivial graph automorphism preserves $\phi$. The distinguishing number of $G$ is the minimum number $k$ necessary for $\phi$ to distinguish the graph. It measures the symmetry of the graph. We extend these definitions to an arbitrary group action of $\Gamma$ on a set $X$. A labelling $\phi: X \longrightarrow \{1,2,\ldots,k\}$ is distinguishing if no element of $\Gamma$ preserves $\phi$ except those which fix each element of $X$. The distinguishing number of the group action on $X$ is the minimum $k$ needed for $\phi$ to distinguish the group action. We show that distinguishing group actions is a more general problem than distinguishing graphs. We completely characterize actions of $S_n$ on a set with distinguishing number $n$, answering an open question of Albertson and Collins.

Détail

DOI : 10.37236/1816

Classification : 05C25, 20D60, 05C78
Mots-clés : graph automorphism, distinguishing number, group action, labelling