Minimum degree, leaf number and traceability
MetadataShow full item record
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.
Additional Citation InformationMukwembi, S. (2013). Minimum degree, leaf number and traceability. Czechoslovak Mathematical Journal, 63 (2), 539-545.
SponsorNational Research Foundation and the University of KwaZulu-Natal
Institute of Mathematics of the Czech Academy of Sciences
This paper was written during the author’s Sabbatical visit at the University of Zimbabwe, Harare.