## Abstract

Let G be a connected graph of order p and S 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 a bound on diamn(G) for a graph G in terms of the order of G and the minimum degree of G. Our result implies a bound on the ordinary diameter by Erds, Pach, Pollack and Tuza. We obtain improved bounds on diamn(G) for K3-free graphs and C4-free graphs. Moreover, we construct graphs to show that the bounds are asymptotically best possible.

Original language | English |
---|---|

Pages (from-to) | 1845-1850 |

Number of pages | 6 |

Journal | Discrete Applied Mathematics |

Volume | 160 |

Issue number | 12 |

DOIs | |

Publication status | Published - Aug 2012 |

Externally published | Yes |

## Keywords

- Distance
- Steiner diameter
- Steiner distance

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics