On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs | Sciact - Система учета научной деятельности ИМ СО РАН

On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs Научная публикация

Журнал

Algebra Colloquium
ISSN: 1005-3867

Вых. Данные

Год: 2020, Том: 27, Номер: 1, Страницы: 87-94 Страниц : 8 DOI: 10.1142/S1005386720000085

Ключевые слова

Chebyshev polynomial; circulant graph; generating function; spanning tree

Авторы

Mednykh A.D. ^1,2 , Mednykh I.A. ^1,2

Организации

1	Sobolev Institute of Mathematics, Novosibirsk, 630090, Russian Federation
2	Novosibirsk State University, Novosibirsk, 630090, Russian Federation

Let F(x) = n=1s1,s2, ...,sk(n)xn be the generating function for the number τs1,s2, ...,sk(n) of spanning trees in the circulant graph Cn(s1, s2, ..., sk). We show that F(x) is a rational function with integer coefficients satisfying the property F(x) = F(1/x). A similar result is also true for the circulant graphs C2n(s1, s2, ..., sk, n) of odd valency. We illustrate the obtained results by a series of examples.

Mednykh A.D. , Mednykh I.A.
On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs
Algebra Colloquium. 2020. V.27. N1. P.87-94. DOI: 10.1142/S1005386720000085 WOS Scopus OpenAlex

Web of science:	WOS:000518157600008
Scopus:	2-s2.0-85080125218
OpenAlex:	W3008816466

БД	Цитирований
Scopus	4
OpenAlex	4
Web of science	3