Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419637 | Discrete Applied Mathematics | 2013 | 6 Pages |
Abstract
Let GG be a simple connected graph with minimum degree δδ. Then GG is Hamiltonian if it contains a spanning cycle and traceable if it contains a spanning path. The leaf number L(G)L(G) of GG is defined as the maximum number of end vertices contained in a spanning tree of GG. We prove a sufficient condition, depending on L(G)L(G) and δδ, for GG to be Hamiltonian or traceable. Our results, apart from providing a new sufficient condition for Hamiltonicity, settle completely a conjecture of the computer program, Graffiti.pc, instructed by DeLaViña.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Simon Mukwembi,