pith. sign in

arxiv: 1804.09332 · v2 · pith:WGBF5OMQnew · submitted 2018-04-25 · 🧮 math.CO

Spanning trees with at most 4 leaves in K_(1,5)-free graphs

classification 🧮 math.CO
keywords freeconnectedleavessigmaspanningcontainseverygraph
0
0 comments X
read the original abstract

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with $\sigma_4(G)\geq n-1$ contains a spanning tree with at most $3$ leaves. In this paper, we prove an analogue of Kyaw's result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with $\sigma_5(G)\geq n-1$ contains a spanning tree with at most $4$ leaves. Moreover, the degree sum condition `$\sigma_5(G)\geq n-1$' is best possible.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.