Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs
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 e...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2022-02-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2234 |
| _version_ | 1827840330934779904 |
|---|---|
| author | Furuya Michitaka Maezawa Shun-ichi Matsubara Ryota Matsuda Haruhide Tsuchiya Shoichi Yashima Takamasa |
| author_facet | Furuya Michitaka Maezawa Shun-ichi Matsubara Ryota Matsuda Haruhide Tsuchiya Shoichi Yashima Takamasa |
| author_sort | Furuya Michitaka |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T07:32:32Z |
| format | Article |
| id | doaj.art-5cd98b7366c048698d83ce7b5e64ea4a |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:32:32Z |
| publishDate | 2022-02-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-5cd98b7366c048698d83ce7b5e64ea4a2023-09-02T21:43:01ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922022-02-0142151310.7151/dmgt.2234Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free GraphsFuruya Michitaka0Maezawa Shun-ichi1Matsubara Ryota2Matsuda Haruhide3Tsuchiya Shoichi4Yashima Takamasa5College of Liberal Arts and Sciences, Kitasato University, 1-15-1 Kitasato, Minami-ku, Sagamihara, Kanagawa 252-0373, JapanGraduate School of Environment and Information Sciences, Yokohama National University, 79-1 Tokiwadai, Hodogaya-ku, Yokohama, Kanagawa 240-8501, JapanDepartment of Mathematics, Shibaura Institute of Technology, 307 Fukasaku, Minuma-ku, Saitama 337-8577, JapanDepartment of Mathematics, Shibaura Institute of Technology, 307 Fukasaku, Minuma-ku, Saitama 337-8577, JapanSchool of Network and Information, Senshu University, 2-1-1 Higashimita, Tama-ku, Kawasaki-shi, Kanagawa 214-8580, JapanDepatment of Mathmatics, Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama-shi, Kanagawa 223-8522, JapanFor 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.https://doi.org/10.7151/dmgt.2234spanning treek-treestar-freedegree sum condition05c0505c50 |
| spellingShingle | 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 spanning tree k-tree star-free degree sum condition 05c05 05c50 |
| title | Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs |
| title_full | Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs |
| title_fullStr | Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs |
| title_full_unstemmed | Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs |
| title_short | Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs |
| title_sort | degree sum condition for the existence of spanning k trees in star free graphs |
| topic | spanning tree k-tree star-free degree sum condition 05c05 05c50 |
| url | https://doi.org/10.7151/dmgt.2234 |
| work_keys_str_mv | AT furuyamichitaka degreesumconditionfortheexistenceofspanningktreesinstarfreegraphs AT maezawashunichi degreesumconditionfortheexistenceofspanningktreesinstarfreegraphs AT matsubararyota degreesumconditionfortheexistenceofspanningktreesinstarfreegraphs AT matsudaharuhide degreesumconditionfortheexistenceofspanningktreesinstarfreegraphs AT tsuchiyashoichi degreesumconditionfortheexistenceofspanningktreesinstarfreegraphs AT yashimatakamasa degreesumconditionfortheexistenceofspanningktreesinstarfreegraphs |