- Tytuł:
- Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs
- Autorzy:
-
Furuya, Michitaka
Maezawa, Shun-ichi
Matsubara, Ryota
Matsuda, Haruhide
Tsuchiya, Shoichi
Yashima, Takamasa - Powiązania:
- https://bibliotekanauki.pl/articles/32361756.pdf
- Data publikacji:
- 2022-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
spanning tree
k -tree
star-free
degree sum condition - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 5-13
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł