Spanning trees with at most 4 leaves in $K_{1,5}-$free graphs

Pham Hoang Ha, Dang Dinh Hanh

Published 2018-04-25Version 1

A graph $G$ is said to be $K_{1,5}$-free graph if it contains no $K_{1,5}$ as an induced subgraph. Let $\sigma_5(G)$ denote the minimum degree sum of five independent vertices of a graph $G.$ In this article, we will prove that the connected $K_{1,5}$-free graph $G$ has a spanning tree with at most 4 leaves if $\sigma_5(G)\geq |G|-1.$ We also show that the bound $|G|-1$ is sharp. Beside that, a related result also is introduced.