Name
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 v. V(G) or l := ml(G - v) = ml(G) for each v is an element of 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-leafstable 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. (C) 2016 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1002/jgt.22034 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
spanning tree,hamiltonian path,hamiltonian cycle,hypohamiltonian graph,hypotraceable graph | Journal | 84 |
Issue | ISSN | Citations |
4 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 0 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Wiener | 1 | 64 | 10.65 |