Standard

The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic. / Mednykh, A. D.; Mednykh, I. A.

In: Discrete Mathematics, Vol. 342, No. 6, 01.06.2019, p. 1772-1781.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Mednykh AD, Mednykh IA. The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic. Discrete Mathematics. 2019 Jun 1;342(6):1772-1781. doi: 10.1016/j.disc.2018.08.030

Author

BibTeX

@article{0c752a699340495486f3f27c1f63889e,
title = "The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic",
abstract = " In this paper, we develop a new method to produce explicit formulas for the number τ(n) of spanning trees in the undirected circulant graphs C n (s 1 ,s 2 ,…,s k ) and C 2n (s 1 ,s 2 ,…,s k ,n). Also, we prove that in both cases the number of spanning trees can be represented in the form τ(n)=pna(n) 2 , where a(n) is an integer sequence and p is a prescribed natural number depending on the parity of n. Finally, we find an asymptotic formula for τ(n) through the Mahler measure of the associated Laurent polynomial L(z)=2k−∑j=1k(z s j +z −s j ). ",
keywords = "Chebyshev polynomial, Circulant graph, Laplacian matrix, Mahler measure, Spanning tree, JACOBIAN GROUP, COMPLEXITY",
author = "Mednykh, {A. D.} and Mednykh, {I. A.}",
year = "2019",
month = jun,
day = "1",
doi = "10.1016/j.disc.2018.08.030",
language = "English",
volume = "342",
pages = "1772--1781",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "6",

}

RIS

TY - JOUR

T1 - The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic

AU - Mednykh, A. D.

AU - Mednykh, I. A.

PY - 2019/6/1

Y1 - 2019/6/1

N2 - In this paper, we develop a new method to produce explicit formulas for the number τ(n) of spanning trees in the undirected circulant graphs C n (s 1 ,s 2 ,…,s k ) and C 2n (s 1 ,s 2 ,…,s k ,n). Also, we prove that in both cases the number of spanning trees can be represented in the form τ(n)=pna(n) 2 , where a(n) is an integer sequence and p is a prescribed natural number depending on the parity of n. Finally, we find an asymptotic formula for τ(n) through the Mahler measure of the associated Laurent polynomial L(z)=2k−∑j=1k(z s j +z −s j ).

AB - In this paper, we develop a new method to produce explicit formulas for the number τ(n) of spanning trees in the undirected circulant graphs C n (s 1 ,s 2 ,…,s k ) and C 2n (s 1 ,s 2 ,…,s k ,n). Also, we prove that in both cases the number of spanning trees can be represented in the form τ(n)=pna(n) 2 , where a(n) is an integer sequence and p is a prescribed natural number depending on the parity of n. Finally, we find an asymptotic formula for τ(n) through the Mahler measure of the associated Laurent polynomial L(z)=2k−∑j=1k(z s j +z −s j ).

KW - Chebyshev polynomial

KW - Circulant graph

KW - Laplacian matrix

KW - Mahler measure

KW - Spanning tree

KW - JACOBIAN GROUP

KW - COMPLEXITY

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

U2 - 10.1016/j.disc.2018.08.030

DO - 10.1016/j.disc.2018.08.030

M3 - Article

AN - SCOPUS:85062879766

VL - 342

SP - 1772

EP - 1781

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 6

ER -

ID: 18861210