【摘要】 在计算机互连网络中,完全独立生成树在信息的可靠传输、并行传输、安全分发等方面具有重要的作用。假设图G中存在n棵生成树T₁,T₂,…,T_n,若对于图G中任意两个顶点u和v,满足u和v之间的路径在这n棵树中都是顶点不相交的,则称这n棵树为完全独立生成树（CISTs）。在2015年,Chang等人证明了对于包含n（n≥6）个顶点的任意图G,如果图G的最小顶点度数至少为n-2,那么,G中存在至少n/3棵CISTs^[1]。在Chang等人的基础上,文中继续深入研究了图G中顶点度数和CISTs的棵数之间的关系。对于包含n（n≥5）个顶点的任意图G,假设图G的最小顶点度数至少为n-2,得出度数为n-2的顶点的个数、度数为n-1的顶点的个数与图G中CISTs的棵数之间关系的推导等式,并证明了其正确性,从而改进了文献[1]中的结果。更多还原

【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₂,…,Tnin a graph G,for any pair of vertices uand vin G,if the paths fromuto vare node-disjoint in the ntrees,T₁,T₂,…,Tnare 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/3CISTs 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-1and the number of CISTs can be obtained.The correctness of the equation was also proved,improving the result in paper[1].更多还原