Bounds on distance-based graph parameters

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