On k-E nded Spanning and Dominating Trees - Nikoghosyan, Zhora G. (Mathematical Problems of Computer Science, 2021)
A tree with at most k leaves is called a k-ended tree. Let tk be the order of a largest k-ended tree in a graph. A tree T of a graph G is said to be dominating if V (G - T) is an independent set of vertices. The minimum degree sum of any pair (triple) of nonadjacent vertices in G will be denoted by σ2 (σ 3). The earliest result concerning spanning trees with few leaves (by the author, 1976) states: (*) if G is a connected graph of order n with σ2 ≥ n-k +1 for some positive integer k, then G has a spanning k-ended tree. In this paper we show: (i) the connectivity condition in (*) can be removed; (ii) the condition σ2 ≥ n - k + 1 in (*) can be relaxed by replacing n with tk+1; (iii) if G is a connected graph with σ3 ≥ tk+1 - 2k + 4 for some integer k ≥ 2, then G has a dominating k-ended tree. All results are sharp.