The Existence of Completely Independent Spanning Trees for Some Compound Graphs
Xiao-Wen Qin, Rong‐Xia Hao, Jou–Ming Chang · IEEE Transactions on Parallel and Distributed Systems · 2019
Given two regular graphs G and H such that the vertex degree of G is equal to the number of vertices in H, the compound graph G(H) is constructed by replacing each vertex of G by a copy of Hand replacing each edge of G by an additional edge connecting random vertices in two corresponding copies of H, respectively, under the constraint that each vertex in G(H) is incident with only one additional edge, exactly. L-HSDCmis a compound graph G(H), where G is a hypercube Qmand H is a complete graph Km, which is defined by focusing on the connected relation between servers in the novel data center network HSDCmproposed in [30]. A set of k spanning trees in a graph G are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices x and yin any two trees have neither vertex nor edge in common, except for x and y. In this paper, we give a sufficient condition for the existence of k CISTs in a kind of compound graph. Furthermore, a specific construction algorithm is provided. As corollaries of the main results, the existences of two CISTs form m ≥ 4; three CISTs form m ≥ 8 and four CISTs form m ≥ 10 in L-HSDCm(m) are gotten directly.