Spanning Trees with Few Leaves and Branch Vertices under Degree Conditions

A leaf of a tree is a vertex with degree 1 and a branch vertex of a tree is a vertex with degree at least 3 in the tree. In this paper, we give two sufficient conditions for graphs to have a spanning tree with few total bounded number of leaves and branch vertices. Firstly, by restricting Fan-type degree condition to Formula: see text or Formula: see text of a graph Formula: see text, we prove that a 2-connected graph Formula: see text satisfying Formula: see text for any two nonadjacent vertices Formula: see text and Formula: see text of every induced Formula: see text or Formula: see text in Formula: see text with Formula: see text has a spanning tree with the total number of leaves and branch vertices at most Formula: see text. Secondly, we prove that a connected Formula: see text-free graph Formula: see text with Formula: see text has a spanning tree with the total number of leaves and branch vertices at most Formula: see text for Formula: see text. Moreover, we give examples to show the low bounds of the above degree conditions are best possible.