The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic Full article
| Journal |
Discrete Mathematics
ISSN: 0012-365X , E-ISSN: 1872-681X |
||||
|---|---|---|---|---|---|
| Output data | Year: 2019, Volume: 342, Number: 6, Pages: 1772-1781 Pages count : 10 DOI: 10.1016/j.disc.2018.08.030 | ||||
| Tags | Chebyshev polynomial; Circulant graph; Laplacian matrix; Mahler measure; Spanning tree | ||||
| Authors |
|
||||
| Affiliations |
|
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 ). © 2019 Elsevier B.V.
Cite:
Mednykh A.D.
, Mednykh I.A.
The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic
Discrete Mathematics. 2019. V.342. N6. P.1772-1781. DOI: 10.1016/j.disc.2018.08.030 WOS Scopus OpenAlex
The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic
Discrete Mathematics. 2019. V.342. N6. P.1772-1781. DOI: 10.1016/j.disc.2018.08.030 WOS Scopus OpenAlex
Identifiers:
| Web of science: | WOS:000466833400020 |
| Scopus: | 2-s2.0-85062879766 |
| OpenAlex: | W2963854080 |