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