期刊
GRAPHS AND COMBINATORICS
卷 38, 期 6, 页码 -出版社
SPRINGER JAPAN KK
DOI: 10.1007/s00373-022-02585-w
关键词
Completely independent spanning trees (CISTs); Spanning trees; Bipartite graphs; Minimum degree
类别
资金
- National Natural Science Foundation of China [61402317]
- Shanxi Province Science Foundation [201901D111253]
- Scientific and Technological Innovation Team of Shanxi Province [201805D131007]
- Taiyuan University of Science and Technology Doctoral Fund [20202058]
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.
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|.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据