Next: Shannon Fitzpatrick - The Up: Discrete Mathematics / Mathématiques Previous: Ramaswamy Chandrasekaran - Nonnegative
Karen L. Collins - Symmetry breaking in graphs
KAREN L. COLLINS, Wesleyan University, Middletown, Connecticut 06459, USA | |
Symmetry breaking in graphs |
A labeling of the vertices of a graph G is said to be r-distinguishing, provided no non-trivial automorphism of the graph preserves all of the vertex labels. We define the distinguishing number of G, D(G), to be the minimum r such that G has an r-distinguishing labeling. For example, D(Cn)= 3 for n= 3,4,5, but D(Cn)=2 if . For any group J, we define is isomorphic to . Let Hn be the dihedral group with 2n elements. Then unless n=3,4,5,6,10, in which case, . This talk will be a survey of distinguishing results for groups and graphs, with special attention to symmetric groups.
eo@camel.math.ca