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
