RUS  ENG
Full version
JOURNALS // Matematicheskie Trudy // Archive

Mat. Tr., 2023 Volume 26, Number 2, Pages 129–137 (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

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.

UDC: 519.1

Received: 18.05.2023
Revised: 31.07.2023
Accepted: 05.10.2023

DOI: 10.33048/mattrudy.2023.26.206


 English version:
Siberian Advances in Mathematics, 2023, 33:4, 322–328


© Steklov Math. Inst. of RAS, 2024