On the shortest path in some k-connected graphs
Kai An Sim, Ta Sheng Tan, Kok Bin Wong · AIP conference proceedings · 2016
Suppose G is a connected graph and u and v are two distinct vertices of G. Let P[u, v] be the shortest path in G with endpoints u and v. Let t(G) = max{| V (P[u, v]) |:u, v ∈ V (G)}. A graph G is said to be k-connected if it has more than k vertices and removal of fewer than k vertices does not disconnect the graph G. We show that in any k-connected graph G with n vertices, t(G)≤⌊n−2k⌋+2. We also present some graphs where the equality holds.