On the minimum distance in a k-vertex set in a graph
Abstract Consider the smallest distance among k distinct vertices in a graph. How large can it be? Let G be a connected graph on n vertices, let k satisfy 3 ≤ k  v 1 , v 2 … , v k be distinct vertices in G. We prove that there are i and j, 1 ≤ i  d G ( v i , v j ) ≤ 2 n − 2 k . Moreover, for every k and n the subdivided k-star, with rays of lengths ⌊ n − 1 k ⌋ and ⌈ n − 1 k ⌉ , is one of the extremal graphs. The special case k = 2 coincides with the well-known fact that in a connected graph two vertices are on distance at most n − 1 , and the maximum distance is achieved for the endvertices of the path Pn. We consider also the corresponding problem for 2-connected graphs and we solve it for k = 3 .