[Solved]: What is the maximum number of shortest paths between any pair of vertices in a chordal graph?

Problem Detail: 

A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ corresponds to a minimal separator. In general, $G$ can have more than one clique tree representing it. A graph is said to be geodetic if the shortest path between any pair of vertices is unique.

Consider a chordal graph $G$ in which every minimal separator is a singleton set. I can prove such a graph is geodetic, but this property doesn't hold once minimal separators get larger. For example, consider a graph with a minimal separator $S = \{2,3\}$ of size 2 below. It already has 2 shortest paths between the vertices 1 and 4.

In fact, consider two adjacent vertices in a clique tree of a chordal graph. Let $S$ be the minimal separator corresponding to the edge between them. Now consider two distinct vertices $u$ and $v$ in these adjacent cliques such that $u,v \notin S$. The number of shortest paths from $u$ to $v$ is the size of the minimal separator between them. This is because, roughly speaking, it takes one step to move from any vertex in a clique to a separator, and likewise any vertex in a clique can be reached with one step from the separator.

Finally, consider an example like below. The graph has 3 maximal cliques, and the minimal separators are $\{ 4,5 \}$ and $\{ 2,3 \}$. Now the number of shortest paths from 1 to 6 is $2 \times 2 = 4$.

Given a connected chordal graph $G$ (with no loops nor parallel edges), what is the maximum number of shortest paths there can exist between any pair of vertices? How can it be bounded (in terms of $n$ and $m$)?

Asked By : Juho

Answered By : Pål GD

It can be exponential in $n/2$. The following graph has $2^{(n/2) - 1}$ shortest paths between the endpoints:

This graph has $2^{(14/2)-1} = 2^6 = 64$ different shortest path, each corresponding to a selection of "ups" and "downs".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10438