Complexity of circulant graphs with non-fixed jumps, its arithmetic properties and asymptotics - Mednykh, Alexander (Ars mathematica contemporanea, 2023)
V članku preučujemo družino cirkulantov z nefiksiranimi skoki ?$$ \begin{gathered} G_n = C_{\beta n} (s_1, \dots, s_k, \alpha_1 n,\dots, \alpha_{\ell} n), \\ 1 \leq s_1 <\dots < s_k \leq \frac{\beta n}{2}, 1 \leq \alpha_1 < \dots < \alpha_{\ell} \leq \frac{\beta}{2}. \end{gathered} $$? Tukaj je ?$n$? poljubno veliko naravno število, cela števila ?$s_1,\ldots, s_k, \alpha_1, \ldots, \alpha_{\ell}, \beta$? pa so fiksirana. Najprej predstavimo eksplicitno formulo za število vpetih dreves v grafu ?$G_n$?. Ta formula je produkt ?$\beta s_k -1$? faktorjev, vsak od njih je podan z ?$n$?-tim Čebiševljevim polinomom prve vrste, evaluiranim pri ničlah nekega predpisanega polinoma stopnje ?$s_k$?. Nadalje predstavimo nekaj aritmetičnih lastnosti kompleksnostne funkcije. Dokažemo, da se da število vpetih dreves v grafu ?$G_n$? zapisati v obliki ?$\tau (n) = pna(n)^2$?, kjer je ?$a(n)$? celoštevilsko zaporedje, ?$p$? pa dano naravno število, odvisno od sodosti števil?$\beta$? in ?$n$?. Poiščemo še asimptotsko formulo za ?$\tau (n)$? preko Mahlerjeve mere Laurentovih polinomov, ki se od ?$2k-\sum_{i = 1}^k (z^{s_i}+z^{-s_i})$? razlikujejo samo za konstanto.
Keywords: Chebyshev polynomial; circulant graph; cirkulant; Čebiševljev polinom; Laplaceova matrika; Laplacian matrix; Mahler measure; Mahlerjeva mera; spanning tree; vpeto drevo