A note on the number of spanning trees in a prism graph

Abstract

In Vol. 21, pp. 229-243 of this journal Boesch and Bogdanowicz showed that the number of spanning trees in the prism graph P _n , a graph usually denoted by K ₂ × C _n , is equal to (n/2) [(2 + √3) ⁿ + (2 − √3) ⁿ − 2]. We give a new and short proof of this formula and mention a few relations with the existing literature.

Keywords:

• Graph theory
• prism
• spanning trees
• circulants
• Chebyshev polynomials

C.R. Categories:

• G.2.2.2
• G.2.1