TY - JOUR

T1 - Counting rooted spanning forests for circulant foliation over a graph

AU - Grunwald, Liliya A.

AU - Kwon, Young Soo

AU - Mednykh, Ilya

N1 - 2010 Mathematics Subject Classification. Primary 05C30; Secondary 39A10. Key words and phrases. Spanning forest, rooted forest, circulant graph, -graph, -graph, -graph, Laplacian matrix, Chebyshev polynomial. The first and the third authors were supported by the Mathematical Center in Akademgorodok, agreement no. 075-15-2019-1613 with the Ministry of Science and Higher Education of the Russian Federation. The second author was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2018R1D1A1B05048450).

PY - 2022/12/15

Y1 - 2022/12/15

N2 - In this paper, we present a new method to produce explicit formulas for the number of rooted spanning forests f(n) for the infinite family of graphs Hn = Hn(G1, G2, …, Gm) obtained as a circulant foliation over a graph H on m vertices with fibers G1, G2, …,Gm. Each fiber Gi = Cn(si,1, si,2,…,si,ki) of this foliation is the circulant graph on n vertices with jumps si,1, si,2, …, si,ki. This family includes the family of generalized Petersen graphs, I-graphs, sandwiches of circulant graphs, discrete torus graphs and others.The formulas are expressed through Chebyshev polynomials. We prove that the number of rooted spanning forests can be represented in the form f(n) = pf(H)a(n)2, where a(n) is an integer sequence and p is a prescribed natural number depending on the number of odd elements in the set of si,j. Finally, we find an asymptotic formula for f(n) through the Mahler measure of the associated Laurent polynomial.

AB - In this paper, we present a new method to produce explicit formulas for the number of rooted spanning forests f(n) for the infinite family of graphs Hn = Hn(G1, G2, …, Gm) obtained as a circulant foliation over a graph H on m vertices with fibers G1, G2, …,Gm. Each fiber Gi = Cn(si,1, si,2,…,si,ki) of this foliation is the circulant graph on n vertices with jumps si,1, si,2, …, si,ki. This family includes the family of generalized Petersen graphs, I-graphs, sandwiches of circulant graphs, discrete torus graphs and others.The formulas are expressed through Chebyshev polynomials. We prove that the number of rooted spanning forests can be represented in the form f(n) = pf(H)a(n)2, where a(n) is an integer sequence and p is a prescribed natural number depending on the number of odd elements in the set of si,j. Finally, we find an asymptotic formula for f(n) through the Mahler measure of the associated Laurent polynomial.

UR - https://www.scopus.com/inward/record.url?eid=2-s2.0-85143421408&partnerID=40&md5=88c1ddb34c495b9f69d346e83b998962

UR - https://www.mendeley.com/catalogue/3a0fa46c-57ef-34bb-b195-362ef4362519/

U2 - 10.2748/tmj.20210810

DO - 10.2748/tmj.20210810

M3 - Article

VL - 74

SP - 535

EP - 548

JO - Tohoku Mathematical Journal

JF - Tohoku Mathematical Journal

SN - 0040-8735

IS - 4

ER -