|
Matematicheskie Trudy, 2023, Volume 26, Number 2, Pages 129–137 DOI: https://doi.org/10.33048/mattrudy.2023.26.206
(Mi mt682)
|
|
|
|
The generating function is rational for the number of rooted forests in a circulant graph
U. P. Kamalovab, A. B. Kutbaevbc, A. D. Mednykhab a Sobolev Institute of Mathematics, Novosibirsk, 630090, Russia
b Novosibirsk State University, Novosibirsk, 630090, Russia
c Nukus State Pedagogical Institute, Nukus, 230100, Uzbekistan
DOI:
https://doi.org/10.33048/mattrudy.2023.26.206
Abstract:
We consider the generating function $\Phi$ for the number $f_\Gamma(n)$ of rooted spanning forests in the circulant graph $\Gamma$, where $\Phi(x)=\sum_{n=1}^\infty f_\Gamma(n)x^n$ and either $\Gamma=C_n(s_1,s_2,\dots,s_k)$ or $\Gamma=C_{2n}(s_1,s_2,\dots,s_k,n)$. We show that $\Phi$ is a rational function with integer coefficients that satisfies the condition $\Phi(x)=-\Phi(1/x)$. We illustrate this result by a series of examples.
Key words:
rooted spanning forest, circulant graph, generating function.
Received: 18.05.2023 Revised: 31.07.2023 Accepted: 05.10.2023
Citation:
U. P. Kamalov, A. B. Kutbaev, A. D. Mednykh, “The generating function is rational for the number of rooted forests in a circulant graph”, Mat. Tr., 26:2 (2023), 129–137; Siberian Adv. Math., 33:4 (2023), 322–328
Linking options:
https://www.mathnet.ru/eng/mt682 https://www.mathnet.ru/eng/mt/v26/i2/p129
|
| Statistics & downloads: |
| Abstract page: | 190 | | Full-text PDF : | 59 | | References: | 46 |
|