University of Zimbabwe Institutional Repository

# Distance measures in graphs

 dc.contributor.author Mazorodze, Jaya Percival dc.date.accessioned 2017-03-27T07:58:59Z dc.date.available 2017-03-27T07:58:59Z dc.date.issued 2016-10 dc.identifier.citation Mazorodze, J. P. (2016). Distance measures in graphs (Unpublished Doctoral thesis). University of Zimbabwe, Harare. en_US dc.identifier.uri http://hdl.handle.net/10646/3020 dc.description.abstract This thesis details the results of an investigation of bounds on four distances measures, en_US 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 [24] 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 [18] and Mukwembi [43], 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 [43]. 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 [49] if edge-connectivity is prescribed and constant. dc.language.iso en_ZW en_US dc.subject Graph theory terminology en_US dc.subject Topological indices en_US dc.subject Gutman index en_US dc.subject edge-wiener index en_US dc.subject vertex-connectivity en_US dc.title Distance measures in graphs en_US thesis.degree.advisor Mukwembi, Simon thesis.degree.advisor Stewart, Alexander Grant Robertson thesis.degree.country Zimbabwe en_US thesis.degree.discipline Mathematics en_US thesis.degree.faculty Faculty of Science en_US thesis.degree.grantor University of Zimbabwe en_US thesis.degree.grantoremail specialcol@uzlib.uz.ac.zw thesis.degree.level DPhil en_US thesis.degree.name Doctor of Philosophy en_US thesis.degree.thesistype Thesis en_US dc.date.defense 2016-04
﻿