Counting spanning trees in generalized $ K_n $-chain/ring graphs

Sujing Cheng; Jun Ge; Sujing Cheng; Jun Ge

doi:10.3934/math.2026071

AIMS Mathematics

2026, Volume 11, Issue 1: 1701-1711. doi: 10.3934/math.2026071

Previous Article Next Article

Research article Special Issues

Counting spanning trees in generalized $ K_n $-chain/ring graphs

Sujing Cheng ,
Jun Ge ^,

School of Mathematical Sciences, Sichuan Normal University, Chengdu 610068, China

Received: 23 August 2025 Revised: 19 December 2025 Accepted: 06 January 2026 Published: 19 January 2026
MSC : 05C31, 05C70

Let $ K_n $ be the complete graph of order $ n $. Very recently, the number of spanning trees (the $ \mathcal{NST} $ for short) and the resistance distances in $ K_n $-chain (ring) graphs were determined explicitly. We generalized the concept to the generalized $ K_n $-chain (ring) graph $ [L_n^s]^m $ ($ [C_n^s]^m $). New formulae for the $ \mathcal{NST} $ of $ [L_n^s]^m $ and $ [C_n^s]^m $ were given by a simple and more physical way with a novel technique of adding a pair of positive and negative edges, avoiding complicated linear algebraic computations.
- spanning tree,
- generalized $ K_n $-chain/ring graph,
- graph transformation,
- vertex-weighted graph,
- complete split graph
Citation: Sujing Cheng, Jun Ge. Counting spanning trees in generalized $ K_n $-chain/ring graphs[J]. AIMS Mathematics, 2026, 11(1): 1701-1711. doi: 10.3934/math.2026071

Related Papers:

Abstract

Let $ K_n $ be the complete graph of order $ n $. Very recently, the number of spanning trees (the $ \mathcal{NST} $ for short) and the resistance distances in $ K_n $-chain (ring) graphs were determined explicitly. We generalized the concept to the generalized $ K_n $-chain (ring) graph $ [L_n^s]^m $ ($ [C_n^s]^m $). New formulae for the $ \mathcal{NST} $ of $ [L_n^s]^m $ and $ [C_n^s]^m $ were given by a simple and more physical way with a novel technique of adding a pair of positive and negative edges, avoiding complicated linear algebraic computations.

References

[1]	F. T. Boesch, On unreliability polynomials and graph connectivity in reliable network synthesis, J. Graph Theor., 10 (1986), 339–352. https://doi.org/10.1002/jgt.3190100311 doi: 10.1002/jgt.3190100311
[2]	B. Bollobás, Modern graph theory, New York: Springer, 1998. https://doi.org/10.1007/978-1-4612-0619-4
[3]	G. Burde, H. Zieschang, Knots, Berlin, New York: De Gruyter, 2002. https://doi.org/10.1515/9783110198034
[4]	A. Cayley, A theorem on trees, In: The collected mathematical papers, Cambridge University Press, 2009, 26–28. https://doi.org/10.1017/cbo9780511703799.010
[5]	S. J. Cheng, J. Ge, The number of spanning trees in $K_n$-chain and ring graphs, Phys. Scr., 99 (2024), 115236. https://doi.org/10.1088/1402-4896/ad8273 doi: 10.1088/1402-4896/ad8273
[6]	D. Dhar, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett., 64 (1990), 1613–1616. https://doi.org/10.1103/physrevlett.64.1613 doi: 10.1103/physrevlett.64.1613
[7]	D. Dhar, A. Dhar, Distribution of sizes of erased loops for loop-erased random walks, Phys. Rev. E, 55 (1997), R2093. https://doi.org/10.1103/physreve.55.r2093 doi: 10.1103/physreve.55.r2093
[8]	F. M. Dong, J. Ge, Counting spanning trees in a complete bipartite graph which contain a given spanning forest, J. Graph Theor., 101 (2022), 79–94. https://doi.org/10.1002/jgt.22812 doi: 10.1002/jgt.22812
[9]	J. Ge, F. M. Dong, Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs, Discrete Appl. Math., 283 (2020), 542–554. https://doi.org/10.1016/j.dam.2020.02.002 doi: 10.1016/j.dam.2020.02.002
[10]	J. Ge, Y. C. Liao, B. H. Zhang, Resistance distances and the Moon-type formula of a vertex-weighted complete split graph, Discrete Appl. Math., 359 (2024), 10–15. https://doi.org/10.1016/j.dam.2024.07.040 doi: 10.1016/j.dam.2024.07.040
[11]	H. L. Gong, X. Jin, A simple formula for the number of the spanning trees of line graphs, J. Graph Theor., 88 (2018), 294–301. https://doi.org/10.1002/jgt.22212 doi: 10.1002/jgt.22212
[12]	H. L. Gong, Y. Gong, J. Ge, The number of spanning trees in $K_n$-complement of a bipartite graph, J. Algebr. Comb., 60 (2024), 541–554. https://doi.org/10.1007/s10801-024-01341-y doi: 10.1007/s10801-024-01341-y
[13]	A. E. Kennelly, The equivalence of triangles and three-pointed stars in conducting networks, Electrical World and Engineer, 34 (1899), 413–414.
[14]	G. Kirchhoff, Über die Auflösung der Gleichungen auf, welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys.-Berlin, 148 (1847), 497–508. https://doi.org/10.1002/andp.18471481202 doi: 10.1002/andp.18471481202
[15]	Z. Kosar, S. Zaman, W. Ali, A. Ullah, The number of spanning trees in a $K_5$ chain graph, Phys. Scr., 98 (2023), 125239. https://doi.org/10.1088/1402-4896/ad07b9 doi: 10.1088/1402-4896/ad07b9
[16]	D. Y. Li, W. X. Chen, W. G. Yan, Enumeration of spanning trees of complete multipartite graphs containing a fixed spanning forest, J. Graph Theor., 104 (2023), 160–170. https://doi.org/10.1002/jgt.22954 doi: 10.1002/jgt.22954
[17]	D. Y. Li, X. Feng, W. G. Yan, Enumeration of spanning trees with a perfect matching of hexagonal lattices on the cylinder and Möbius strip, Discrete Appl. Math., 358 (2024), 320–325. https://doi.org/10.1016/j.dam.2024.07.026 doi: 10.1016/j.dam.2024.07.026
[18]	S. L. Li, W. G. Yan, T. Tian, Some physical and chemical indices of the Union Jack lattice, J. Stat. Mech., 2015 (2015), P02014. https://doi.org/10.1088/1742-5468/2015/02/p02014 doi: 10.1088/1742-5468/2015/02/p02014
[19]	S. L. Li, W. G. Yan, T. Tian, The spectrum and Laplacian Spectrum of the dice lattice, J. Stat. Phys., 164 (2016), 449–462. https://doi.org/10.1007/s10955-016-1552-6 doi: 10.1007/s10955-016-1552-6
[20]	T. Y. Li, W. G. Yan, Enumeration of spanning trees of 2-separable networks, Physica A, 536 (2019), 120877. https://doi.org/10.1016/j.physa.2019.04.113 doi: 10.1016/j.physa.2019.04.113
[21]	J. D. Noh, H. Rieger, Random walks on complex networks, Phys. Rev. Lett., 92 (2004), 118701. https://doi.org/10.1103/PhysRevLett.92.118701 doi: 10.1103/PhysRevLett.92.118701
[22]	W. S. Sun, M. S. Sardar, Y. J. Yang, S.-J. Xu, On the resistance distance and Kirchhoff index of $K_n$-chain(ring) network, Circuits Syst. Signal Process., 43 (2024), 4728–4749. https://doi.org/10.1007/s00034-024-02709-y doi: 10.1007/s00034-024-02709-y
[23]	E. Teufl, S. Wagner, On the number of spanning trees on various lattices, J. Phys. A: Math. Gen., 43 (2010), 415001. https://doi.org/10.1088/1751-8113/43/41/415001 doi: 10.1088/1751-8113/43/41/415001
[24]	E. Teufl, S. Wagner, Determinant identities for Laplace matrices, Linear Algebra Appl., 432 (2010), 441–457. https://doi.org/10.1016/j.laa.2009.08.028 doi: 10.1016/j.laa.2009.08.028
[25]	L. Versfeld, Remarks on star-mesh transformation of electrical networks, Electron. Lett., 6 (1970), 597–599. https://doi.org/10.1049/el:19700417 doi: 10.1049/el:19700417
[26]	F. Y. Wu, The Potts model, Rev. Mod. Phys., 54 (1982), 235–268. https://doi.org/10.1103/RevModPhys.54.235 doi: 10.1103/RevModPhys.54.235
[27]	T. Yan, Z. Kosar, A. Aslam, S. Zaman, A. Ullah, Spectral techniques and mathematical aspects of $K_4$ chain graph, Phys. Scr., 98 (2023), 045222. https://doi.org/10.1088/1402-4896/acc4f0 doi: 10.1088/1402-4896/acc4f0
[28]	C. L. Yang, T. Tian, Counting spanning trees of multiple complete split-like graph containing a given spanning forest, Discrete Math., 348 (2025), 114300. https://doi.org/10.1016/j.disc.2024.114300 doi: 10.1016/j.disc.2024.114300
[29]	J. Y. Zhang, W. G. Yan, Counting spanning trees of a type of generalized Farey graphs, Physica A, 555 (2020), 124749. https://doi.org/10.1016/j.physa.2020.124749 doi: 10.1016/j.physa.2020.124749
[30]	J. Zhou, C. J. Bu, The enumeration of spanning tree of weighted graphs, J. Algebr. Comb., 54 (2021), 75–108. https://doi.org/10.1007/s10801-020-00969-w doi: 10.1007/s10801-020-00969-w

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)