Computer Science ›› 2017, Vol. 44 ›› Issue (6): 94-96.doi: 10.11896/j.issn.1002-137X.2017.06.016

Previous Articles     Next Articles

Research on Completely Independent Spanning Trees Based on Degree of Vertices

LIN Cheng-kuan, ZHAO Yuan, FAN Jian-xi and CHENG Bao-lei   

  • Online:2018-11-13 Published:2018-11-13

Abstract: In the interconnection network of computers,completely independent spanning trees(CISTs) play an important role in the aspects such as reliable transmission,parallel transmission,secure distribution and others of information.Supposing that there exist n spanning trees which are T1,T2,…,Tn in a graph G,for any pair of vertices u and v in G,if the paths from u to v are node-disjoint in the n trees,T1,T2,…,Tn are called CISTs in G.In 2005,Chang et al.[1] gave the proof that for graphs of order n with n≥6,if the minimum degree is at least n-2,there are at least n/3 CISTs in G.Based on the result of Chang et al.,we further studied the relation between vertex degree and number of CISTs in G.For any graph of order n with n≥5,if the minimum degree of vertices is at least n-2,the equation between the number of vertices whose degree is n-2,the number of vertices whose degree is n-1 and the number of CISTs can be obtained.The correctness of the equation was also proved,improving the result in paper [1].

Key words: Completely independent spanning trees,Reliable transmission,Interconnection network,Graph

[1] CHANG H Y,WANG H L,YANG J S,et al.A note on the degree condition of completely independent spanning trees[J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,2015,8(10):2191-2193.
[2] HSU L H,LN C K.Graph theory and interconnection networks[M].CRC press,2008.
[3] HASUNUMA T.Completely independent spanning trees in the underlying graph of a linegraph[J].Discrete Math.,2001,4(1-3):149-157.
[4] HASUNUMA T.Completely independent spanning trees in ma-ximal planar graphs[J].Proceedings of 28th Graph Theore-tic Concepts of Computer Science (WG2002),2002,3:235-245.
[5] ARAKI T.Dirac’s condition for completely independent span-ning trees[J].Graph Theor.,2014,7(3):171-179.
[6] FAN G,HONG Y,LIU Q.Ore’s condition for completely independent spanning trees[J].Discrete Appl.Math.,2014,7(177):95-100.
[7] ROSE K H.离散数学及其应用(第七版)[M].徐六福,等译.北京:机械工业出版社,2014:552.
[8] PAI K J,TANG S M,CHANG J M,et al.Completely indepen-dent spanning trees on complete graphs,complete bipartite graphs and complete tripartite graphs[M]∥Advances in Intelligent Systems and Applications-Volume 1.Springer Berlin Heidelberg,2013:107-113.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .