Minimum degree, leaf number and traceability

Mukwembi, Simon (2013) Minimum degree, leaf number and traceability.

Full text not available from this repository.
Official URL:


This paper was written during the author’s Sabbatical visit at the University of Zimbabwe, Harare.,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.,National Research Foundation and the University of KwaZulu-Natal

Item Type: Article
Uncontrolled Keywords: interconnection network,graph,leaf number,traceability,Hamiltonicity,Graffiti.pc
Divisions: Universities > State Universities > University of Zimbabwe
Depositing User: Mr. Edmore Sibanda
Date Deposited: 09 Sep 2017 22:01
Last Modified: 09 Sep 2017 22:01

Actions (login required)

View Item View Item