Distance Measures in Graphs

Mazorodze, Jaya Percival (2016) Distance Measures in Graphs. PhD thesis, University of Zimbabwe.

PDF (Distance Measures in Graphs) Mazorodze, Jaya Percival.pdf - Accepted Version Restricted to Repository staff only Download (475kB) | Request a copy

Abstract

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 define 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ös, 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 finite connected graphs of order n and minimum degree δ, where δ is a constant, Gut(G) 24_355(n+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 δn 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(n+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.

Item Type:	Thesis (PhD)
Subjects:	H Social Sciences > HA Statistics Q Science > QA Mathematics
Divisions:	Africana
Depositing User:	Tim Khabala
Date Deposited:	15 May 2018 12:42
Last Modified:	15 May 2018 12:42
URI:	http://thesisbank.jhia.ac.ke/id/eprint/3985

Actions (login required)

View Item