The number of spanning trees in circulant graphs, its arithmetic\n properties and asymptotic

2017/10/31 by Alexander Mednykh, Mednykh, Alexander, I. A. Mednykh +1 · 2 citations
Mathematics · Physics and Astronomy · #05C30 #39A10 #Advanced Combinatorial Mathematics #Advanced Mathematical Theories and Applications #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1711.00175

openalex publication_date 2017/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we develop a new method to produce explicit formulas for the\nnumber \τ(n) of spanning trees in the undirected circulant graphs\nC_n(s₁,s₂,\…,s_k) and C_2n(s₁,s₂,\…,s_k,n). Also, we prove\nthat in both cases the number of spanning trees can be represented in the form\n\τ(n)=p ,n ,a(n)², where a(n) is an integer sequence and p is a\nprescribed natural number depending on the parity of n. Finally, we find an\nasymptotic formula for \τ(n) through the Mahler measure of the associated\nLaurent polynomial L(z)=2k-\∑\_i=1^k(z^s_i+z^-s_i).\n

Cited by

• The number of rooted spanning forests of bicirculant graphs
• Chebyshev Recurrence Structures for Reduced Spectral Functions of Cyclic Circulant Graphs

Related

• The number of rooted forests in circulant graphs
• On rationality of generating function for the number of spanning trees in circulant graphs
• A formula for the number of the spanning trees of line graphs
• The spanning tree spectrum: improved bounds and simple proofs
• Complexity of the circulant foliation over a graph