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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Sufficient Condition for the Existence of Two Completely Independent Spanning Trees

  • Yang Hu,
  • Bo Ning,
  • Xiumin Wang

摘要

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.