摘要
A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k >= 3. Let G be a graph of order n and let S subset of V(G) with kappa(S) >= 1. Suppose that for every l >= kappa(S), there exists an integer t such that 1 <= t <= (k - 1)l + 2 left perpendicular l- 1/k right perpendicular and the degree sum of any t independent vertices of S is at least n + tl - kl - 1. Then G has a k-tree containing S. We also show some new results on a spanning k-tree as corollaries of the above theorem.
- 出版日期2010-3