Suppose we have an $n$-vertex connected graph, $G$. For any given $i, j \in V(G)$, what is the maximum possible number of $k$-length geodesics that can exist between $i$ and $j$, where $1 \lt k \leq n-1$?
What is the maximum possible number of k-length geodesics in an n-vertex connected graph?
3
$\begingroup$
combinatorics
graph-theory
1 Answers
2
When $k$ is small compared to $n$, I think the following construction should give some idea of what's going on: partition the other $n-2$ vertices into $k-1$ sets $A_1,A_2,\dots,A_{k-1}$, roughly equal in size, join $i$ to each vertex in $A_1$, each vertex in $A_r$ to each vertex in $A_{r+1}$, and each vertex in $A_{k-1}$ to $j$. The number of geodesics of length $k$ from $i$ to $j$ will be the product of the cardinalities of the $A_r$.
Now that I think of it, this might even work if $k$ is not small compared to $n$. I take it that when you write of "$k$-length geodesics" you mean to imply that there is no path of length less than $k$ from vertex $i$ to vertex $j$.