On complexity of cyclic coverings of graphs

2018/11/09 by Young Soo Kwon, Alexander Mednykh, Kwon, Y. S. +3
Computer Science · Mathematics · #05C30 #39A10 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1811.03801

openalex publication_date 2018/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

By complexity of a finite graph we mean the number of spanning trees in the graph. The aim of the present paper is to give a new approach for counting complexity τ(n) of cyclic n-fold coverings of a graph. We give an explicit analytic formula for τ(n) in terms of Chebyshev polynomials and find its asymptotic behavior as n→∞ through the Mahler measure of the associated voltage polynomial. We also prove that F(x)=∑_n=1^∞τ(n)xⁿ is a rational function with integer coefficients.

Citations

• A survey of the theory of hypercube graphs

Related

• Complexity of the circulant foliation over a graph
• On the complexity of Cayley graphs on a dihedral group
• Spanning Trees and Mahler Measure
• On the Computational Complexity of Local and Global Covering Numbers
• On Jacobian group and complexity of the generalized Petersen graph GP(n,k) through Chebyshev polynomials