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.
  2. 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.
  3. 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.