Spanning \(k\)-trees of bipartite graphs (Q490315)

Summary: A tree is called a \(k\)-tree if its maximum degree is at most \(k\). We prove the following theorem. Let \(k \geq 2\) be an integer, and \(G\) be a connected bipartite graph with bipartition \((A,B)\) such that \(|A| \leq |B| \leq (k-1)|A|+1\). If \(\sigma_k(G) \geq |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 \textit{S. Win} [Abh. Math. Semin. Univ. Hamb. 43, 263--267 (1975; Zbl 0309.05122)] that if a connected graph \(H\) satisfies \(\sigma_k(H) \geq |H|-1\), then \(H\) has a spanning \(k\)-tree. Thus our theorem shows that the condition becomes much weaker if the graph is bipartite.