Progress on sufficient conditions for a graph to have a spanning $k-$ended tree

Abstract

In 1998, Broersma and Tuinstra [J. Graph Theory \textbf{29} (1998), 227-237] proved that if $G$ is a connected graph satisfying ${\sigma }_2(G)\ge |G|-k+1$ then $G$ has a spanning $k-$ended tree. They also gave an example to show that the condition "${\sigma }_2(G)\ge |G|-k+1$" is sharp. In this paper, we introduce a new progress for this result. Let $K_{m,m+k}$ be a complete bipartite graph with bipartition $V(K_{m,m+k})=A\cup B,|A|=m,|B|=m+k.$ Denote by $H$ to be the graph obtained from $K_{m,m+k}$ by adding (or no adding) some edges with two end vertices in $A.$ We prove that if $G$ is a connected graph satisfying ${\sigma }_2(G)\ge |G|-k$ then $G$ has a spanning $k-$ended tree except for the case $G$ is isomorphic to a graph $H.$ As a corollary of our main result, a sufficient condition for a graph to have a few branch vertices is given.

6 pages