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

Research output: Contribution to journalArticle

2 Citations (Scopus)

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 ).

Original languageEnglish
Pages (from-to)1772-1781
Number of pages10
JournalDiscrete Mathematics
Volume342
Issue number6
DOIs
Publication statusPublished - 1 Jun 2019

Keywords

  • Chebyshev polynomial
  • Circulant graph
  • Laplacian matrix
  • Mahler measure
  • Spanning tree
  • JACOBIAN GROUP
  • COMPLEXITY

Fingerprint Dive into the research topics of 'The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic'. Together they form a unique fingerprint.

  • Cite this