Asymptotics and Arithmetical Properties of Complexity for Circulant Graphs

Resumo

Abstract—We study analytical and arithmetical properties of the complexity function for infinite families of circulant C_n(s₁, s_2,…, s_k) C_2n(s₁, s_2,…, s_k, n). Exact analytical formulas for the complexity functions of these families are derived, and their asymptotics are found. As a consequence, we show that the thermodynamic limit of these families of graphs coincides with the small Mahler measure of the accompanying Laurent polynomials.