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 - 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 -