On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes
Xiaorui Li, Baolei Cheng, Jianxi Fan, Yan Wang, Dajin Wang · Fundamenta Informaticae · 2023
A network can contain numerous spanning trees. If two spanning trees T i , T j do not share any common edges, T i and T j are said to be pairwisely edge-disjoint. For spanning trees T 1 , T 2 ,…, T m , if every two of them are pairwisely edge-disjoint, they are called completely edge-independent spanning trees (CEISTs for short). CEISTs can facilitate many network functionalities, and constructing CEISTs as maximally allowed as possible in a given network is a worthy undertaking. In this paper, we establish the maximal number of CEISTs in the locally twisted cube network, and propose an algorithm to construct ⌊ n 2 ⌋ CEISTs in LTQ n , the n -dimensional locally twisted cube. The proposed algorithm has been actually implemented, and we present the outputs. Network broadcasting in the LTQ n was simulated using ⌊ n 2 ⌋ CEISTs, and the performance compared with broadcasting using a single tree.