Generating formulas of the number of spanning trees of some special graphs

S. N. Daoud

doi:10.1140/epjp/i2014-14146-7

EPJ

Generating formulas of the number of spanning trees of some special graphs

S. N. Daoud¹^,2^*

¹ Department of Mathematics, Faculty of Science, Taibah University, 344, Al-Madinah, Saudi Arabia
² Department of Mathematics, Faculty of Science, Minufiya University, 32511, Shibin El Kom, Egypt

Received: 12 May 2014
Revised: 3 June 2014
Accepted: 3 June 2014
Published online: 9 July 2014

Abstract

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.