The number of spanning trees in Kn-chain and ring graphs

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 K 5 l constructed by connecting l 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ₙ-ring graphs. The results show that there is a simple relation between the number of spanning trees of the K n -chain graph L n l and the K n -ring graph C n l . 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.