Minimum Degree, Leaf Number, and Hamiltonicity
Simon Mukwembi · American Mathematical Monthly · 2013
Let G be a finite connected graph with minimum degree δ > 4. The leaf number L(G) of G is defined as the maximum number of leaf vertices contained in a spanning tree of G. We show that if δ ≥ L(G) − 1, then G is Hamiltonian. This confirms, and improves, a conjecture of the computer program Graffiti.pc.