Upper bounds on the Steiner diameter of a graph

Patrick Ali, Peter Dankelmann, Simon Mukwembi

Research output: Contribution to journalArticlepeer-review

37 Citations (Scopus)


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 languageEnglish
Pages (from-to)1845-1850
Number of pages6
JournalDiscrete Applied Mathematics
Issue number12
Publication statusPublished - Aug 2012
Externally publishedYes


  • Distance
  • Steiner diameter
  • Steiner distance

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Upper bounds on the Steiner diameter of a graph'. Together they form a unique fingerprint.

Cite this