ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P1.08
https://doi.org/10.26493/1855-3974.2530.e7c
(Also available at http://amc-journal.eu)
Complexity of circulant graphs with non-fixed
jumps, its arithmetic properties and
asymptotics*
Alexander Mednykh , Ilya Mednykh †
Sobolev Institute of Mathematics, 630090, Novosibirsk, Russia
Novosibirsk State University, 630090, Novosibirsk, Russia
Received 11 January 2021, accepted 23 March 2022, published online 21 October 2022
Abstract
In the present paper, we investigate a family of circulant graphs with non-fixed jumps
Gn = Cβn(s1, . . . , sk, α1n, . . . , αℓn),
1 ≤ s1 < . . . < sk < [
βn
2
], 1 ≤ α1 < . . . < αℓ ≤ [
β
2
].
Here n is an arbitrary large natural number and integers s1, . . . , sk, α1, . . . , αℓ, β are sup-
posed to be fixed.
First, we present an explicit formula for the number of spanning trees in the graph Gn.
This formula is a product of βsk−1 factors, each given by the n-th Chebyshev polynomial
of the first kind evaluated at the roots of some prescribed polynomial of degree sk. Next, we
provide some arithmetic properties of the complexity function. We show that the number
of spanning trees in Gn can be represented in the form τ(n) = p n a(n)2, where a(n)
is an integer sequence and p is a given natural number depending on parity of β and n.
Finally, we find an asymptotic formula for τ(n) through the Mahler measure of the Laurent
polynomials differing by a constant from 2k −
∑k
i=1(z
si + z−si).
Keywords: Spanning tree, circulant graph, Laplacian matrix, Chebyshev polynomial, Mahler mea-
sure.
Math. Subj. Class. (2020): 05C30, 05A18
*The authors are grateful to anonymous referees for helpful remarks and suggestions. The work was supported
by Mathematical Center in Akademgorodok under agreement No. 075-15-2019-1613 with the Ministry of Science
and Higher Education of the Russian Federation.
†Corresponding author.
E-mail addresses: smedn@mail.ru (Alexander Mednykh), ilyamednykh@mail.ru (Ilya Mednykh)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P1.08
https://doi.org/10.26493/1855-3974.2530.e7c
(Dostopno tudi na http://amc-journal.eu)
Kompleksnost cirkulantov z nefiksiranimi skoki,
njene aritmetične lastnosti in asimptotika*
Alexander Mednykh , Ilya Mednykh †
Sobolev Institute of Mathematics, 630090, Novosibirsk, Russia
Novosibirsk State University, 630090, Novosibirsk, Russia
Prejeto 11. januarja 2021, sprejeto 23. marca 2022, objavljeno na spletu 21. oktobra 2022
Povzetek
V tem članku preučujemo družino cirkulantov z nefiksiranimi skoki
Gn = Cβn(s1, . . . , sk, α1n, . . . , αℓn),
1 ≤ s1 < . . . < sk < [
βn
2
], 1 ≤ α1 < . . . < αℓ ≤ [
β
2
].
Tukaj je n poljubno veliko naravno število, cela števila s1, . . . , sk, α1, . . . , αℓ, β pa so
fiksirana.
Najprej predstavimo eksplicitno formulo za število vpetih dreves v grafu Gn. Ta for-
mula je produkt βsk−1 faktorjev, vsak od njih je podan z n-tim Čebiševljevim polinomom
prve vrste, evaluiranim pri ničlah nekega predpisanega polinoma stopnje sk. Nadalje pred-
stavimo nekaj aritmetičnih lastnosti kompleksnostne funkcije. Dokažemo, da se da število
vpetih dreves v grafu Gn zapisati v obliki τ(n) = p n a(n)2, kjer je a(n) celoštevil-
sko zaporedje, p pa dano naravno število, odvisno od sodosti števil β in n. Poiščemo še
asimptotsko formulo za τ(n) preko Mahlerjeve mere Laurentovih polinomov, ki se od
2k −
∑k
i=1(z
si + z−si) razlikujejo samo za konstanto.
Ključne besede: Vpeto drevo, cirkulant, Laplaceova matrika, Čebiševljev polinom, Mahlerjeva mera.
Math. Subj. Class. (2020): 05C30, 05A18
*Avtorja sta hvaležna neznanim recenzentom za koristne pripombe in predloge. To delo je bilo podprto s
strani Mathematical Center in Akademgorodok po pogodbi št. 075-15-2019-1613 z Ministry of Science and
Higher Education of the Russian Federation.
†Kontaktni avtor.
E-poštna naslova: smedn@mail.ru (Alexander Mednykh), ilyamednykh@mail.ru (Ilya Mednykh)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/