CompSci 163/265, Spring 2016, Homework 8

  1. Find an actor for whom the Oracle of Bacon (with its default settings) returns a path that connects that actor to Kevin Bacon but has more than four hops.

  2. Calculate the clustering coefficients of each of the five graphs of the Platonic solids (the tetrahedron, cube, regular octahedron, regular dodecahedron, and regular icosahedron).

  3. (163 students:) Prove that, in any graph, the maximum clique size is at most one plus the degeneracy. (Hint: find a subgraph in which all vertices have degree at least the clique size minus one.)

    (265 students:) Prove that the degeneracy of a chordal graph always equals one less than the size of its maximum clique.

  4. (163 students:) A complete graph is a graph in which every two vertices are adjacent. When the Bron–Kerbosch algorithm (with pivoting) is run on a 4-vertex complete graph, how many recursive calls does it make in total? When the algorithm without pivoting is run on a 4-vertex complete graph, how many recursive calls does it make in total?

    (265 students:) Give formulas for the number of recursive calls made by the Bron–Kerbosch algorithm on an $n$-vertex complete graph, with and without pivoting, as a function of $n$. (Suggestion: try it on small graphs first to find the pattern, and then verify that the pattern you find is correct.)