Abstract:
In this thesis, we deal with bounds on distance measures, namely, degree distance,
radius, diameter and the leaf number, in terms of other graph parameters, such
as order and the three classical connectivity measures, minimum degree, vertexconnectivity
and edge-connectivity.
The thesis has six chapters. In Chapter 1, apart from de ning the most important
terms used throughout the thesis, we give a motivation for our research and provide
background for relevant results. The practical importance of the distance measures
to be studied in the thesis is also given in this chapter.
Chapter 2 focuses on degree distance and minimum degree. Here, we give an
asymptotically sharp upper bound on the degree distance in terms of order, minimum
degree and diameter. As a corollary, we obtain the bound D0(G)
n4
9( + 1)
+O(n3)
on the degree distance D0(G) of a graph G of order n and minimum degree .
This result apart from improving on a result of Dankelmann, Gutman, Mukwembi
and Swart [10] for graphs of given order and minimum degree, completely settles a
conjecture of Tomescu [57].
In Chapter 3, we deal with degree distance and vertex-connectivity. We give an
asymptotically sharp upper bound on the degree distance in terms of order, vertexconnectivity,
and diameter. As a corollary, we obtain the bound,
D0(G)
n4
27
+O(n3) on the degree distance in terms of order and vertex-connectivity.
We give examples to show that this bound of a graph G, for xed vertex-connectivity is asymptotically sharp.
Chapter 4 completes our study of degree distance, in relation to the three classical
connectivity measures, by looking at degree distance and edge-connectivity. In this
chapter, we give asymptotically tight upper bounds on degree distance in terms of
order and edge-connectivity.
Chapter 5 is a chapter in which we use techniques introduced in Chapter 3
to solve new problems on the size of a graph. Here, we give an asymptotically
sharp upper bound on size of a graph G, in terms of order, diameter and vertexconnectivity.
The result is a strengthening of an old classical theorem of Ore [49]
if vertex-connectivity is prescribed and constant. Using the same techniques, we
obtained an asymptotically tight upper bound on the size of a graph in terms of
order, radius and vertex-connectivity. The result is an improvement of Vizing's
theorem [60] if vertex-connectivity is prescribed.
Finally, in Chapter 6, we discuss, radius, diameter and the leaf number. We give
tight upper bounds on the maximum radius and diameter of a graph G in terms of
minimum degree and the leaf number. We also give a tight lower bound on the radius in terms of order, and the leaf number. Equivalently, our result provides a lower
bound on the leaf number of a graph in terms of minimum degree and diameter.
Moreover, we prove a lower bound on the leaf number which essentially solves a
conjecture of Linial reported in [17].