Return to search

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<sub>n</sub>) is found where D<sub>n</sub> 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. / Master of Science

Identiferoai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/36630
Date28 April 1998
CreatorsPotanka, Karen Sue
ContributorsMathematics, Brown, Ezra A., Boisen, Monte B. Jr., Ball, Joseph A.
PublisherVirginia Tech
Source SetsVirginia Tech Theses and Dissertation
Detected LanguageEnglish
TypeThesis
Formatapplication/pdf
RightsIn Copyright, http://rightsstatements.org/vocab/InC/1.0/
Relationetd.pdf

Page generated in 0.0022 seconds