Leaf-critical and leaf-stable graphs

Wiener, Gábor (2016) Leaf-critical and leaf-stable graphs. Journal of Graph Theory. ISSN 0364-9024

Text leafcriticalrevised.pdf - Accepted Version Restricted to Registered users only Download (372kB) | Request a copy

Abstract

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 vertex v of G or l:=ml(G-v)=ml(G) for each vertex v of G. These graphs will be called (l+1)-leaf-critical and l-leaf-stable, respectively. It is far from obvious whether such graphs exist; e.g. 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 at least 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 Grunbaum in correspondence with the problem of finding graphs without concurrent longest paths.

Actions (login required)

Edit Item