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
This is joint work with Karen Collins of Wesleyan University.
- (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.
Document last modified on March 25, 1996