The number of spanning trees in a new lexicographic product of graphs

被引：0
作者：
Dong Liang
Feng Li
ZongBen Xu
机构：
[1] Xi’an Jiaotong University,Institute of Information and System Sciences, School of Mathematics and Statistics
[2] Qinghai Normal University,College of Computer Science
[3] Xi’an Jiaotong University,Ministry of Education key Lab for Intelligent Networks and Network Security
来源：
Science China Information Sciences | 2014年 / 57卷
关键词：
spanning trees; lexicographic product; Laplacian matrix; reliable network; graph;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The problem of counting the number of spanning trees is an old topic in graph theory with important applications to reliable network design. Usually, it is desirable to put forward a formula of the number of spanning trees for various graphs, which is not only interesting in its own right but also in practice. Since some large graphs can be composed of some existing smaller graphs by using the product of graphs, the number of spanning trees of such large graph is also closely related to that of the corresponding smaller ones. In this article, we establish a formula for the number of spanning trees in the lexicographic product of two graphs, in which one graph is an arbitrary graph G and the other is a complete multipartite graph. The results extend some of the previous work, which is closely related to the number of vertices and Lapalacian eigenvalues of smaller graphs only.
引用
收藏
页码：1 / 9
页数：8
相关论文
共 40 条
[1]  
Cayley A(1889)A theorem on trees Quart J Math 23 276-278
[2]  
Ho J(2013)Wavelet Bayesian network image denoising IEEE Trans Image Process 22 1277-1290
[3]  
Hwang W(2009)Parallel splash belief propagation J Mach Learn Res 1 1-48
[4]  
Gonzalez J(1981)Maximizing the total number spanning trees in a graph: two related problems in graph theory and optimization design theory J Combin Theory B 31 240-248
[5]  
Low Y(2011)Heavy cycles and spanning trees with few leaves in weighted graphs Appl Math Lett 24 908-910
[6]  
Guestrin C(1995)On the number of spanning trees of some composite graphs (in Chinese) Acta Math Sci 15 259-268
[7]  
Cheng C(2000)The number of spanning trees in circulant graphs Discrete Appl Math 223 337-350
[8]  
Li B L(1986)Spanning tree formulas and Chebyshev polynomials Graph Combinator 2 191-200
[9]  
Zhang S G(2000)On the number of spanning trees of a multi-complete/star related graphs Inform Process Lett 76 113-119
[10]  
Huang Z(1996)Laplacian spectra and spanning trees of threshold graphs Discrete Math 65 255-273
1234