• Login
    View Item 
    •   UZ eScholar Home
    • Faculty of Science
    • Department of Mathematics
    • Department of Mathematics Staff Publications
    • View Item
    •   UZ eScholar Home
    • Faculty of Science
    • Department of Mathematics
    • Department of Mathematics Staff Publications
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Minimum degree, leaf number and traceability

    Thumbnail
    View/Open
    Mukwembi_Minimum_degree_leaf_number_and_traceability.pdf (120.7Kb)
    Date
    2013-03-26
    Author
    Mukwembi, Simon
    Type
    Article
    Metadata
    Show full item record

    Abstract
    Let G be a finite connected graph with minimum degree δ. The leaf number L (G) of G is defined as the maximum number of leaf vertices contained in a spanning tree of G. We prove that if δ >12(L (G) + 1), then G is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if δ>12(L (G) + 1), then G contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaVi ̃na and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin. 15 (2008), 1–16]. For G claw-free, we show that if δ >12(L (G) + 1), then G is Hamiltonian. This again confirms, and even improves, the conjecture of Graffiti.pc for this class of graphs.
    URI
    http://hdl.handle.net/10646/3380
    Additional Citation Information
    Mukwembi, S. (2013). Minimum degree, leaf number and traceability. Czechoslovak Mathematical Journal, 63 (2), 539-545.
    Sponsor
    National Research Foundation and the University of KwaZulu-Natal
    Publisher
    Institute of Mathematics of the Czech Academy of Sciences
    Subject
    interconnection network
    graph
    leaf number
    traceability
    Hamiltonicity
    Graffiti.pc
    Additional Notes
    This paper was written during the author’s Sabbatical visit at the University of Zimbabwe, Harare.
    Collections
    • Department of Mathematics Staff Publications [14]

    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