On k-ended spanning and dominating trees

الأصل · EN

A tree with at most k leaves is called a k-ended tree. A spanning 2-ended tree is a Hamilton path. A Hamilton cycle can be considered as a spanning 1-ended tree. The earliest result concerning spanning trees with few leaves states that if k is a positive integer and G is a connected graph of order n with d(x)+d(y)≥ n-k+1 for each pair of nonadjacent vertices x,y, then G has a spanning k-ended tree. In this paper, we improve this result in two ways, and an analogous result is proved for dominating k-ended trees based on the generalized parameter tₖ - the order of a largest k-ended tree. In particular, t₁ is the circumference (the length of a longest cycle), and t₂ is the order of a longest path.