Distance measures in graphs
Mazorodze, Jaya Percival
MetadataShow full item record
This thesis details the results of an investigation of bounds on four distances measures, namely, radius, diameter, the Gutman index and the edge-Wiener index, in terms of other graph parameters, namely, order, irregularity index and the three classical connectivity measures, minimum degree, vertex-connectivity and edgeconnectivity. The thesis has six chapters. In Chapter 1, we de ne the most important terms used throughout the thesis and we also give a motivation for our research and provide background for relevant results. In this chapter we include the importance of the distance measures to be studied.Chapter 2 focuses on the radius, diameter and the degree sequence of a graph. We give asymptotically sharp upper bounds on the radius and diameter of (i) a connected graph, (ii) a connected triangle-free graph, (iii) a connected C4-free graph of given order, minimum degree, and given number of distinct terms in the degree sequence of the graph. We also give better bounds for graphs with a given order, minimum degree and maximum degree. Our results improve on old classical theorems by Erd os, Pach, Pollack and Tuza  on radius, diameter and minimum degree.In Chapter 3, we deal with the Gutman index and minimum degree. We show that for nite connected graphs of order n and minimum degree , where is a constant, Gut(G) 24 3 55( +1)n5 +O(n4). Our bound is asymptotically sharp for every 2 and it extends results of Dankelmann, Gutman, Mukwembi and Swart  and Mukwembi , whose bound is sharp only for graphs of minimum degree 2: In Chapter 4, we develop the concept of the Gutman index and edge-Wiener index in graphs given order and vertex-connectivity. We show that Gut(G) 24 55 n5 +O(n4) for graphs of order n and vertex-connectivity , where is a constant. Our bound is asymptotically sharp for every 1 and it substantially generalizes the bound of Mukwembi . As a corollary, we obtain a similar result for the edge-Wiener index of graphs of given order and vertex-connectivity.Chapter 5 completes our study of the Gutman index, the edge-Wiener index and edge-connectivity. We study the Gutman index Gut(G) and the Edge-Wiener index We(G) of graphs G of given order n and edge-connectivity . We show that the bound Gut(G) 24 3 55( +1)n5 + O(n4) is asymptotically sharp for 8. We improve this result considerably for 7 by presenting asymptotically sharp upper bounds on Gut(G) and We(G) for 2 7. We complete our study in Chapter 6 in which we use techniques introduced in Chapter 5 to solve new problems on size. We give asymptotically sharp upper bounds on the size, m of (i) a connected triangle-free graph in terms of order, diameter and minimum degree,(ii) a connected graph in terms of order, diameter and edge-connectivity, (iii) a connected triangle-free graph in terms of edge-connectivity, order and diameter. The result is a strengthening of an old classical theorem of Ore  if edge-connectivity is prescribed and constant.
Additional Citation InformationMazorodze, J. P. (2016). Distance measures in graphs (Unpublished Doctoral thesis). University of Zimbabwe, Harare.
SubjectGraph theory terminology