Distinguishing numbers for graphs and groups

Details Distinguishing numbers for graphs and groups Distinguishing numbers for graphs and groups

2004-06-26

arxiv.org/abs/math/0406542v2

Electronic Journal of Combinatorics, 11 (1) (2004), #R63

Mathematics

Combinatorics

13 pages; final version

Scientific paper

A graph G is distinguished if its vertices are labelled by a map \phi: V(G) \longrightarrow {1,2,...,k} so that no graph automorphism preserves \phi. The distinguishing number of G is the minimum number k necessary for \phi 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 \phi: X \longrightarrow {1,2,...,k} is distinguishing if no nontrivial element of G preserves \phi except those in the stabilizer 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 the symmetric group S_n on a set with distinguishing number n.

Affiliated with

Also associated with

No associations

Rating

Distinguishing numbers for graphs and groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distinguishing numbers for graphs and groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distinguishing numbers for graphs and groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-706475