Groups, Graphs, and Symmetry-Breaking

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(D_n) is found where D_n 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.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Mathematics

Department dc:contributor.department

Mathematics

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

1998

Author dc:creator

• Potanka, Karen Sue

Chair dc:contributor.committeechair

• Brown, Ezra A.

Committee members dc:contributor.committeemember

• Boisen, Monte B. Jr.
• Ball, Joseph A.

• Petersen Graph
• Symmetry-Breaking
• Graph Theory

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

etd-32798-215247

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/36630