dc.contributor.advisor Morgan, Megan Jane. dc.contributor.advisor Mukwembi, Simon. dc.creator Ntuli, Mthobisi Luca. dc.date.accessioned 2018-10-15T13:01:22Z dc.date.available 2018-10-15T13:01:22Z dc.date.created 2018 dc.date.issued 2018 dc.identifier.uri http://hdl.handle.net/10413/15652 dc.description Master of Science in Applied Mathematics, University of KwaZulu-Natal, Westville, 2018. en_US dc.description.abstract In graph theory, there are several techniques known in literature for constructing en_US 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. dc.language.iso en_ZA en_US dc.subject.other Graph theory. en_US dc.subject.other Spanning trees. en_US dc.subject.other Vertex math. en_US dc.subject.other Edges. en_US dc.subject.other Graphs. en_US dc.title Bounds on distances for spanning trees of graphs. en_US dc.type Thesis en_US dc.description.notes Date (2018) taken as per title page. en_US
﻿