TY - JOUR

T1 - Counting rooted spanning foresrs in cobordism of two circulant graphs

AU - Abrosimov, N. V.

AU - Baigonakova, G. A.

AU - Grunwald, L. A.

AU - Mednykh, I. A.

N1 - Funding Information: Abrosimov, N.V., Baigonakova, G.A., Grunwald, L.A., Mednykh, I.A., Counting rooted spanning foresrs in cobordism of two circulant graphs. ⃝c 2020 Abrosimov N.V., Baigonakova G.A., Grunwald L.A., Mednykh I.A. Parts 1–4 of the work were supported by Mathematical Center in Akademgorodok under agreement No. 075-15-2019-1613 with the Ministry of Science and Higher Education of the Russian Federation, part 5 was supported by Russian Foundation for Basic Research (project 18-01-00420). Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - We consider a family of graphs H-n(s(1), ..., s(k); t(1), ...,t(l)), which is a generalization of the family of I-graphs, which in turn, includes the generalized Petersen graphs and the prism graphs. We present an explicit formula for the number f(H)(n) of rooted spanning forests in these graphs in terms of Chebyshev polynomials and find its asymptotics. Also, we show that the number of rooted spanning forests can be represented in the form f(H)(n) = p a(n)(2), where a(n) is an integer sequence and p is a prescribed integer depending on the number of odd elements in the sequence s(1), ..., s(k), t(1), ..., t(l) and the parity of n.

AB - We consider a family of graphs H-n(s(1), ..., s(k); t(1), ...,t(l)), which is a generalization of the family of I-graphs, which in turn, includes the generalized Petersen graphs and the prism graphs. We present an explicit formula for the number f(H)(n) of rooted spanning forests in these graphs in terms of Chebyshev polynomials and find its asymptotics. Also, we show that the number of rooted spanning forests can be represented in the form f(H)(n) = p a(n)(2), where a(n) is an integer sequence and p is a prescribed integer depending on the number of odd elements in the sequence s(1), ..., s(k), t(1), ..., t(l) and the parity of n.

KW - circulant graph

KW - I-graph

KW - Petersen graph

KW - prism graph

KW - spanning forest

KW - Chebyshev polynomial

KW - Mahler measure

KW - TREE FORMULAS

KW - I-GRAPHS

KW - NUMBER

KW - ENUMERATION

KW - COMPLEXITY

UR - http://www.scopus.com/inward/record.url?scp=85099396304&partnerID=8YFLogxK

U2 - 10.33048/semi.2020.17.059

DO - 10.33048/semi.2020.17.059

M3 - Article

AN - SCOPUS:85099396304

VL - 17

SP - 814

EP - 823

JO - Сибирские электронные математические известия

JF - Сибирские электронные математические известия

SN - 1813-3304

ER -