Distinguishing numbers for graphs and groups
| dc.creator | Tymoczko, Julianna S. | |
| dc.date | 2004-06-26 | |
| dc.date | 2005-03-17 | |
| dc.date.accessioned | 2026-07-07T05:09:43Z | |
| dc.date.available | 2026-07-07T05:09:43Z | |
| dc.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. | |
| dc.description | 13 pages; final version | |
| dc.identifier | https://arxiv.org/abs/math/0406542 | |
| dc.identifier | http://arxiv.org/abs/math/0406542 | |
| dc.identifier | Electronic Journal of Combinatorics, 11 (1) (2004), #R63 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71684 | |
| dc.subject | Combinatorics | |
| dc.subject | Group Theory | |
| dc.subject | 05C15, 05C25, 20D60 | |
| dc.title | Distinguishing numbers for graphs and groups | |
| dc.type | text |