Groups, Graphs, and Symmetry-Breaking
Abstract
A labeling of a graph G is said to be r-distinguishing if no
automorphism of G preserves all of the vertex labels. The smallest
such number r for which there is an r-distinguishing labeling on
G is called the distinguishing number of G. The distinguishing set
of a group Gamma, D(Gamma), is the set of distinguishing numbers of
graphs G in which Aut(G) = Gamma. It is shown that D(Gamma) is
non-empty for any finite group Gamma. In particular,
D(Dn) is found where Dn is the dihedral group
with 2n elements. From there, the generalized Petersen graphs,
GP(n,k), are defined and the automorphism groups and distinguishing
numbers of such graphs are given.
Collections
- Masters Theses [19415]