Integral circulant Ramanujan graphs of prime power order

T. A. Le ; J. W. Sander

The electronic journal of combinatorics, Tome 20 (2013) no. 3

Résumé

A connected $\rho$-regular graph $G$ has largest eigenvalue $\rho$ in modulus. $G$ is called Ramanujan if it has at least $3$ vertices and the second largest modulus of its eigenvalues is at most $2\sqrt{\rho-1}$. In 2010 Droll classified all Ramanujan unitary Cayley graphs. These graphs of type ${\rm ICG}(n,\{1\})$ form a subset of the class of integral circulant graphs ${\rm ICG}(n,{\cal D})$, which can be characterised by their order $n$ and a set $\cal D$ of positive divisors of $n$ in such a way that they have vertex set $\mathbb{Z}/n\mathbb{Z}$ and edge set $\{(a,b):\, a,b\in\mathbb{Z}/n\mathbb{Z} ,\, \gcd(a-b,n)\in {\cal D}\}$. We extend Droll's result by drawing up a complete list of all graphs ${\rm ICG}(p^s,{\cal D})$ having the Ramanujan property for each prime power $p^s$ and arbitrary divisor set ${\cal D}$.

Détail

DOI : 10.37236/3159

Classification : 05C50, 05C75, 15A18
Mots-clés : Cayley graph, integral graph, circulant graph, graph spectrum, Ramanujan graph