Research output: Contribution to journal › Article › peer-review
Counting spanning trees in cobordism of two circulant graphs. / Baigonakova, Galya Amanboldynovna; Mednykh, Ilya Aleksandrovich.
In: Сибирские электронные математические известия, Vol. 15, 01.01.2018, p. 1145-1157.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Counting spanning trees in cobordism of two circulant graphs
AU - Baigonakova, Galya Amanboldynovna
AU - Mednykh, Ilya Aleksandrovich
PY - 2018/1/1
Y1 - 2018/1/1
N2 - We consider a family of graphs Hn(s1, ..., sk; t1, ..., tl) that is a generalisation of the family of I-graphs, which, in turn, includes the generalized Petersen graphs. We present an explicit formula for the number τ(n) of spanning trees in these graphs in terms of the Chebyshev polynomials and find its asymptotics. Also, we show that the number of spanning trees can be represented in the form τ(n) = p n a(n)2; where a(n) is an integer sequence and p is a prescribed integer depending on the number of even elements in the sequence s1, ..., sk; t1, ..., tl and the parity of n.
AB - We consider a family of graphs Hn(s1, ..., sk; t1, ..., tl) that is a generalisation of the family of I-graphs, which, in turn, includes the generalized Petersen graphs. We present an explicit formula for the number τ(n) of spanning trees in these graphs in terms of the Chebyshev polynomials and find its asymptotics. Also, we show that the number of spanning trees can be represented in the form τ(n) = p n a(n)2; where a(n) is an integer sequence and p is a prescribed integer depending on the number of even elements in the sequence s1, ..., sk; t1, ..., tl and the parity of n.
KW - Chebyshev polynomial
KW - Circulant graph
KW - I-graph
KW - Mahler measure
KW - Petersen graph
KW - Spanning tree
KW - I-GRAPHS
KW - NUMBER
KW - spanning tree
KW - COMPLEXITY
KW - circulant graph
KW - FORMULAS
UR - http://www.scopus.com/inward/record.url?scp=85069981202&partnerID=8YFLogxK
U2 - 10.17377/semi.2018.15.093
DO - 10.17377/semi.2018.15.093
M3 - Article
AN - SCOPUS:85069981202
VL - 15
SP - 1145
EP - 1157
JO - Сибирские электронные математические известия
JF - Сибирские электронные математические известия
SN - 1813-3304
ER -
ID: 22323121