Article ID Journal Published Year Pages File Type
4647669 Discrete Mathematics 2013 5 Pages PDF
Abstract
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, diamn(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 δ, and girth g, of G. Moreover, we construct graphs to show that, if for given δ and g there exists a Moore graph of minimum degree δ and girth g, then the bounds are asymptotically sharp.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,