• Login
    View Item 
    •   UZ eScholar Home
    • Faculty of Science
    • Faculty of Science ETDs
    • Faculty of Science e-Theses Collection
    • View Item
    •   UZ eScholar Home
    • Faculty of Science
    • Faculty of Science ETDs
    • Faculty of Science e-Theses Collection
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Bounds on distance-based graph parameters

    Thumbnail
    View/Open
    Munyira_BOUNDS_ON_DISTANCE_BASED_GRAPH_PARAMETERS.pdf (440.9Kb)
    Date
    2016-04
    Author
    Munyira, Sheunesu
    Metadata
    Show full item record

    Abstract
    In this thesis, we deal with bounds on distance measures, namely, degree distance, radius, diameter and the leaf number, in terms of other graph parameters, such as order and the three classical connectivity measures, minimum degree, vertexconnectivity and edge-connectivity. The thesis has six chapters. In Chapter 1, apart from de ning the most important terms used throughout the thesis, we give a motivation for our research and provide background for relevant results. The practical importance of the distance measures to be studied in the thesis is also given in this chapter. Chapter 2 focuses on degree distance and minimum degree. Here, we give an asymptotically sharp upper bound on the degree distance in terms of order, minimum degree and diameter. As a corollary, we obtain the bound D0(G) n4 9( + 1) +O(n3) on the degree distance D0(G) of a graph G of order n and minimum degree . This result apart from improving on a result of Dankelmann, Gutman, Mukwembi and Swart [10] for graphs of given order and minimum degree, completely settles a conjecture of Tomescu [57]. In Chapter 3, we deal with degree distance and vertex-connectivity. We give an asymptotically sharp upper bound on the degree distance in terms of order, vertexconnectivity, and diameter. As a corollary, we obtain the bound, D0(G) n4 27 +O(n3) on the degree distance in terms of order and vertex-connectivity. We give examples to show that this bound of a graph G, for xed vertex-connectivity is asymptotically sharp. Chapter 4 completes our study of degree distance, in relation to the three classical connectivity measures, by looking at degree distance and edge-connectivity. In this chapter, we give asymptotically tight upper bounds on degree distance in terms of order and edge-connectivity. Chapter 5 is a chapter in which we use techniques introduced in Chapter 3 to solve new problems on the size of a graph. Here, we give an asymptotically sharp upper bound on size of a graph G, in terms of order, diameter and vertexconnectivity. The result is a strengthening of an old classical theorem of Ore [49] if vertex-connectivity is prescribed and constant. Using the same techniques, we obtained an asymptotically tight upper bound on the size of a graph in terms of order, radius and vertex-connectivity. The result is an improvement of Vizing's theorem [60] if vertex-connectivity is prescribed. Finally, in Chapter 6, we discuss, radius, diameter and the leaf number. We give tight upper bounds on the maximum radius and diameter of a graph G in terms of minimum degree and the leaf number. We also give a tight lower bound on the radius in terms of order, and the leaf number. Equivalently, our result provides a lower bound on the leaf number of a graph in terms of minimum degree and diameter. Moreover, we prove a lower bound on the leaf number which essentially solves a conjecture of Linial reported in [17].
    URI
    http://hdl.handle.net/10646/2563
    Subject
    graph theory
    graph parameters
    degree distance
    Collections
    • Faculty of Science e-Theses Collection [257]

    University of Zimbabwe: Educating To Change Lives!
    DSpace software copyright © 2002-2020  DuraSpace | Contact Us | Send Feedback
     

     

    Browse

    All of UZ eScholarCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Statistics

    View Usage StatisticsView Google Analytics Statistics

    University of Zimbabwe: Educating To Change Lives!
    DSpace software copyright © 2002-2020  DuraSpace | Contact Us | Send Feedback