CompSci 163/265, Spring 2015, Homework 8

  1. Let $G$ be a six-vertex graph formed from a square $abcd$ and a triangle $cde$ that share an edge, together with one more edge $ef$ attached to the third vertex of the triangle. Describe the sequence of all the recursive calls that would be performed by the pivoting version of the Bron–Kerbosch algorithm on this graph. For each call, describe the three sets given as arguments to the call, the pivot vertex $u$ chosen by the call, the list of vertices $v$ corresponding to the recursive calls that this call makes, and any maximal clique that is produced as output by the call.

  2. What are the degeneracy, $h$-index, and clustering coefficient of the same graph $G$ given in the previous problem?

  3. Suppose that we are generating simulated social-network data by using the Barabasi-Albert method, with parameter $k$: we start with a $k$-vertex clique and at each step add a new vertex connected to exactly $k$ previous vertices (chosen with probabilities in proportion to their degrees). Suppose also that we do this for exactly $9k$ steps, so that we end up with a graph that has $10k$ vertices. Define the diameter of a graph to be the largest unweighted distance between any two of its vertices. What is the smallest possible diameter of a graph that can be generated in this way? Describe how a graph with this diameter could be generated, and why no smaller diameter is possible.

  4. Use the MathSciNet collaboration distance calculator to find five mathematicians, whose collaboration distances from Paul Erdös are respectively 1, 2, 3, 4, and 5. To find the distance for an author: go to the author search feature of MathSciNet (from a UCI IP address, so that you will be given subscription access to the database), enter the name of a mathematician, click on the "Collaboration Distance" link in the results page, hit the "use Erdös" button in the collaboration distance page, and hit the search button. What is the shortest path from each of your mathematicians to Erdös? What is the largest collaboration distance you can find in this way?