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

1. The k-cube 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 2-cube has vertex set {0=00, 1=01, 2=10, 3=11} and edge set {(01),(02),(13),(23)}. Let G be the 3-cube and G- the 3-cube minus vertex 7.
   • Draw G and G- (label the vertices).
   • Determine all automorphisms of G-.
   • Determine all automorphisms of G.
2. • Determine all non-isomorphic 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.
3. 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.
4. 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.