字典乘积网络的支撑树计数
摘要
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.