Spectrum of twists of Cayley and Cayley sum graphs

Abstract

Let $G$ be a finite group with $|G|\ge 4$ and $S$ be a subset of $G$. Given an automorphism $\sigma$ of $G$, the twisted Cayley graph $C(G,S{)}^{\sigma }$ (resp. the twisted Cayley sum graph $C_{\Sigma }(G,S{)}^{\sigma }$) is defined as the graph having $G$ as its set of vertices and the adjacent vertices of a vertex $g\in G$ are of the form $\sigma (gs)$ (resp. $\sigma (g^{-1}s)$) for some $s\in S$. If the twisted Cayley graph $C(G,S{)}^{\sigma }$ is undirected and connected, then we prove that the nontrivial spectrum of its normalised adjacency operator is bounded away from $-1$ and this bound depends only on its degree, the order of $\sigma$ and the vertex Cheeger constant of $C(G,S{)}^{\sigma }$. Moreover, if the twisted Cayley sum graph $C_{\Sigma }(G,S{)}^{\sigma }$ is undirected and connected, then we prove that the nontrivial spectrum of its normalised adjacency operator is bounded away from $-1$ and this bound depends only on its degree and the vertex Cheeger constant of $C_{\Sigma }(G,S{)}^{\sigma }$. We also study these twisted graphs with respect to anti-automorphisms, and obtain similar results. Further, we prove an analogous result for the Schreier graphs satisfying certain conditions.