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 v1,v2…,vk be distinct vertices in G. We prove that there are i and j, 1 ≤ i < j ≤ k, such that dG(vi,vj)≤2n−2k. Moreover, for every k and n the subdivided k-star, with rays of lengths ⌊n−1k⌋ and ⌈n−1k⌉, 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.