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

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 $δ$ such that $L(G)\leq 2δ-1$. We show that the circumference of $G$ is at least $n-1$, and that if $G$ is regular then $G$ is hamiltonian.

No reviews yet.

No comments yet.