• Login
    View Item 
    •   ResearchSpace Home
    • College of Agriculture, Engineering and Science
    • School Mathematics, Statistics and Computer Science
    • Applied Mathematics
    • Masters Degrees (Applied Mathematics)
    • View Item
    •   ResearchSpace Home
    • College of Agriculture, Engineering and Science
    • School Mathematics, Statistics and Computer Science
    • Applied Mathematics
    • Masters Degrees (Applied Mathematics)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Bounds on distances for spanning trees of graphs.

    Thumbnail
    View/Open
    Thesis. (1.869Mb)
    Date
    2018
    Author
    Ntuli, Mthobisi Luca.
    Metadata
    Show full item record
    Abstract
    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.
    URI
    http://hdl.handle.net/10413/15652
    Collections
    • Masters Degrees (Applied Mathematics) [59]

    DSpace software copyright © 2002-2013  Duraspace
    Contact Us | Send Feedback
    Theme by 
    @mire NV
     

     

    Browse

    All of ResearchSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsAdvisorsTypeThis CollectionBy Issue DateAuthorsTitlesSubjectsAdvisorsType

    My Account

    LoginRegister

    DSpace software copyright © 2002-2013  Duraspace
    Contact Us | Send Feedback
    Theme by 
    @mire NV