DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

M. Furuya, S. Maezawa, R. Matsubara, H. Matsuda, S. Tsuchiya, T. Yashima

Title:

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

Source:

Discussiones Mathematicae Graph Theory

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

Abstract:

For an integer $k \geq 2$, a $k${\it-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${\it-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

PDF
Close