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.

Item Type: | Article |
---|---|

Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |

Depositing User: | Dr. Gábor Wiener |

Date Deposited: | 24 Aug 2016 07:25 |

Last Modified: | 24 Aug 2016 07:25 |

URI: | http://real.mtak.hu/id/eprint/39095 |

### Actions (login required)

Edit Item |