Symmetry breaking in graphs (Q1918875)

Summary: A labeling of the vertices of a graph \(G\), \(\phi: V(G)\to \{1,\dots, 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)\) is \(\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)= S_4\), then either \(D(G)= 2\) or \(D(G)= 4\).