### 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_{1}, ... , s_{k}, α_{1}n, ... , α_{l}n), 1 ≤ s_{1}< ... < s_{k}≤ [βn/2], 1 ≤ α_{1}< ... < α_{l} ≤ [β/2].

Here n is an arbitrary large natural number and integers s_{1}, ... , s_{k}, α_{1}, ... , α_{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)^{2}, 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 2*k* - ∑_{i = 1}^{k}(*z*^{si}+*z*^{−si}).

#### Keywords

#### Full Text:

MANUSCRIPTDOI: https://doi.org/10.26493/1855-3974.2530.e7c

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications