### 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 language | English |
---|---|

Pages (from-to) | 1772-1781 |

Number of pages | 10 |

Journal | Discrete Mathematics |

Volume | 342 |

Issue number | 6 |

DOIs | |

Publication status | Published - 1 Jun 2019 |

### Keywords

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