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



No Suggested Reading articles found!