Assignment 10 (last assignment)
due by the end of class Wednesday April 4 2001.

The kcube is the graph whose vertices are the numbers
0 to 2^{k}1, where two vertices are adjacent
if and only if the binary representations of their numbers
differs in exactly one position.
For example, the 2cube has vertex set
{0=00, 1=01, 2=10, 3=11} and edge set {(01),(02),(13),(23)}.
Let G be the 3cube and G the 3cube minus vertex 7.
 Draw G and G (label the vertices).
 Determine all automorphisms of G.
 Determine all automorphisms of G.

 Determine all nonisomorphic tree with up to 6 vertices.
 Give the canonical representation of all trees
in the previous question.
 Give the canonical representation of the 2nd tree on the handout.
 Give the most efficient algorithm you can
to find the center(s) in a tree,
and analyze its worst case running time.
Briefly justify the correctness, and the running time.
 Suppose that a graph with n vertices
has exactly one vertex of degree k, for some k.
Using this vertex as a starting point (like the
center of a tree with one center), is it possible
to define a canonical representation of the graph?
If so, does this imply a polynomial time isomorphism
testing algorithm for graphs with this degree sequence?
Explain in detail.