非固定步长的无向循环图的支撑树数

The Number of Spanning Trees in the Undirected Circulant Graphs with Non-fixed Jumps

图的支撑树数是图的重要的不变量,也是网络可靠性的重要量度.循环图是一个重要的图类,可应用于局域网和分布系统的设计中.对有固定步长的循环图,其支撑树数已得到了研究.本文考虑有非固定步长的无向循环图Cpn(a1,a2,…,ak,q1n,q2n,…,qmn),这里a1,a2,…,ak,q1,q2,…,qm,n和p都是正整数,a1≤a2≤…≤ak≤n/2,q1≤q2≤…≤qm≤p/2,且n是可变化的,因而有些步长并非固定.给出其支撑树数的一个公式,并得到其渐近性态和常数系数的线性递归关系.

The number of spanning trees is an important invariant of a graph.it is also an important measure of the reliability of a network. The circulant graphs are an important class of graphs, they can be used in the designing of local area networks and distributed systems. For the circulant graphs with fixed jumps,the number of their spanning trees have been studied. In this paper.the undirected circulant graphs with non-fixed jumps Cpn（a1,a2…,ak,q1n,q2n,…,qmn） were considered, where （a1,a2,…,ak,q1,q2,…,qm）. n and p were positive integers,a1≤a2≤…≤ak≤n/2,q1≤q2≤…≤qm≤p/2. and n changes （some steps are non-fixed）. A formula for the number of their spanning trees was given, Furthermore its asymptotic behaviors were considered and the linear recurfence relations with constant coefficients were also obtained.