Upper bounds on the Steiner diameter of a graph

Let GG be a connected graph of order pp and SS a nonempty set of vertices of GG. Then the Steiner distance d(S)d(S) of SS is the minimum size of a connected subgraph of GG whose vertex set contains SS. If nn is an integer, 2≤n≤p2≤n≤p, the Steiner nn-diameter, diamn(G), of GG is the maximum Steiner distance of any nn-subset of vertices of GG. We give a bound on diamn(G) for a graph GG in terms of the order of GG and the minimum degree of GG. Our result implies a bound on the ordinary diameter by Erdős, Pach, Pollack and Tuza. We obtain improved bounds on diamn(G) for K3K3-free graphs and C4C4-free graphs. Moreover, we construct graphs to show that the bounds are asymptotically best possible.