Spanning Caterpillars Having at Most k Leaves

摘要

A tree is called a caterpillar if all its leaves are adjacent to the same its path, and the path is called a spine of the caterpillar. Broersma and Tuinstra proved that if a connected graph G satisfies σ_2(G) ≥ |G| -k + 1 for an integer k ≥ 2, then G has a spanning tree having at most k leaves. In this paper we improve this result as follows. If a connected graph G satisfies σ_2(G) ≥ |G| -k + 1 and |G| ≥ 3k-10 for an integer k ≥2, then G has a spanning caterpillar having at most k leaves. Moreover, if |G| ≥ 3k - 7, then for any longest path, G has a spanning caterpillar having at most k leaves such that its spine is the longest path. These three lower bounds on σ_2(G) and |G| are sharp.