关键词: 完全独立生成树,可靠传输,互连网络,图

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 T₁,T₂,…,T_n 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,T₁,T₂,…,T_n 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