DMGT

Article in volume

Authors:

M. Furuya

Michitaka Furuya

College of Liberal Arts and Sciences,
Kitasato University,
1-15-1 Kitasato, Minami-ku, Sagamihara, Kanagawa 252-0373, Japan

email: michitaka.furuya@gmail.com

0000-0003-0991-6122

S. Maezawa

Shun-ichi Maezawa

Graduate School of Environment and Information Sciences,
Yokohama National University,
79-1 Tokiwadai, Hodogaya-ku, Yokohama, Kanagawa 240-8501, Japan

email: maezawa-shunichi-bg@ynu.jp

0000-0003-1607-8665

R. Matsubara

Ryota Matsubara

Department of Mathematics,
Shibaura Institute of Technology,
307 Fukasaku, Minuma-ku, Saitama 337-8577, Japan

email: ryota@sic.shibaura-it.ac.jp

H. Matsuda

Haruhide Matsuda

Department of Mathematics,
Shibaura Institute of Technology,
307 Fukasaku, Minuma-ku, Saitama 337-8577, Japan

email: hmatsuda@sic.shibaura-it.ac.jp

0000-0003-2022-619X

S. Tsuchiya

Shoichi Tsuchiya

School of Network and Information,
Senshu University,
2-1-1 Higashimita, Tama-ku, Kawasaki-shi, Kanagawa 214-8580, Japan

email: s.tsuchiya@isc.senshu-u.ac.jp

0000-0001-9006-5120

T. Yashima

Takamasa Yashima

Depatment of Mathmatics,
Keio University,
3-14-1 Hiyoshi, Kohoku-ku, Yokohama-shi, Kanagawa 223-8522, Japan

email: takamasa.yashima@gmail.com

0000-0002-3378-4740

Title:

Degree sum condition for the existence of spanning $\boldsymbol{k}$-trees in star-free graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 42(1) (2022) 5-13

Received: 2018-02-12 , Revised: 2019-04-05 , Accepted: 2019-06-10 , Available online: 2021-11-29 , https://doi.org/10.7151/dmgt.2234

Abstract:

For an integer $k \geq 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 \geq 3$, every connected $K_{1,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 $K_{1,k+1}$-free graphs. In particular, we show that every connected $K_{1,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

References:

H.J. Broersma, Hamilton Cycles in Graphs and Related Topics (Ph.D. Thesis, University of Twente, 1988).
Y. Caro, I. Krasikov and Y. Roditty, Spanning trees and some edge reconstructible graphs, Ars Combin. 20 A (1985) 109–118.
B. Jackson and N.C. Wormald, $k$-walks of graphs, Australas. J. Combin. 2 (1990) 135–146.
Y. Liu, F. Tian and Z. Wu, Some results on longest paths and cycles in $K_{1,3}$-free graphs, J. Changsha Railway Inst. 4 (1986) 105–106.
O. Ore, Notes on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
https://doi.org/10.2307/2308928
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