Answers are grounded in this paper and cite their sources.
Let T 1 , T 2 , … , T k be k spanning trees in a graph G . If for any two vertices u , v of G , the paths from u to v in T 1 , T 2 , … , T k are pairwise edge-disjoint and internal vertex-disjoint, then T 1 , T 2 , … , T k are k completely independent spanning trees (CISTs) of G . The concept of CISTs was first introduced by Hasunuma in 2001. In 2002, Hasunuma further proved that determining whether a graph G contains k CISTs is NP-complete, even for k = 2 . In 2014, Araki raised the question of whether certain known sufficient conditions for Hamiltonian cycles could also guarantee the existence of two CISTs. Inspired by Araki's question and building upon spectral radius-based studies of Hamiltonicity in general graphs, we establish a spectral condition for the existence of CISTs in connected graphs for k = 2 and k = 3 .
No takes yet. Share an insight, caveat, or question.
Hu et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: