Geodesic
Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 5-13 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: spanning tree, k -tree, star-free, degree sum condition 
@article{DMGT_2022_42_1_a0,
     author = {Furuya, Michitaka and Maezawa, Shun-ichi and Matsubara, Ryota and Matsuda, Haruhide and Tsuchiya, Shoichi and Yashima, Takamasa},
     title = {Degree {Sum} {Condition} for the {Existence} of {Spanning} {k-Trees} in {Star-Free} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--13},
     year = {2022},
     volume = {42},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a0/}
}
TY  - JOUR
AU  - Furuya, Michitaka
AU  - Maezawa, Shun-ichi
AU  - Matsubara, Ryota
AU  - Matsuda, Haruhide
AU  - Tsuchiya, Shoichi
AU  - Yashima, Takamasa
TI  - Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 5
EP  - 13
VL  - 42
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a0/
LA  - en
ID  - DMGT_2022_42_1_a0
ER  - 
%0 Journal Article
%A Furuya, Michitaka
%A Maezawa, Shun-ichi
%A Matsubara, Ryota
%A Matsuda, Haruhide
%A Tsuchiya, Shoichi
%A Yashima, Takamasa
%T Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 5-13
%V 42
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a0/
%G en
%F DMGT_2022_42_1_a0
Furuya, Michitaka; Maezawa, Shun-ichi; Matsubara, Ryota; Matsuda, Haruhide; Tsuchiya, Shoichi; Yashima, Takamasa. Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 5-13. http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a0/

[1] H.J. Broersma, Hamilton Cycles in Graphs and Related Topics (Ph.D. Thesis, University of Twente, 1988).

[2] Y. Caro, I. Krasikov and Y. Roditty, Spanning trees and some edge reconstructible graphs, Ars Combin. 20 A (1985) 109–118.

[3] B. Jackson and N.C. Wormald, k-walks of graphs, Australas. J. Combin. 2 (1990) 135–146.

[4] Y. Liu, F. Tian and Z. Wu, Some results on longest paths and cycles in K1,3-free graphs, J. Changsha Railway Inst. 4 (1986) 105–106.

[5] O. Ore, Notes on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55. https://doi.org/10.2307/2308928

[6] S. Win, Existenz von Gerüsten mit vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg 43 (1975) 263–267. https://doi.org/10.1007/BF02995957