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},\dots ,b^{\pm {\beta }_s},a{b}^{{\gamma }_1},a{b}^{{\gamma }_2},\dots ,a{b}^{{\gamma }_t})$ on the dihedral group ${\mathbb{D}}_n=⟨a,b|a^2=1,b^n=1,(ab{)}^2=1⟩$ 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 _{n=1}^{\infty }\tau (n)x^n$ is a rational function with integer coefficients.