2024/10/04 by Barabde, R., S. A. Mane, Mane, S. A. +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2410.03379
openalex publication_date 2024/10/04 · openalex created_date 2024/10/31 · openalex updated_date 2026/07/28
A set of \( k \) spanning trees in a graph \( G \) is called a set of completely independent spanning trees (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 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 \( Q6 \) 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 (k)/(2) \rfloor \) CISTs. We also investigate that the hypercube of dimension \( n \) cannot have \( (n)/(2) \) CISTs, which means Hasunuma's conjecture does not hold for the hypercube \( Qn \) when \( n \) is an even integer \(2 < n ≤ 107 \), except when \(n = 2r\) and \( n ∈ \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 \(Qn\) for \(n ≥ 7\). Our results show that Hasunuma's conjecture holds for odd integer \(n = 7\) in \(Qn\), but does not hold for even integer \(n = 6\).