Complexity of circulant graphs with non-fixed jumps, its arithmetic properties and asymptotics

Abstract

In the present paper, we investigate a family of circulant graphs with non-fixed jumps

G_n= C_βn(s₁, ... , s_k, α₁n, ... , α_ln), 1 ≤ s₁< ... < s_k≤ [βn/2], 1 ≤ α₁< ... < α_l ≤ [β/2]. 

Here n is an arbitrary large natural number and integers s₁, ... , s_k, α₁, ... , α_l are supposed to be fixed.

First, we present an explicit formula for the number of spanning trees in the graph G_n. This formula is a product of βs_k-1 factors, each given by the n-th Chebyshev polynomial of the first kind evaluated at the roots of some prescribed polynomial of degree s_k. Next, we provide some arithmetic properties of the complexity function. We show that the number of spanning trees in G_n can be represented in the form τ(n) = p n a(n)², where a(n) is an integer sequence and p is a prescribed natural number depending of parity of β and n. Finally, we find an asymptotic formula for τ(n) through the Mahler measure of the associated Laurent polynomials differing by a constant from 2k - ∑_i = 1^k(z^s_i+z^−s_i).