The number of spanning trees in K _n-chain and ring graphs

Abstract The problem of counting spanning trees of graphs or networks is a fundamental and crucial area of research in combinatorics, while has numerous important applications in statistical physics, network theory and theoretical computer science. Very recently, Kosar, Zaman, Ali and Ullah obtained a nice formula on the number of spanning trees of a K 5 -chain network <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:msubsup> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> <mml:mrow> <mml:mn>5</mml:mn> </mml:mrow> <mml:mrow> <mml:mi mathvariant="italic">ℓ</mml:mi> </mml:mrow> </mml:msubsup> </mml:math> constructed by connecting ℓ copys of complete graphs K 5 . They made extensive use of matrix theory and spectral graph theory, especially the normalized Laplacian of graphs. In this paper, by using a rather simple and more physical treatment (the mesh-star transformation in electrical network) without any linear algebra, we generalize their result to K n -chain graphs and K n -ring graphs. The results show that there is a simple relation between the number of spanning trees of the K n -chain graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:msubsup> <mml:mrow> <mml:mi>L</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:mrow> <mml:mi mathvariant="italic">ℓ</mml:mi> </mml:mrow> </mml:msubsup> </mml:math> and the K n -ring graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:msubsup> <mml:mrow> <mml:mi>C</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:mrow> <mml:mi mathvariant="italic">ℓ</mml:mi> </mml:mrow> </mml:msubsup> </mml:math> . We also calculate the corresponding tree entropy (or so called ‘the asymptotic growth constant’) and find that the tree entropy of the corresponding K n -chain graphs and K n -ring graphs are totally the same.