Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419427 | Discrete Applied Mathematics | 2012 | 6 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Patrick Ali, Peter Dankelmann, Simon Mukwembi,