字典乘积网络的支撑树计数  

On the number of spanning trees of the lexicographic product of networks

作　　者：李峰[1,2] 徐宗本[1,2] 赵海兴[3] 王卫[1,2] 

机构地区：[1]西安交通大学信息与系统科学研究所,西安710049 [2]西安交通大学智能网络与网络安全教育部重点实验室,西安710049 [3]青海师范大学计算机学院,西宁810008

出　　处：《中国科学：信息科学》2012年第8期949-959,共11页Scientia Sinica(Informationis)

基　　金：国家重点基础研究发展计划(批准号:2007CB311002);国家自然科学基金(批准号:70531030)资助项目

摘　　要：支撑树个数是边失效下网络可靠性分析与设计的一个重要性能参考指标,本文利用字典乘积的方法来构建网络,通过这种方法我们很容易由若干特定规模较小网络来构建规模较大的网络,并得到它的一个紧的支撑树计数解析公式,这样的计数公式仅仅依赖于小网络的性能参数,如:结点的度数、小网络的阶数、小网络的支撑树数目.The number of the spanning trees of a network is a very important index in the analysis and synthesis of reliable networks. Usually, it is desirable to give the formulae of the number of spanning trees for various networks, which is not only interesting in its own right but also in practice. Product graphs play a vital role not only in applied mathematics but also in computer science. Since many large networks are composed of some existing smaller networks by using, in terms of graph theory, lexicographic product, the topological invariants and some properties of such large networks are associated strongly with that of the corresponding smaller ones. The number of spanning trees of the Cartesian product of two networks has been studied extensively with more results obtained. However, few results are available for the number of spanning trees of the Lexicographic product of two networks. In this paper, we establish a closed formula for the number of spanning trees of the lexicographic product of two networks. The formula of the number of the spanning trees which depends only on the number of the vertices and the Laplacian eigenvalues of the smaller networks. The results extend some of the previous results and give new closed formulaes of the number of spanning trees for some new family of graphs.

关 键 词：图 网络 支撑树 字典乘积 LAPLACIAN矩阵 

分 类 号：O157.5[理学—数学]