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

In 1998, Broersma and Tuinstra [J. Graph Theory \textbf{29} (1998), 227-237] proved that if $G$ is a connected graph satisfying $σ_2(G) \geq |G|-k+1$ then $G$ has a spanning $k-$ended tree. They also gave an example to show that the condition "$σ_2(G) \geq |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 $σ_2(G) \geq |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.

No reviews yet.

No comments yet.