| Completely independent spanning trees are independent spanning trees rooted at any vertex. In the application to fault-tolerant broadcasting in parallel computers, once we have constructed completely independent spanning trees,then we do not need to reconstruct them when a source vertex is changed to another vertex. Let G be a simple undirected graph, and P1, P2 be paths from a vertex u to a vertex v in G, if P1 and P2 have no common edge and no common vertex except for u and v. Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and υ, the paths from u and υ in T1 and T2 are internally disjoint.In 2013, Toru Araki proved a necessary and sufficient condition for the existence of completely independent spanning trees. In the same article, he showed that Dirac’s condition and Fleischner’s theorem all can be the sufficient conditions for the existence of two completely independent spanning trees. Therefore, he asked whether another sufficient conditions for hamiltonian graphs are also sufficient conditions for the existence of two completely independent spanning trees.In this paper, we prove that it is true for some sufficient conditions for hamil-tonian graphs. Besides, we also show that there are two completely independent spanning trees in the Pyramid networks. |
