Degree Conditions for Completely Independent Spanning Trees of Bipartite Graphs

Let T1, T2,, T-k be k(>= 2) spanning trees of a graph G. The trees T-1, T-2,, T-k are completely independent if the paths connecting any two vertices of G in these k trees are pairwise internally disjoint. Sufficient conditions for a graph to possess k completely independent spanning trees have attracted popular attention intensively. In this paper, we focus on such sufficient conditions for bipartite graphs, and show that a bipartite graph G = (X boolean OR Y, E) with order v = m + n, m = |X| >= 2k and n = |Y| >= m, has k completely independent spanning trees if for every pair of vertices x is an element of X, y is an element of Y, d(x) >= (k-l)n/k + 2, d(y) >= (k-1)m/k + 2. Furthermore, we obtain that a bipartite graph G = (X U Y, E) with order v >= 8, |X| >= 2k and |Y| >= 2k, has k completely independent spanning trees if the minimum degree delta(G) > [3(x2(k-2)-1)nu/3x2(k-1)] +2, or delta(G) >= (k-1)nu/2k + 2 and |X| = |Y|.

Automated summary

This paper focuses on the sufficient conditions for bipartite graphs to possess k completely independent spanning trees. It provides two inequalities for the number of elements and degrees, and when these inequalities are satisfied, the bipartite graph has k completely independent spanning trees.