The "$k$th diameter" of a graph

94 Views Asked by At

From Menger's theorem, we know that a graph is $k$-connected if and only if it contains $k$ independent paths between any two vertices. Let $G$ be a $k$-connected graph and define the distance between any two vertices $u$ and $v$ to be the length of the longest path among the $k$ shortest independent paths between $u$ and $v$. Define $k$th diameter of $G$, say $D_k(G)$, accordingly to this distance. We see that $D_1(G)$ is the usual diameter of $G$ and that $D_k(G)$ is an upper bound on the usual diameter of $G$ after removing $k-1$ vertices.

Is there any work done on this quantity? Or something like it?