On the complexity of Cayley graphs on a dihedral group

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)xn$} is a rational function with integer coefficients.