An Innovative Algorithm for Generating Three Completely Independent Spanning Trees in Folded Hypercube Networks

Let G be a simple undirected graph, a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any two vertices [Formula: see text], the (u, v)-paths in these trees have neither vertex nor edge in common, except u and v. Hasunuma [ 1 , 2 ] proposed that there are k CISTs in any [Formula: see text]-connected graph. However, Péterfalvi [ 3 ] disproved this by constructing k-connected graphs for [Formula: see text], which doesn’t have two CISTs. In this paper, we present an algorithm for the construction of three CISTs within the 5-dimensional folded hypercube ([Formula: see text] for short), since [Formula: see text] is 6-connected graph [ 4 ]. Moreover, we also provided an approach to construct three CISTs in any [Formula: see text] where n is greater than 5. In particular, for an [Formula: see text] the diameters of the constructed three CISTs are [Formula: see text].