Spanning $k$-trees of Bipartite Graphs
Open Access
- 2 January 2015
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 22 (1) , P1.13
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 (k-1)|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 |H|-1$, then $H$ has a spanning $k$-tree. Thus our theorem shows that the condition becomes much weaker if the graph is bipartite.
Keywords
This publication has 5 references indexed in Scilit:
- Spanning Trees: A SurveyGraphs and Combinatorics, 2010
- On a k-Tree Containing Specified Leaves in a GraphGraphs and Combinatorics, 2006
- Spanning Trees of Bounded DegreeThe Electronic Journal of Combinatorics, 2001
- Spanning trees with bounded degreesCombinatorica, 1991
- Existenz von Gerüsten mit vorgeschriebenem Maximalgrad in GraphenAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1975