×

The number of spanning trees in the composition graphs. (English) Zbl 1407.05131

Summary: Using the composition of some existing smaller graphs to construct some large graphs, the number of spanning trees and the Laplacian eigenvalues of such large graphs are also closely related to those of the corresponding smaller ones. By using tools from linear algebra and matrix theory, we establish closed formulae for the number of spanning trees of the composition of two graphs with one of them being an arbitrary complete 3-partite graph and the other being an arbitrary graph. Our results extend some of the previous work, which depend on the structural parameters such as the number of vertices and eigenvalues of the small graphs only.

MSC:

05C30 Enumeration in graph theory
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boesch, F. T.; Prodinger, H., Spanning tree formulas and chebyshev polynomials, Graphs and Combinatorics, 2, 1, 191-200 (1986) · Zbl 0651.05028
[2] Boesch, F. T.; Satyanarayana, A.; Suffel, C. L., A survey of some network reliability analysis and synthesis results, Networks, 54, 2, 99-107 (2009) · Zbl 1200.90057
[3] Cayley, A., A theorem on trees, Quarterly Journal of Mathematics, 23, 276-278 (1889)
[4] Petingi, L.; Boesch, F.; Suffel, C., On the characterization of graphs with maximum number of spanning trees, Discrete Mathematics, 179, 1-3, 155-166 (1998) · Zbl 0895.05052
[5] Zhang, Y.; Yong, X.; Golin, M. J., The number of spanning trees in circulant graphs, Discrete Mathematics, 223, 1-3, 337-350 (2000) · Zbl 0969.05036
[6] Chung, K.-L.; Yan, W.-M., On the number of spanning trees of a multi-complete/star related graph, Information Processing Letters, 76, 3, 113-119 (2000) · Zbl 1339.05189
[7] Gilbert, B.; Myrvold, W., Maximizing spanning trees in almost complete graphs, Networks, 30, 2, 97-104 (1997) · Zbl 0885.90109
[8] Hammer, P. L.; Kelmans, A. K., Laplacian spectra and spanning trees of threshold graphs, Discrete Applied Mathematics, 65, 1-3, 255-273 (1996) · Zbl 0860.05055
[9] Kelmans, A. K.; Chelnokov, V. M., A certain polynomial of a graph and graphs with an extremal number of trees, Journal of Combinatorial Theory B, 16, 3, 197-214 (1974) · Zbl 0277.05104
[10] Yegnanarayanan, V.; Thiripurasundari, P. R.; Padmavathy, T., On some graph operations and related applications, Electronic Notes in Discrete Mathematics, 33, 123-130 (2009) · Zbl 1267.05226
[11] Li, F.; Xu, Z. B.; Zhao, H. X.; Wang, W., On the number of spanning trees of the lexicographic product of netwoks, Scientia Sinica Informationis, 42, 949-959 (2012)
[12] Fiedler, M., Eigenvalues of nonnegative symmetric matrices, Linear Algebra and Its Applications, 9, 119-142 (1974) · Zbl 0322.15015
[13] Cardoso, D. M.; Gutman, I.; Martins, E. A.; Robbiano, M., A generalization of fiedler’s lemma and some applications, Linear and Multilinear Algebra, 59, 8, 929-942 (2011) · Zbl 1222.05148
[14] Xu, Z. B.; Li, F.; Zhao, H. X., On the vertex-forwarding index of the lexicographic product of graphs
[15] Li, F.; Wang, W.; Xu, Z.; Zhao, H., Some results on the lexicographic product of vertex-transitive graphs, Applied Mathematics Letters, 24, 11, 1924-1926 (2011) · Zbl 1234.05192
[16] Wang, W.; Li, F.; Lu, H.; Xu, Z., Graphs determined by their generalized characteristic polynomials, Linear Algebra and Its Applications, 434, 5, 1378-1387 (2011) · Zbl 1205.05113
[17] Biggs, N., Algebraic Graph Theory (1993), Cambridge, Mass, USA: Cambridge University Press, Cambridge, Mass, USA
[18] Huang, Z.; Li, X., On the number of spanning trees of some composite graphs, Acta Mathematics Scientia, 15, 3, 259-268 (1995) · Zbl 0900.05006
[19] Moon, J., Enumerating Labelled Trees (1967), New York, NY, USA: Graph Theory and Theoretical Physics, Academic Press, New York, NY, USA · Zbl 0204.24502
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.