Bounds on distance-based topological indices in graphs.

Abstract

This thesis details the results of investigations into bounds on some distance-based topological indices. The thesis consists of six chapters. In the first chapter we define the standard graph theory concepts, and introduce the distance-based graph invariants called topological indices. We give some background to these mathematical models, and show their applications, which are largely in chemistry and pharmacology. To complete the chapter we present some known results which will be relevant to the work. Chapter 2 focuses on the topological index called the eccentric connectivity index. We obtain an exact lower bound on this index, in terms of order, and show that this bound is sharp. An asymptotically sharp upper bound is also derived. In addition, for trees of given order, when the diameter is also prescribed, tight upper and lower bounds are provided. Our investigation into the eccentric connectivity index continues in Chapter 3. We generalize a result on trees from the previous chapter, proving that the known tight lower bound on the index for a tree in terms of order and diameter, is also valid for a graph of given order and diameter. In Chapter 4, we turn to bounds on the eccentric connectivity index in terms of order and minimum degree. We first consider graphs with constant degree (regular graphs). Došlić, Saheli & Vukičević, and Ilić posed the problem of determining extremal graphs with respect to our index, for regular (and more specifically, cubic) graphs. In addressing this open problem, we find upper and lower bounds

for the index. We also provide an extremal graph for the upper bound. Thereafter, the chapter continues with a consideration of minimum degree. For given order and minimum degree, an asymptotically sharp upper bound on the index is derived. In Chapter 5, we turn our focus to the well-studied Wiener index. For trees of given order, we determine a sharp upper bound on this index, in terms of the eccentric connectivity index. With the use of spanning trees, this bound is then generalized to graphs. Yet another distance-based topological index, the degree distance, is considered in Chapter 6. We find an asymptotically sharp upper bound on this index, for a graph of given order. This proof definitively settles a conjecture posed by Tomescu in 1999.