
arXiv: math/0406542
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.
labelling, Group Theory (math.GR), 05C15, 05C25, 20D60, Graphs and abstract algebra (groups, rings, fields, etc.), Graph labelling (graceful graphs, bandwidth, etc.), graph automorphism, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), group action, Mathematics - Group Theory, Mathematics, Arithmetic and combinatorial problems involving abstract finite groups, distinguishing number
labelling, Group Theory (math.GR), 05C15, 05C25, 20D60, Graphs and abstract algebra (groups, rings, fields, etc.), Graph labelling (graceful graphs, bandwidth, etc.), graph automorphism, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), group action, Mathematics - Group Theory, Mathematics, Arithmetic and combinatorial problems involving abstract finite groups, distinguishing number
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 24 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
