×

The number of spanning trees in a new lexicographic product of graphs. (English) Zbl 1398.05111

Summary: 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 Laplacian eigenvalues of smaller graphs only.

MSC:

05C30 Enumeration in graph theory
05C76 Graph operations (line graphs, products, etc.)
05C05 Trees
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Cayley, A., A theorem on trees, Quart J Math, 23, 276-278, (1889)
[2] Ho, J.; Hwang, W., Wavelet Bayesian network image denoising, IEEE Trans Image Process, 22, 1277-1290, (2013) · Zbl 1373.94163
[3] Ou, W. H.; You, X. G.; Cheung, Y. M.; etal., Structured sparse coding for image representation based on L1-graph, 3220-3223, (2012)
[4] Gonzalez, J.; Low, Y.; Guestrin, C., Parallel splash belief propagation, J Mach Learn Res, 1, 1-48, (2009)
[5] Cheng, C., 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, (1981) · Zbl 0475.05050
[6] Li, B. L.; Zhang, S. G., Heavy cycles and spanning trees with few leaves in weighted graphs, Appl Math Lett, 24, 908-910, (2011) · Zbl 1214.05058
[7] Huang, Z.; Li, X., On the number of spanning trees of some composite graphs (in Chinese), Acta Math Sci, 15, 259-268, (1995) · Zbl 0900.05006
[8] Li X, Huang Z. On the Number of Spanning Trees of Graphs and Applications of Networks. Harbin: Harbin Institute of Technology Press, 1999
[9] Zhang, Y.; Yong, X.; Golin, M. J., The number of spanning trees in circulant graphs, Discrete Appl Math, 223, 337-350, (2000) · Zbl 0969.05036
[10] Biggs N. Algebraic Graph Theory. 2nd ed. Cambridge: Cambridge University Press, 1993
[11] Boesch, F.; Prodinger, H., Spanning tree formulas and Chebyshev polynomials, Graph Combinator, 2, 191-200, (1986) · Zbl 0651.05028
[12] Boesch, F.; Wang, J. F., A conjecture on the number of spanning trees in the square of a cycle, 1-16, (1982), New York
[13] Chung, K. L.; Yan, W. M., On the number of spanning trees of a multi-complete/star related graphs, Inform Process Lett, 76, 113-119, (2000) · Zbl 1339.05189
[14] Gilbert, B.; Kelman, A. K., Laplacian spectra and spanning trees of threshold graphs, Discrete Math, 65, 255-273, (1996) · Zbl 0860.05055
[15] Imrich, W.; Izbicki, H., Associative products of graphs, Monatsh Math, 80, 277-281, (1975) · Zbl 0328.05136
[16] Zhang, Z.; Zhu, Y. F., Cyclic arc-connectivity in a Cartesian product digraph, Appl Math Lett, 23, 796-800, (2010) · Zbl 1215.05142
[17] Li, F.; Peng, Y.; Zhao, H. X., On the number of spanning trees of the multi-lexicographic product of networks (in Chinese), Software, 7, 51-53, (2011)
[18] Li, F.; Xu, Z. B.; Zhao, H. X.; etal., On the number of spanning trees of the lexicographic product of networks, Scientia Sin Inform, 42, 949-959, (2012)
[19] Li, F.; Wang, W.; Xu, Z. B.; etal., Some results on the lexicographic product of vertex-transitive graphs, Appl Math Lett, 24, 1924-1926, (2011) · Zbl 1234.05192
[20] Yegnanarayanan, V.; Thiripurasundari, P. R., On some graph operations and related applications, Electron Notes Discrete Math, 33, 123-130, (2009) · Zbl 1267.05226
[21] Moon J. Enumerating Labelled Trees, Graph Theory and Theoretical Physics. New York: New York Academic Press, 1967. 261-272
[22] Kelman, A. K.; Chelnokov, V. M., A certain polynomials of a graph and graphs with an extremal number of trees, J Combin Theory B, 16, 197-214, (1974) · Zbl 0277.05104
[23] Wang, W.; Li, F.; Lu, H. L.; etal., Graphs determined by their generalized characteristic polynomials, Linear Algebra Appl, 434, 1378-1387, (2011) · Zbl 1205.05113
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.