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

angleški

2023

letnik 23, številka 1

cirkulant   Čebiševljev polinom   Laplaceova matrika   Mahlerjeva mera   vpeto drevo

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

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.

02.10.2023