Leaf‐Critical and Leaf‐Stable Graphs

The minimum leaf number ml( G ) of a connected graph G is defined as the minimum number of leaves of the spanning trees of G if G is not hamiltonian and 1 if G is hamiltonian. We study nonhamiltonian graphs with the property l : = ml ( G − v ) = ml ( G ) − 1 for each v ∈ V ( G ) or l : = ml ( G − v ) = ml ( G ) for each v ∈ V ( G ) . These graphs will be called ( l + 1 ) ‐leaf‐critical and l ‐leaf‐stable, respectively. It is far from obvious whether such graphs exist; for example, the existence of 3‐leaf‐critical graphs (that turn out to be the so‐called hypotraceable graphs) was an open problem until 1975. We show that l ‐leaf‐stable and l ‐leaf‐critical graphs exist for every integer l ≥ 2 , moreover for n sufficiently large, planar l ‐leaf‐stable and l ‐leaf‐critical graphs exist on n vertices. We also characterize 2‐fragments of leaf‐critical graphs generalizing a lemma of Thomassen. As an application of some of the leaf‐critical graphs constructed, we settle an open problem of Gargano et al. concerning spanning spiders. We also explore connections with a family of graphs introduced by Grünbaum in correspondence with the problem of finding graphs without concurrent longest paths.