Constructing node-independent spanning trees on the line graph of the hypercube by an independent forest scheme.

Due to the application in reliable communication, reliable broadcasting, secure message distribution, etc., node/edge-independent spanning trees (ISTs) have attracted much attention in the past twenty years. However, node/edge conjecture is still open for networks with node/edge-connectivity ≥ 5. So far, results have been obtained on a lot of special networks, but only a few results are reported on the line graphs of them. Hypercubes play important roles in parallel computing systems, and the line graphs of which have been recently adopted for the architectures of data center networks. Since the line graph of n -dimensional hypercube Q n , L (Q n) , is (2 n − 2) -regular, whether there exist 2 n − 2 node-ISTs rooted at any node on L (Q n) is an open question. In this paper, we focus on the problem of constructing node-ISTs on L (Q n). Firstly, we point out that L (Q n) can be partitioned into 2 n − 1 complete graphs. Then, based on the complete graphs and n − 1 node-ISTs rooted at 0 on Q n − 1 0 , we obtain an "independent forest" containing 2 n − 2 trees on L (Q n). Furthermore, we present an O (N) time algorithm to construct 2 n − 2 node-ISTs rooted at node [0, 2 n − 1 ] isomorphic to each other on L (Q n) based on the independent forest, where N = n × 2 n − 1 is the number of nodes on L (Q n). In addition, we point out that the 2 n − 2 node-ISTs on L (Q n) is a new method to prove the node/edge-connectivity and the upper bound of (2 n − 2) -node/edge-wide-diameter of L (Q n). • We propose the definition of independent forest and use it to solve the node-independent spanning trees (ISTs) problem on L (Q n). • We design an O (N) time algorithm to construct 2 n − 2 node-ISTs rooted at node [0, 2 n − 1 ] in L (Q n) , where N = n × 2 n − 1 is the number of nodes in L (Q n). • The height of the node-ISTs is n + 2 and the trees are isomorphic to each other. • The 2 n − 2 node-ISTs in L (Q n) is a new method to prove the node/edge connectivity and the upper bound of (2 n − 2) -node/edge-wide-diameter of L (Q n). [ABSTRACT FROM AUTHOR]