| dc.contributor.author | Mukwembi, Simon | |
| dc.date.accessioned | 2017-09-06T07:35:23Z | |
| dc.date.available | 2017-09-06T07:35:23Z | |
| dc.date.issued | 2013-03-26 | |
| dc.identifier.citation | Mukwembi, S. (2013). Minimum degree, leaf number and traceability. Czechoslovak Mathematical Journal, 63 (2), 539-545. | en_US |
| dc.identifier.issn | 1572-9141 | |
| dc.identifier.uri | http://hdl.handle.net/10646/3380 | |
| dc.description | This paper was written during the author’s Sabbatical visit at the University of Zimbabwe, Harare. | en_US |
| dc.description.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. | en_US |
| dc.description.sponsorship | National Research Foundation and the University of KwaZulu-Natal | en_US |
| dc.language.iso | en_ZW | en_US |
| dc.publisher | Institute of Mathematics of the Czech Academy of Sciences | en_US |
| dc.subject | interconnection network | en_US |
| dc.subject | graph | en_US |
| dc.subject | leaf number | en_US |
| dc.subject | traceability | en_US |
| dc.subject | Hamiltonicity | en_US |
| dc.subject | Graffiti.pc | en_US |
| dc.title | Minimum degree, leaf number and traceability | en_US |
| dc.type | Article | en_US |
| dc.contributor.authoremail | mukwembi@ukzn.ac.za | en_US |
