Please use this identifier to cite or link to this item: http://hdl.handle.net/10646/3380
Title: Minimum degree, leaf number and traceability
Authors: Mukwembi, Simon
metadata.dc.contributor.authoremail: mukwembi@ukzn.ac.za
metadata.dc.type: Article
Keywords: interconnection network
graph
leaf number
traceability
Hamiltonicity
Graffiti.pc
Issue Date: 26-Mar-2013
Publisher: Institute of Mathematics of the Czech Academy of Sciences
Citation: Mukwembi, S. (2013). Minimum degree, leaf number and traceability. Czechoslovak Mathematical Journal, 63 (2), 539-545.
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.
Description: This paper was written during the author’s Sabbatical visit at the University of Zimbabwe, Harare.
URI: http://hdl.handle.net/10646/3380
ISSN: 1572-9141
Appears in Collections:Department of Mathematics Staff Publications

Files in This Item:
File Description SizeFormat 
Mukwembi_Minimum_degree_leaf_number_and_traceability.pdf120.77 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.