https://doi.org/10.1140/epjp/i2014-14146-7
Regular Article
Generating formulas of the number of spanning trees of some special graphs
1
Department of Mathematics, Faculty of Science, Taibah University, 344, Al-Madinah, Saudi Arabia
2
Department of Mathematics, Faculty of Science, Minufiya University, 32511, Shibin El Kom, Egypt
* e-mail: salamadaoud@gmail.com
Received:
12
May
2014
Revised:
3
June
2014
Accepted:
3
June
2014
Published online:
9
July
2014
Boesh and Prodinger (J. Graphs Comb. 2, 191 (1986)) illustrated how to use the properties of Chebyshev polynomials to calculate the associated determinants and derived closed formula for the number of spanning trees of graphs. In this paper, we extend this idea and describe how to use Chebyshev polynomials to calculate the number of spanning trees (the complexity) in a graph G , when G belongs to one of the following different classes of graphs: i) Grid graph; ii) torus graph; iii) cylinder graph; iv) lattice graph; v) hypercube graph; and vi) stacked book graph.
© Società Italiana di Fisica and Springer-Verlag Berlin Heidelberg, 2014