
Mikio Kano

Kenta Ozeki

Kazuhiro Suzuki

Masao Tsugaki

Tomoki Yamashita
Keywords:
spanning tree, spanning $k$tree, bipartite graph
Abstract
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 \le B \le (k1)A+1$. If $\sigma_k(G) \ge 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) \ge H1$, then $H$ has a spanning $k$tree. Thus our theorem shows that the condition becomes much weaker if the graph is bipartite.