Repository logo
 

Bounds on distances for spanning trees of graphs.

dc.contributor.advisorMorgan, Megan Jane.
dc.contributor.advisorMukwembi, Simon.
dc.contributor.authorNtuli, Mthobisi Luca.
dc.date.accessioned2018-10-15T13:01:22Z
dc.date.available2018-10-15T13:01:22Z
dc.date.created2018
dc.date.issued2018
dc.descriptionMaster of Science in Applied Mathematics, University of KwaZulu-Natal, Westville, 2018.en_US
dc.description.abstractIn 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.en_US
dc.description.notesDate (2018) taken as per title page.en_US
dc.identifier.urihttp://hdl.handle.net/10413/15652
dc.language.isoen_ZAen_US
dc.subject.otherGraph theory.en_US
dc.subject.otherSpanning trees.en_US
dc.subject.otherVertex math.en_US
dc.subject.otherEdges.en_US
dc.subject.otherGraphs.en_US
dc.titleBounds on distances for spanning trees of graphs.en_US
dc.typeThesisen_US

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Ntuli_Mthobisi Luca_2018.pdf
Size:
1.87 MB
Format:
Adobe Portable Document Format
Description:
Thesis.

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.64 KB
Format:
Item-specific license agreed upon to submission
Description: