CS 163/265, Winter 2025, Practice Problem Set 6

1. Modify a 5-vertex path by adding another edge between the first and third vertex of the path. Compute the closeness centralities and betweenness centralities of the resulting graph.

2. Find an ordering of the vertices for a six-vertex cycle graph, for which the greedy algorithm does not find the optimal coloring. Describe both your ordering and the steps of the greedy coloring algorithm for your ordering. (For this graph, every ordering is a degeneracy ordering, so this problem shows that greedy coloring in the reverse of a degeneracy ordering can be non-optimal.)

3. Let $n$ be a multiple of $3$. How many edges are in a Moon-Moser graph with $n$ vertices and $3^{n/3}$ maximal cliques? How big does $n$ need to be for the number of edges to be smaller than the number of cliques?

4. A given rooted tree $T$ has $n$ vertices. Suppose we want to draw the vertices of $T$, with integer coordinates, so that the $y$-coordinate of each vertex is its Strahler number, and with each edge drawn as a straight line segment between its two vertices. Describe a way of assigning distinct $x$-coordinates from $1$ to $n$ to the vertices so that the resulting drawing has no crossings. (You are allowed to reorder the children of each node; they do not have to be placed in an already-given order. If it helps, you can describe your ordering method as a recursive algorithm. Do not assume that $T$ is a binary tree.)