A spanning tree with at most \(k\) leaves in a \(K_{1,p}\)-free graph

Kenta Ozeki ; Masao Tsugaki

The electronic journal of combinatorics, Tome 30 (2023) no. 4

Résumé

For an integer $k \geq 2$, a tree is called a $k$-ended tree if it has at most $k$ leaves. It was shown that some $\sigma_{k+1}(G)$ conditions assure the existence of a spanning $k$-ended tree in a connected $K_{1,p}$-free graph $G$ for the pairs $(p,k)$ with $p \leq 4$, or $p= 5$ and $k=4,6$, where $\sigma_{k+1}(G)$ is the minimum degree sum of pairwise non-adjacent $k+1$ vertices of $G$. In this paper, we extend those results to the case with any integer $p \geq 3$ by proving that for any $k \geq 2$ and $p \geq 3$, there exists a constant $f(p,k)$ depending only on $k$ and $p$ such that if a connected $K_{1,p}$-free graph satisfies $\sigma_{k+1}(G) \ge |G|+ f(p,k)$, then $G$ has a spanning $k$-ended tree. The coefficient $1$ of $|G|$ in the $\sigma_{k+1}(G)$ condition is best possible.

Détail

DOI : 10.37236/11698

Classification : 05C05, 05C35, 05C45
Mots-clés : \(k\)-ended tree, Hamiltonian path