Steiner diameter of 3, 4 and 5-connected maximal planar graphs

Patrick Ali, Simon Mukwembi, Peter Dankelmann

Research output: Contribution to journalArticlepeer-review

4 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. This is a generalisation of the ordinary diameter, which is the case n=2. We give upper bounds on the Steiner n-diameter of maximum planar graphs in terms of order and connectivity. Moreover, we construct graphs to show that the bound is asymptotically sharp. Furthermore we extend this result to 4 and 5-connected maximal planar graphs.

Original languageEnglish
Pages (from-to)222-228
Number of pages7
JournalDiscrete Applied Mathematics
Publication statusPublished - 31 Dec 2014


  • Diameter
  • Distance
  • Planar
  • Steiner diameter
  • Steiner distance

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Steiner diameter of 3, 4 and 5-connected maximal planar graphs'. Together they form a unique fingerprint.

Cite this