完全二部图K_n,n的线图中的完全独立生成树

Completely Independent Spanning Treesin the Line Graph of Complete BipartiteGraph K_n,n

摘要: 连接不同顶点u和的两条路径P₁和P₂，若它们没有共同的内部顶点，则称为公开不相交的。 设T₁,T₂,...,T_k是G的生成树。如果对于每一对不同的顶点u,v∈V(G)，在T₁,T₂,...,T_k中从u到v的 路径两两公开不相交，则称T₁,T₂,...,T_k为G中的完全独立生成树。关于完全独立生成树，我们 关心的问题是图中最多可以存在多少棵完全独立生成树。对于线图，Hasunuma证明了对于任 意n≥4，L(K_n)中存在[n+1/2]棵完全独立生成树，并且进一步地，当n=4或n为奇数时，L(K_n)一v (对任意顶点v）中仍存在[n+1/2]棵完全独立生成树；当n（n≥6）为偶数时，L(K_n)一V(P)（对任 意阶至多n/2的诱导路径P）中仍存在[n+1/2]棵完全独立生成树。在本文中，我们将Hasumuma的想 法推广至K_n,n的线图，并得到：对于任意n≥3，L(K_n,n)中存在[n+1/2]棵完全独立生成树，进一步 地，当n为奇数时，L(K_n,n)一v（对任意顶点v）中仍存在[n+1/2]棵完全独立生成树；当n为偶数时， L(K_n,n)一V(P)（对任意阶至多n的诱导路径P）中仍存在[n+1/2]棵完全独立生成树。

Abstract: Two paths P₁ and P₁ between distinct vertices u and v are called openly disjoint if they have no internal vertices in common. Let T₁,T₂,...,T_k be spanning trees of G. If for each pair of distinct vertices u,v∈V(G), the paths from u to v in T₁,T₂,...,T_k are pairwise openly disjoint, then T₁,T₂,...,T_k are called completely independent spanning trees in G. Regarding completely independent spanning tree, the question we are concerned with is the maximum number of completely independent spanning trees that can exist in a graph. For line graphs, Hasunuma showed that for any n≥4, there are [n+1/2] completely independent spanning trees in L(K_n), and further, [n+1/2] completely independent spanning trees still exist in L(K_n)一v for any vertex v when n = 4 or n is odd and in L(K_n)一V(P) for any induced path P of order at most n/2 when n (≥6) is even. In this paper, we apply Hasunuma's idea to the line graph of K_n,n and obtain that, for any n≥3, there are [n+1/2] completely independent spanning trees in L(K_n,n), and further,[n+1/2] completely independent spanning trees still exist in L(K_n,n)一v for any vertex v when n is odd and in L(K_n,n)一V(P) for any induced path P of order at most n when n is even.