DIMACS Discrete Math/Theory of Computing Seminar

Title:

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

Speaker:

Michael Albertson

Smith College

Place:

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

Busch Campus, Rutgers University

Time:

4:30 PM

Tuesday, March 26, 1996

Abstract:

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