The Steiner diameter of a graph with prescribed girth

Let G be a connected graph of order p, and let S be a nonempty set of vertices of G. Then the Steiner distance d(S) of S is the minimum size of a connected subgraph of G whose vertex set contains S. If n is an integer, 2 <= n <= p, the Steiner n-diameter, diam(n)(G), of G is the maximum Steiner distance of any n-subset of vertices of G. We give upper bounds on the Steiner n-diameter of G in terms of order, minimum degree delta, and girth g, of G. Moreover, we construct graphs to show that, if for given delta and g there exists a Moore graph of minimum degree delta and girth g, then the bounds are asymptotically sharp. (c) 2013 Elsevier B.V. All rights reserved.