Construction and Conditions for Completely Independent Spanning Trees in Hypercubes and Regular Bipartite Graphs

A set of $k$ spanning trees in a graph $G$ is called a set of $\mathit{\text{completely}}\mathit{\text{independent}}\mathit{\text{spanning}}\mathit{\text{trees}}\mathit{\text{(CISTs)}}$ if, for every pair of vertices $x$ and $y$, the paths connecting $x$ and $y$ across different trees do not share any vertices or edges, except for $x$ and $y$ themselves. Hasunuma conjectured that every $2k$-connected graph contains exactly $k$ completely independent spanning trees (CISTs). However, Pétérfalvi disproved this conjecture. When $k=2$, the two CISTs are called a $\mathit{\text{dual-CIST}}$. It has been shown that determining whether a graph can have $k$ CISTs is an NP-complete problem, even when $k=2$. In $2017$, Darties et al. raised the question of whether the $6-$dimensional hypercube $Q_6$ can have three completely independent spanning trees (CISTs). This paper provides an answer to that question. In this paper, we first present a necessary condition for $k$-regular, $k$-connected bipartite graphs to have $\lfloor \frac{k}{2}\rfloor$ CISTs. We also investigate that the hypercube of dimension $n$ cannot have $\frac{n}{2}$ CISTs, which means Hasunuma’s conjecture does not hold for the hypercube $Q_n$ when $n$ is an even integer $2<n\le {10}^7$, except when $n=2^r$ and $n\in \{161038,215326,2568226,3020626,7866046,9115426\}$. This result also resolves a question posed by Darties et al. The construction of multiple CISTs on the underlying graph of a network has practical applications in ensuring the fault tolerance of data transmission. In this context, we also provide a construction for three completely independent spanning trees in the hypercube $Q_n$ for $n\ge 7$. Our results show that Hasunuma’s conjecture holds for odd integer $n=7$ in $Q_n$, but does not hold for even integer $n=6$.