{
  "id": "1907.02635",
  "version": "v1",
  "published": "2019-07-04T03:03:47.000Z",
  "updated": "2019-07-04T03:03:47.000Z",
  "title": "The number of rooted forests in circulant graphs",
  "authors": [
    "L. A. Grunwald",
    "I. A. Mednykh"
  ],
  "comment": "14 pages. arXiv admin note: substantial text overlap with arXiv:1711.00175, arXiv:1812.04484",
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper, we develop a new method to produce explicit formulas for the number $f_{G}(n)$ of rooted spanning forests in the circulant graphs $ G=C_{n}(s_1,s_2,\\ldots,s_k)$ and $ G=C_{2n}(s_1,s_2,\\ldots,s_k,n).$ These formulas are expressed through Chebyshev polynomials. We prove that in both cases the number of rooted spanning forests can be represented in the form $f_{G}(n)=p\\,a(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 $f_{G}(n)$ through the Mahler measure of the associated Laurent polynomial $P(z)=2k+1-\\sum\\limits_{i=1}^k(z^{s_i}+z^{-s_i}).$",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-07-04T03:03:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30",
      "39A12"
    ],
    "keywords": [
      "circulant graphs",
      "rooted forests",
      "rooted spanning forests",
      "produce explicit formulas",
      "asymptotic formula"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}