Estimating the circumference of a graph in terms of its leaf number

Abstract

Let $\mathcal{T}$ be the set of spanning trees of $G$ and let $L(T)$ be the number of leaves in a tree $T$. The leaf number $L(G)$ of $G$ is defined as $L(G)=\max \{L(T)|T\in \mathcal{T}\}$. Let $G$ be a connected graph of order $n$ and minimum degree $\delta$ such that $L(G)\le 2\delta -1$. We show that the circumference of $G$ is at least $n-1$, and that if $G$ is regular then $G$ is hamiltonian.

14 pages, 9 figures