DIMACS Discrete Math/Theory of Computing Seminar


Symmetry breaking in graphs, or ``How do you tell your keys apart?''


Michael Albertson
Smith College


CoRE Building, CORE A (3rd floor, end of hall) NOTE ROOM CHANGE
Busch Campus, Rutgers University


4:30 PM
Tuesday, March 26, 1996


A labeling of the vertices of a graph G with the integers 1, 2, ..., r is said to be r-distinguishing if 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. It is immediate that a complete graph requires a different label for each vertex and that a graph is rigid iff it can be 1-distinguished. There seems to be a bit of a dance between properties of G's automorphism group and its distinguishing number. For instance, we prove
(i) if Aut(G) is abelian but not trivial, then D(G) = 2;
(ii) if Aut(G) is dihedral, then G can be either 2- or 3- distinguished;
(iii) D(G) = O(log|Aut(G)|);
(iv) given any group Gamma, there is a graph G with Aut(G) = Gamma and D(G)= 2; and
(v) If Aut(G) is S4, then either D(G) = 2 or D(G) = 4.
This is joint work with Karen Collins of Wesleyan University.
Document last modified on March 25, 1996