| dc.description.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. | en_US |
