科研之友
微信
新浪微博
Facebook
分享链接
摘要
A tree is called a k-tree if its maximum degree is at most k. We prove the following theorem. Let k >= 2 be an integer, and G he a connected bipartite graph with bipartition (A, B) such that |A| <= |B| <= (k - 1) |A| + 1. If sigma(k)(G) >= |B|, then G has a spanning k-tree, where sigma(k)(G) denotes the minimum degree sum of k independent vertices of G. Moreover, the condition on sigma(k) (G) is sharp. It was shown by Win (Abh. Math. Sem. Univ. Hamburg, 43, 263-267, 1975) that if a connected graph H satisfies sigma(k)(H) >= |H| - 1, then H has a spanning k-tree. Thus our theorem shows that the condition becomes much weaker if the graph is bipartite.
- 出版日期2015-1-20
