Browsing by Author "Morgan, Megan Jane."

Now showing 1 - 2 of 2

Bounds on distance-based topological indices in graphs.
(2012) Morgan, Megan Jane.; Mukwembi, Simon.; Swart, Hendrika Cornelia Scott.
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.
Bounds on distances for spanning trees of graphs.
(2018) Ntuli, Mthobisi Luca.; Morgan, Megan Jane.; Mukwembi, Simon.
In graph theory, there are several techniques known in literature for constructing spanning trees. Some of these techniques yield spanning trees with many leaves. We will use these constructed spanning trees to bound several distance parameters. The cardinality of the vertex set of graph G is called the order, n(G) or n. The cardinality of the edge set of graph G is called the size, m(G) or m. The minimum degree of G, (G) or , is the minimum degree among the degrees of the vertices of G: A spanning tree T of a graph G is a subgraph that is a tree which includes all the vertices of G. The distance d(u; v) between two vertices u and v is the length of a shortest u-v path of G. The eccentricity, ec (v), of a vertex v 2 V (G) is the maximum distance from it to any other vertex in G. The diameter, diam(G) or d, is the maximum eccentricity amongst all vertices of G. The radius, rad(G), is the minimum eccentricity among all vertices of G. The average distance of a graph G, (G), is the expected distance between a randomly chosen pair of distinct vertices. We investigate how each constructed spanning tree can be used to bound diam- eter, radius or average distance in terms of order, size and minimum degree. The techniques to be considered include the radius-preserving spanning trees by Erd}os et al, the Ding et al technique, and the Dankelmann and Entringer technique. Finally, we use the Kleitman and West dead leaves technique to construct spanning trees with many leaves for various values of the minimum degree k (for k = 3; 4 and k > 4) and order n. We then use the leaf number to bound diameter.