On large $k$-ended trees in connected graphs

Abstract

A vertex of degree one is called an end-vertex, and an end-vertex of a tree is called a leaf. A tree with at most $k$ leaves is called a $k$-ended tree. For a positive integer $k$, let $t_k$ be the order of a largest $k$-ended tree. Let ${\sigma }_m$ be the minimum degree sum of an independent set of $m$ vertices. The main result (Theorem 2) provides a lower bound for $t_{k+1}$ in terms of ${\sigma }_m$ and relative orders: if $G$ is a connected graph and $k$, $\lambda$, $m$ are positive integers with $2\le m\le \min \{k,\lambda \}+1$ then either $t_{k+1}\ge {\sigma }_m+\lambda (k-m+1)+1$ or $t_k\ge t_{k+1}-\lambda +1$.

arXiv comment15 pages, major revision-2