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.

A chordal graph in which the minimal separator is of size 2.

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$.

enter image description here

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$)?

up vote 6 down vote accepted

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

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

  • Thanks! Your graph is missing labels 10 and 13. If you don't mind, I'll update the pic :-) – Juho Mar 10 '13 at 22:44
  • Thanks, @Juho. The graph was a hack, indeed the labels aren't necessary. Indeed, the best would be if the endpoints were labeled $s$ and $t$ and the rest was unlabeled. – Pål GD Mar 10 '13 at 22:46
  • BTW, did you mean $2^{(n/2)-1}$ shortest paths? – Juho Mar 10 '13 at 23:02
  • @Juho Yes, I did. I was planning on writing exponential in $(n-2) / 2$ and when moving it into a power, things got messed up. Thanks (again). – Pål GD Mar 10 '13 at 23:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.