Aspects of distance measures in graphs.

Abstract

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