\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4
Abstract for Michael O. Albertson and Karen L. Collins, Symmetry Breaking in Graphs

A labeling of the vertices of a graph G, $\phi :V(G) \rightarrow
\{1,\ldots,r\}$, is said to be $r$-distinguishing provided no automorphism of
the graph preserves all of the vertex labels. The distinguishing number
of a graph G, denoted by $D(G)$, is the minimum $r$ such that $G$ has an
$r$-distinguishing labeling. The distinguishing number of the complete
graph on $t$ vertices is $t$.  In contrast, we prove
(i) given any group $\Gamma$, there
is a graph $G$ such that $Aut(G) \cong \Gamma$ and $D(G)= 2$; 
(ii) $D(G) = O(log(|Aut(G)|))$;
(iii) if $Aut(G)$ is abelian, then $D(G) \leq 2$; 
(iv) if $Aut(G)$ is dihedral, then  $D(G) \leq 3$;  and
(v) If $Aut(G) \cong S_4$, then either $D(G) = 2$ or $D(G) = 4$. 
Mathematics Subject Classification 05C,20B,20F,68R

\bye