TY - JOUR
T1 - DEGREE SUM CONDITION FOR THE EXISTENCE OF SPANNING k-TREES IN STAR-FREE GRAPHS
AU - Furuya, Michitaka
AU - Maezawa, Shun Ichi
AU - Matsubara, Ryota
AU - Matsuda, Haruhide
AU - Tsuchiya, Shoichi
AU - Yashima, Takamasa
N1 - Funding Information:
The authors would like to thank the anonymous referee for valuable comments and suggestions. This work was partially supported by JSPS KAKENHI Grant numbers JP18K13449 (to M.F.), JP15K04980 (to H.M.), JP19K14584 (to S.T.), and by Grant for Basic Science Research Projects from The Sumitomo Foundation (to S.T).
Publisher Copyright:
© 2022 Sciendo. All rights reserved.
PY - 2022
Y1 - 2022
N2 - For an integer k ≥ 2, a k-tree T is defined as a tree with maximum degree at most k. If a k-tree T spans a graph G, then T is called a spanning k-tree of G. Since a spanning 2-tree is a Hamiltonian path, a spanning k-tree is an extended concept of a Hamiltonian path. The first result, implying the existence of k-trees in star-free graphs, was by Caro, Krasikov, and Roditty in 1985, and independently, Jackson and Wormald in 1990, who proved that for any integer k with k ≥ 3, every connected K1,k-free graph contains a spanning k-tree. In this paper, we focus on a sharp condition that guarantees the existence of a spanning k-tree in K1,k+1-free graphs. In particular, we show that every connected K1,k+1-free graph G has a spanning k-tree if the degree sum of any 3k − 3 independent vertices in G is at least |G| − 2, where |G| is the order of G.
AB - For an integer k ≥ 2, a k-tree T is defined as a tree with maximum degree at most k. If a k-tree T spans a graph G, then T is called a spanning k-tree of G. Since a spanning 2-tree is a Hamiltonian path, a spanning k-tree is an extended concept of a Hamiltonian path. The first result, implying the existence of k-trees in star-free graphs, was by Caro, Krasikov, and Roditty in 1985, and independently, Jackson and Wormald in 1990, who proved that for any integer k with k ≥ 3, every connected K1,k-free graph contains a spanning k-tree. In this paper, we focus on a sharp condition that guarantees the existence of a spanning k-tree in K1,k+1-free graphs. In particular, we show that every connected K1,k+1-free graph G has a spanning k-tree if the degree sum of any 3k − 3 independent vertices in G is at least |G| − 2, where |G| is the order of G.
KW - degree sum condition
KW - k-tree
KW - spanning tree
KW - star-free
UR - http://www.scopus.com/inward/record.url?scp=85079613544&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85079613544&partnerID=8YFLogxK
U2 - 10.7151/dmgt.2234
DO - 10.7151/dmgt.2234
M3 - Article
AN - SCOPUS:85079613544
SN - 1234-3099
VL - 42
SP - 5
EP - 13
JO - Discussiones Mathematicae - Graph Theory
JF - Discussiones Mathematicae - Graph Theory
IS - 1
ER -