The number of spanning trees in a prism

Abstract

Let the vertices of two disjoint, equal length cycles be labelled in one cycle and in the other. The prism P_n is defined as the graph obtained by adding to the disjoint cycles all edges of the form V_iW_i The prism is sometimes denoted by K ₂×C_n . In this work we derive the following simple formula for t(P_n ) the number of spanning trees in .

Keywords:

• Graph theory
• prism
• spanning trees
• circulants

C.R. Categories:

• G.2.2
• G.2.1

^†The work of this author was supported under NSF Grant LCS-8100652

^†The work of this author was supported under NSF Grant LCS-8100652

Notes

^†The work of this author was supported under NSF Grant LCS-8100652