On the minimum distance in a k-vertex set in a graph

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 < n and let v(1), v(2) ..., v(k) be distinct vertices in G. We prove that there are i and j, 1 <= i < j <= k, such that d(G )(v(i), v(j)) <= 2n-2/k . Moreover, for every k and n the subdivided k-star, with rays of lengths left perpendicular n-1/k right perpendicular and inverted right perpendicular n-1/k inverted left perpendicular,is one of the external 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 P-n. We consider also the corresponding problem for 2-connected graphs and we solve it for k = 3. (C) 2019 Published by Elsevier Inc.