Minimum Degree Conditions and Optimal Graphs for Completely Independent Spanning Trees

Completely independent spanning trees \(T_1,T_2,\ldots ,T_k\) in a graph G are spanning trees in G such that for any pair of distinct vertices u and v, the k paths in the spanning trees between u and v mutually have no common edge and no common vertex except for u and v. The concept finds applications in fault-tolerant communication problems in a network. Recently, it was shown that Dirac’s condition for a graph to be hamiltonian is also a sufficient condition for a graph to have two completely independent spanning trees. In this paper, we generalize this result to three or more completely independent spanning trees. Namely, we show that for any graph G with \(n \ge 7\) vertices, if the minimum degree of a vertex in G is at least \(n-k\), where \(3 \le k \le \frac{n}{2}\), then there are \(\lfloor \frac{n}{k} \rfloor \) completely independent spanning trees in G. Besides, we improve the lower bound of \(\frac{n}{2}\) on the Dirac’s condition for completely independent spanning trees to \(\frac{n-1}{2}\) except for some specific graph. Our results are theoretical ones, since these minimum degree conditions can be applied only to a very dense graph. We then present constructions of symmetric regular graphs which include optimal graphs with respect to the number of completely independent spanning trees.