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

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-su...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2014-12, Vol.179, p.222-228
Main Authors: Ali, Patrick, Mukwembi, Simon, Dankelmann, Peter
Format: Article
Language:English
Subjects:
Diameter
Distance
Planar
Steiner diameter
Steiner distance
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2014.07.007