Distance measures in graphs

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