A Sufficient Condition for the Existence of Two Completely Independent Spanning Trees
摘要
Completely independent spanning trees play an important role in security protection routing and enhancing the robustness of ad hoc networks. In a graph G, a collection of k spanning trees is termed completely independent spanning trees if the paths connecting any pair of vertices x and y in these distinct trees are internally disjoint. Fan (1984) [10] proposed a sufficient condition for the existence of Hamilton cycles. Based on Fan’s result, we derive a sufficient condition for the existence of two CISTs and identify the graphs that satisfy Fan’s condition but do not contain two CISTs.