Constructing two completely independent spanning trees in hypercube-variant networks

Given a graph G, a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any two vertices x,y∈V(G), the paths joining x and y on these trees have neither vertex nor edge in common, except x and y. Hasunuma [9,10] first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Unfortunately, Péterfalvi [16] disproved this conjecture by constructing a k-connected graph, for each k⩾2, which does not have two CISTs. In this paper, we provide a unified approach for constructing two CISTs in several hypercube-variant networks, including hypercubes, locally twisted cubes, crossed cubes, parity cubes, and Möbius cubes. In particular, for an n-dimensional hypercube-variant network, the diameters of the constructed CISTs are 2n−1.