Completely independent spanning trees in torus networks
Completely independent spanning trees in torus networks
复制标题
DOI：
10.1002/net.20460
复制
发表时间：
2012-08
期刊：
影响因子：
2.1
通讯作者：
Toru Hasunuma;Chie Morisaka
中科院分区：
文献类型：
--
作者：
Toru Hasunuma;Chie Morisaka
设T1，T2，…，Tk是图G的生成树.如果对G中任意两个顶点u，v，T1，T2，.，Tk中从u到v的路是两两内部不相交的，则T1，T2，.，Tk是G中完全独立的生成树.完全独立的生成树可以应用于互连网络中的容错通信问题。在这篇文章中，我们证明了在任何环面网络中有两个完全独立的生成树。此外，我们还推广了笛卡尔积的结果。特别地，我们证明了在任何2连通图的笛卡尔积中存在两个完全独立的生成树。© 2011 Wiley Periodicals，Inc.网络，2012年
Let T1, T2, …, Tk be spanning trees in a graph G. If for any two vertices u, v in G, the paths from u to v in T1, T2, …, Tk are pairwise internally disjoint, then T1, T2, …, Tk are completely independent spanning trees in G. Completely independent spanning trees can be applied to fault‐tolerant communication problems in interconnection networks. In this article, we show that there are two completely independent spanning trees in any torus network. Besides, we generalize the result for the Cartesian product. In particular, we show that there are two completely independent spanning trees in the Cartesian product of any 2‐connected graphs. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012