Improved sufficient conditions for k-leaf-connected graphs

For integer k≥2, a graph G is called k-leaf-connected if |V(G)|≥k+1 and given any subset S⊆V(G) with |S|=k,G always has a spanning tree T such that S is precisely the set of leaves of T. Thus a graph is 2-leaf-connected if and only if it is Hamilton-connected. Gurgel and Wakabayashi (1986) provided...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2022-06, Vol.314, p.17-30
Main Authors: Ao, Guoyan, Liu, Ruifang, Yuan, Jinjiang, Li, Rao
Format: Article
Language:English
Subjects:
[formula omitted]-leaf-connected
Complement
Hamilton-connected
Signless Laplacian
Spectral radius
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For integer k≥2, a graph G is called k-leaf-connected if |V(G)|≥k+1 and given any subset S⊆V(G) with |S|=k,G always has a spanning tree T such that S is precisely the set of leaves of T. Thus a graph is 2-leaf-connected if and only if it is Hamilton-connected. Gurgel and Wakabayashi (1986) provided a sufficient condition based upon the size for a graph to be k-leaf-connected. In this paper, we present a new condition for k-leaf-connected graphs which improves the result of Gurgel and Wakabayashi. Meanwhile, we also extend the condition on Hamilton-connected graphs of Zhou and Wang (2017). As applications, sufficient conditions for a graph to be k-leaf-connected in terms of the (signless Laplacian) spectral radius of G or its complement are obtained.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2022.02.020