Show simple item record

dc.contributor.advisorDankelmann, Peter A.
dc.contributor.advisorMukwembi, Simon.
dc.creatorAli, Patrick Yawadu.
dc.date.accessioned2013-10-31T11:40:07Z
dc.date.available2013-10-31T11:40:07Z
dc.date.created2011
dc.date.issued2011
dc.identifier.urihttp://hdl.handle.net/10413/9841
dc.descriptionThesis (Ph.D.)-University of KwaZulu-Natal, Westville, 2011.en
dc.description.abstractIn this thesis we investigate bounds on distance measures, namely, Steiner diameter and radius, in terms of other graph parameters. The thesis consists of four chapters. In Chapter 1, we define the most significant terms used throughout the thesis, provide an underlying motivation for our research and give background in relevant results. 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. In Chapter 2, 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 Erdös, Pach, Pollack and Tuza. We obtain improved bounds on diamn(G) for K3-free graphs and C4-free graphs. In Chapter 3, we prove that, if G is a 3-connected plane graph of order p and maximum face length l then the radius of G does not exceed p/6 + 5l/6 + 5/6. For constant l, our bound improves on a bound by Harant. Furthermore we extend these results to 4- and 5-connected planar graphs. Finally, we complete our study in Chapter 4 by providing an upper bound on diamn(G) for a maximal planar graph G.en
dc.language.isoen_ZAen
dc.subjectGraph theory.en
dc.subjectTheses--Mathematics.en
dc.titleAspects of distance measures in graphs.en
dc.typeThesisen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record