{
  "id": "2312.16447",
  "version": "v1",
  "published": "2023-12-27T07:24:27.000Z",
  "updated": "2023-12-27T07:24:27.000Z",
  "title": "On the complexity of Cayley graphs on a dihedral group",
  "authors": [
    "Bobo Hua",
    "Alexander Mednykh",
    "Ilya Mednykh",
    "Lili Wang"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper, we investigate the complexity of an infinite family of Cayley graphs $\\mathcal{D}_{n}=Cay(\\mathbb{D}_{n}, b^{\\pm\\beta_1},b^{\\pm\\beta_2},\\ldots,b^{\\pm\\beta_s}, a b^{\\gamma_1}, a b^{\\gamma_2},\\ldots, a b^{\\gamma_t} )$ on the dihedral group $\\mathbb{D}_{n}=\\langle a,b| a^2=1, b^n=1,(a\\,b)^2=1\\rangle$ of order $2n.$ We obtain a closed formula for the number $\\tau(n)$ of spanning trees in $\\mathcal{D}_{n}$ in terms of Chebyshev polynomials, investigate some arithmetical properties of this function, and find its asymptotics as $n\\to\\infty.$ Moreover, we show that the generating function $F(x)=\\sum\\limits_{n=1}^\\infty\\tau(n)x^n$ is a rational function with integer coefficients.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-12-27T07:24:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30",
      "39A12"
    ],
    "keywords": [
      "dihedral group",
      "cayley graphs",
      "complexity",
      "chebyshev polynomials",
      "rational function"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}