On k-leaf-connected graphs
type: Item
instance of: scholarly article
title: On k-leaf-connected graphs
zbMATH Open document ID: 0599.05041
DOI: 10.1016/0095-8956(86)90023-7
published in: Journal of Combinatorial Theory. Series B
publication date: 1986-01-01T00:00:00Z
review text: U. S. R. Murty gave a generalization of the concept of Hamilton- connectivity of simple graphs calling a graph G k-leaf-connected if \(| V(G)| >k\) and for each subset S of V(G) with \(k=| S|\) there exists a spanning tree T with precisely S as set of endvertices. Clearly G is Hamilton-connected iff G is 2-leaf-connected. The authors prove that the property that a graph is k-leaf-connected is \((| V(G)| +k-1)\)-stable, which means that if u, v are non- adjacent vertices of G with \(d(u)+d(v)\geq | V(G)| +k-1\) and \(G+uv\) is k-leaf-connected, then also G is k-leaf-connected. With other results they show that for all naturals n, k, \(2\leq k<n-2\) there are k- leaf-connected graphs with \(\lceil \frac{(k+1)n}{2}\rceil\) edges, the minimum number of edges that a k-leaf-connected graph on n vertices can have.
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 3966118
zbMATH Keywords: leaf connectivity
zbMATH Keywords: Hamilton-connectivity
author: Maria Angela C. M. Gurgel
author: Yoshiko Wakabayashi
reviewed by: Michael Hager
MaRDI profile type: Publication
full work available at URL: 0095-8956(86)90023-7
OpenAlex ID: W2007233360
cites work: Q3941433
cites work: A method in graph theory
cites work: Q3097395
cites work: THE MAXIMUM CONNECTIVITY OF A GRAPH
cites work: Note on Hamilton Circuits
cites work: Hamilton connected graphs
cites work: On Hamiltonian-connected regular graphs
cites work: A generalization of the Bondy-Chvátal theorem on the k-closure
description: scientific article; zbMATH DE number 3966118