\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P35}{20(3)}{2013}
\sloppy

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}                                                           
\usepackage{mathrsfs} 

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}


%   Lateinische Ausgangsschrift
%\usepackage{la}
%\usepackage[T1]{fontenc}
\DeclareMathAlphabet{\mathscr}{OT1}{pzc}%
                                 {m}{it}

\usepackage{bm}
\usepackage{bbm}


\DeclareFontFamily{OT1}{pzc}{}
\DeclareFontShape{OT1}{pzc}{m}{it}{<-> s * [1.200] pzcmi7t}{}
\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it} 

\newcommand{\Icg}[2]{\mathrm{ICG}({#2},{#1})}   
\newcommand{\Ene}[2]{\mathpzc{E}({#2},{#1})}   


%\newcommand{\qed}{\hfill \ensuremath{\Box}\bigskip}

%\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{proposition}{Proposition}[section]
%\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{conjecture}{Conjecture}[section]
\newtheorem{example}{Example}[section]

\newtheorem{remarknonumb}{Remark}


\newcommand{\md}{{\mathcal{D} }}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%\tolerance=500








\begin{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Integral Circulant Ramanujan Graphs\\of Prime Power Order}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{T.A. Le \qquad J.W. Sander\thanks{Corresponding author}\\
\small Institut f\"ur Mathematik und Angewandte Informatik\\[-0.8ex]
\small Universit\"at Hildesheim\\[-0.8ex] 
\small D-31141 Hildesheim, Germany\\
\small\tt sander@imai.uni-hildesheim.de
}

\date{\dateline{Feb 24, 2013}{Aug 28, 2013}{Sep 6, 2013}\\
\small Mathematics Subject Classifications:  Primary 05C50, 05C75; Secondary 15A18}

\maketitle














\begin{abstract}

A connected $\rho$-regular graph $G$ has largest eigenvalue $\rho$ in modulus. $G$ is called \textit{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 {\sc Droll} classified all Ramanujan unitary Cayley graphs. These graphs of type $\Icg{\{1\}}{n}$ form a subset of the class of \textit{integral circulant graphs} $\Icg{\md}{n}$, 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 {\sc Droll's} result by drawing up a complete list of all graphs $\Icg{\md}{p^s}$ having the Ramanujan property for each prime power $p^s$ and arbitrary divisor set $\md$.  

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Cayley graph, integral graph, circulant graph, graph spectrum, Ramanujan graph
	
\end{abstract}















\section{Introduction}




Over the last decades the theory of \textit{expander graphs} has attracted quite a lot of research interest. These graphs with strong connectivity properties have a number of applicatory consequences, e.g. the resolution of an extremal problem in communication network theory (cf. $\cite{BIE}$), but they are also of importance in theoretical computer science. For a detailed review of this topic we refer to $\cite{HLW}$.

A special class of expanders are \textit{Ramanujan graphs}, which were introduced by   {\sc Lubotzky}, {\sc Phillips} and {\sc Sarnak} \cite{LPS} in 1988 (see also \cite{MUR}). A connected $\rho$-regular graph $G$ has largest eigenvalue $\rho$ and is called \textit{Ramanujan} if $G$ has at least three vertices and the second largest modulus of its eigenvalues
\begin{equation}  \label{defLambda}
\Lambda(G) := \max \{ \vert \lambda \vert: \; \lambda\in {\rm Spec}(G), \; \vert\lambda\vert \neq \rho\}
\end{equation}
satisfies $\Lambda(G) \leq 2\sqrt{\rho-1}$, where 
the eigenvalues of a graph $G$ simply are the eigenvalues of its adjacency matrix, and 
the \textit{spectrum} ${\rm Spec}(G)$ is the set of all these eigenvalues. Observe that for each $\rho$-regular connected graph $G$ the largest eigenvalue $\rho$ occurs with multiplicity $1$, and consequently $G$ has eigenvalues $\lambda$ with $\vert\lambda\vert <\rho$ if $G$ has at least $3$ vertices (cf. \cite{BIG}), which means that $\Lambda(G)$ is well defined under this mild restriction. By a result of {\sc Alon} \cite{AlBo} and {\sc Boppana} \cite {BOP} (see also \cite{LPS}, Proposition 4.2) on random $\rho$-regular graphs we know that $\Lambda(G)=2\sqrt{\rho-1}$ is asymptotically best possible.


The class of \textit{integral circulant graphs}, i.e. graphs having a circulant adjacency matrix with integral eigenvalues, is an object comprising algebraic, arithmetic and combinatorial features. Lots of interesting results on this class of graphs have been obtained in recent years (see \cite{SA1} for references). 
By the works of {\sc Klotz} and {\sc T.~Sander} \cite{KLO} and {\sc So} \cite{SO}, integral circulant graphs are generalisations of unitary Cayley graphs and can be defined as follows: For a given integer $n>1$ and a set $\md\subseteq D(n):=\{d>0: \; d\mid n\}$ of positive divisors of $n$ the corresponding integral circulant graph $\Icg{\md}{n}$ has 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 \md\}$, where $\mathbb{Z}/n\mathbb{Z}$ denotes the additive group of residue classes $\bmod \; n$. Unitary Cayley graphs are the graphs $\Icg{\{1\}}{n}$.
Since $\Icg{\md}{n}$ has loops in case $n\in \md$, it is usually assumed that $\md\subseteq D^*(n):=D(n)\setminus\{n\}$.  
Recently the examination of spectral properties of ICGs has caught quite some attention (cf.  \cite{AHM,ANG,SAX,SHP}). In particular, a variety of results on the \textit{energy} 
\[
\Ene{\cal D}{n} := E(\Icg{\cal D}{n}) = \sum_{\lambda\in {\rm Spec}(\Icg{\cal D}{n})} \vert \lambda \vert
\]
of $\Icg{\md}{n}$ has been obtained (cf.  \cite{BRU,GUT,ILI,LS2,SA1,SA2,SA5,SHP}).


In 2010 {\sc Droll} \cite{DRO} classified all unitary Cayley graphs, i.e.~graphs of type $\Icg{\{1\}}{n}$, which have the Ramanujan property. 
We extend {\sc Droll's} result by drawing up a complete list of all graphs $\Icg{\md}{p^s}$ having the Ramanujan property for each prime power $p^s$ and arbitrary divisor set $\md \subseteq D^*(p^s)$.  


Expanding our definition of $D(n)$, %and $D^*(n)$
we set $D(n;m):=\{d\in D(n):\, d\geq m\}$ %and $D^*(n;m):=\{d\in D^*(n):\, d \geq m\}$ 
for any positive integer $m$.
\begin{theorem} 
\label{thmrama}
Let $p$ be a prime and $s$ a positive integer such that $p^s \geq 3$. %Let $\md \subseteq D^*(p^s)$, i.e. $\md=\{p^{a_1},p^{a_2},\ldots,p^{a_r}\}$ for some positive integer $r$ with $0\leq a_1< a_2<\ldots<a_r\leq s-1$. 
Let $\md \subseteq D^*(p^s)$ be an arbitrary divisor set of $p^s$.  
Then $\Icg{\md}{p^s}$ is a Ramanujan graph if and only if 
$\md$ %has one of the following properties: it 
lies in one of the following classes:
\begin{itemize}
\item[(i)] 
$\md = D(p^{\lceil \frac{s}{2}\rceil-1})\cup \md'$ for some $\md'\subseteq D(p^{s-1};p^{\lceil \frac{s}{2}\rceil})$;
\item[(ii)] $\md=\{1\}$ in case $p=2$ and $s\geq 3$; 
\item[(iii)] $\md = D(p^{\frac{s-3}{2}}) \cup \md'$ such that $|\md|\geq 2$ for some $\md'\subseteq D(p^{s-1};p^{\frac{s+1}{2}})$ in case $p\in \{2,3\}$ and $s\geq 3$ odd; 
\item[(iv)] $\md = D(2^{\frac{s-4}{2}}) \cup \md'$ for some $\md'\subseteq D(2^{s-1};2^{\frac{s}{2}})$ satisfying $\emptyset\neq \md' \neq \{2^{s-1}\}$ in case $p=2$ and $s\geq 4$ even; 

\item[(v)] $\md = \{1,2^2,2^3,2^4\}$ in case $p=2$ and $s=5$;

\item[(vi)] $\md = D(5^{\frac{s-3}{2}})\cup\{5^{\frac{s+1}{2}}\}  \cup \md'$ for some $\md'\subseteq D(5^{s-1};5^{\frac{s+3}{2}})$ in case $p=5$ and $s\geq 5$ odd; 

\item[(vii)] $\md= D(2^{\frac{s-5}{2}}) \cup\{2^{\frac{s-1}{2}}\} \cup \md'$
%\{p^{a_1},p^{a_2},\ldots,p^{a_r}\}$
for some $\md'\subseteq D(2^{s-1};2^{\frac{s+1}{2}})$ satisfying
\begin{equation} \label{exception}
3-2\sqrt{2} + \frac{1}{2^{\frac{s-3}{2}}} \leq 2^{\frac{s-1}{2}} \sum_{d'\in \md'} \frac{1}{d'} 
\end{equation}
in case  $p=2$ and $s\geq 5$ odd.
\end{itemize}



\end{theorem}
\bigskip
Theorem \ref{thmrama} tells us for each prime power in a simple way how to choose divisor sets to obtain an integral circulant graph that is Ramanujan, except for the final case (vii), where the construction is a little more intricate. In this situation, the binary expansion of the lefthand side of (\ref{exception}) is obtained by adding $2^{-\frac{s-3}{2}}$ to the binary expansion of the real constant  $3-2\sqrt{2} = (0.0010101111101100001...)_2$.
Obviously, the sum on the righthand side of (\ref{exception}) is a binary expansion by construction, and in order to generate a Ramanujan graph we just have to pick $\md'$ %the $a_i$ 
appropriately.
Let us %briefly look at 
sketch an example that illustrates what to do explicitly in case (vii):\newline
Consider the prime power $2^{29}$, for which condition (\ref{exception}) turns into
\[
3-2\sqrt{2} +\frac{1}{2^{13}}= (0.0010101111110100001...)_2
\leq \sum_{i=15}^r \frac{1}{2^{a_i-14}}
\]
with $\md' =\{2^{a_{15}},2^{a_{16}},\ldots,2^{a_r}\}$, say.
The parameter $r\geq 15$ may be selected arbitrarily such that $a_r\leq 28$. 
Now for each choice of the $a_i$, $15\leq i \leq r$, it is completely obvious whether the corresponding divisor set $\md'$ generates a Ramanujan graph or not. For instance, $a_{15}=17$, $a_{16}=19$, $a_{17}=21$, $a_{18}=22$, $a_{19}=23$, $a_{20}=24$, $a_{21}=25$, $a_{22}=26$, $a_{23}=27$ generates the Ramanujan graph
\[
\Icg{D(2^{12})\cup\{2^{14},2^{17},2^{19},{2^{21},2^{22},2^{23},{2^{24},2^{25},2^{26},2^{27}\}}}}{2^{29}},
\]
while the divisor set of
\[
\Icg{D(2^{12})\cup\{2^{14},2^{17},2^{19},{2^{21},2^{22},2^{23},{2^{24},2^{25},2^{26},2^{28}\}}}}{2^{29}}
\]
violates (\ref{exception}), and thus the graph is not Ramanujan.



Theorem \ref{thmrama} (i)  immediately implies the following statement.
\begin{corollary}  \label{corollary}
For each prime power $p^s\geq 3$ and all
%there is a (uni-regular) 
divisor sets $\md=\{1,p,\ldots,p^{r-1}\}$ with $\frac{s}{2}\leq r \leq s$ the graph $\Icg{\md}{p^s}$ is Ramanujan. In particular, there is an integral circulant Ramanujan graph $\Icg{\md}{p^s}$ for each prime power $p^s\geq 3$.
\end{corollary}
We like to make the reader aware of the fact that the divisor sets ensuring the Ramanujan property in Corollary \ref{corollary} are \textit{uni-regular} as introduced in \cite{LS2}, where a subset of $D(p^s)$ is called uni-regular if it consists of successive powers of $p$. 






















\section{The second largest eigenvalue of ICGs}



In this section, we shall prove an explicit formula for the second largest modulus of the eigenvalues of an integral circulant graph of prime power order.
Before doing that, let us recall some general facts about $\Icg{\md}{n}$ for arbitrary positive integers $n$ and arbitrary divisor sets $\md\subseteq D(n)$.
\begin{itemize}
\item[(a)] The eigenvalues $\lambda_{k}(n,\md)$ ($1\leq k \leq n$) of the integral circulant graph $\Icg{\md}{n}$ can be calculated by
\begin{equation*} \label{defeigval}
\lambda_{k}(n,\md) = \sum_{d\in \md}\, c\Big(k,\frac{n}{d}\Big)
\quad\quad\quad (1\leq k \leq n),
\end{equation*}
where
\[
c(k,n):=\sum_{\genfrac{}{}{0pt}{1}{j \bmod n}{(j,n)=1}} \exp\Big(\frac{2\pi i\, k j}{n}\Big)
\] 
is the well-known \textit{Ramanujan sum} (cf. \cite{LS2}).
\item[(b)] 
An integral circulant graph $\Icg{\cal D}{n}$ is in fact regular, more precisely $\Phi(n,\md)$-regular, where 
\begin{equation}  \label{capphi}
\Phi(n,\md):= 
\lambda_{n}(n,\md) = \sum_{d \in \md}\varphi\Big(\frac{n}{d}\Big)
\end{equation}
with Euler's totient function $\varphi$.
This can easily be deduced from the Perron-Frobenius Theorem (cf. \cite{GOD}, chapter 8.8) and the fact that $c(n,n)= \varphi(n)$. 
\item[(c)] 
By the observation of {\sc So} \cite{SO} that $\Icg{\md}{n}$ with $\md=\{d_1,\ldots,d_r\}$, say, is connected if and only if $\gcd(d_1,\ldots,d_r)=1$, connectivity can readily be checked. If $\Icg{\md}{n}$ is connected, then $\Phi(n,\md)$ is 
the largest eigenvalue of $\Icg{\md}{n}$, the so-called \textit{spectral radius} of the graph, and it occurs with multiplicity $1$ (cf. \cite{BIG}, Proposition 3.1, or \cite{GOD}, Theorem 8.8.2). 
\end{itemize}






In order to prove Theorem \ref{thmrama}, 
we shall have to check for which $\md\subseteq D^*(p^s)$ %with $1\in \md$ 
the Ramanujan condition 
\begin{equation}
	\label{ramc}
	\Lambda(p^s,\md) :=\Lambda(\Icg{\md}{p^s}) \leq 2 \sqrt{\Phi(p^s,\md)-1}
  \end{equation}
is satisfied (cf. (\ref{defLambda}) and (b)). 
Since Ramanujan graphs are required to be connected, we necessarily have $1\in \md$ for a Ramanujan graph $\Icg{\md}{p^s}$ due to the criterion of {\sc So} (cf. (c)).
While \eqref{capphi} provides an explicit formula for $\Phi(p^s,\md)$, it is just as important to have such a formula for  
$\Lambda(p^s,\md)$.








\begin{proposition}
\label{Lambda}
Let $p^s\geq 3$ be a prime power, and let $\md \subseteq D(p^s)$ with $1\in \md$. Then 
$\Lambda(2^s,\{1\})=0$ for $s\geq 2$, and in all other cases
\[
\Lambda(p^s,\md) = p^{s-1} - \sum_{\genfrac{}{}{0pt}{1}{d\in\md}{d\neq 1}} \varphi\Big(\frac{p^s}{d}\Big),
\]
where the empty sum for $\md=\{1\}$ vanishes. 
\end{proposition}


\begin{proof}
Since $1\in \md$, 
we have  
$\md=\{p^{a_1},p^{a_2},\ldots,p^{a_r}\}$, say, for suitable integers $0= a_1<a_2< \ldots < a_{r-1} < a_r\leq s$.
Writing $k=p^j m,~p\nmid m,$ with suitable integers $j$, $\,0 \leq j \leq s$, and $m\geq 1$ for each $k \in \{1,2,\ldots,p^s\}$, we obtain by Lemma 4.2 in \cite{LS2} that
\begin{align}   \label{lam2}
\begin{split}
\lambda_k(p^s,\md)
&= \sum_{\genfrac{}{}{0pt}{1}{i=1}{a_i \geq s-j}}^{r} \varphi(p^{s-a_i}) -  \sum_{\genfrac{}{}{0pt}{1}{i=1}{a_i=s-j-1}}^{r} p^{s-a_i-1}.  \\
\end{split}
\end{align}
As in the proof of Proposition 4.1 in \cite{LS2}, 
we distinguish several cases.
If $j=s$, that is $k=p^s$, we have $\lambda_k(p^s,\md)=\Phi(p^s,\md)$, which is the largest eigenvalue of $\Icg{\md}{p^s}$ (see (c)) and thus irrelevant for the determination of $\Lambda(p^s,\md)$.
Hence we are left with the following three cases, the last two of which correspond with the cases in the proof of Proposition 4.1 in \cite{LS2}:

\underline{Case 0}:\quad $0\leq j \leq s-a_r-2$.
\newline
Observe that this only occurs if $a_r\leq s-2$. Then (\ref{lam2}) implies  $\lambda_k(p^s,\md)=0$. 

\underline{Case 1}:\quad $s-a_{\ell} \leq j \leq s-a_{\ell-1}-2\;$ for some $2\leq \ell\leq r$.
\newline
Then
\begin{equation*}  \label{case1a}
\lambda_k(p^s,\md) = \sum_{\genfrac{}{}{0pt}{1}{i=1}{a_i \geq a_{\ell}}}^{r} \varphi(p^{s-a_i}) 
=  \Phi(p^s,\md(p^{a_{\ell}})) >0
\end{equation*}
with $\md(x):=\{d\in \md:\, d\geq x\}$.


\underline{Case 2}:\quad $j = s-a_{\ell}-1$ for some $1\leq \ell\leq r$.
\newline
Then, on setting $a_{r+1}:=s+1$ and consequently $\Phi(p^s,\md(p^{a_{r+1}}))=0$, we have
\begin{equation*}  \label{case2a}
\lambda_k(p^s,\md) = \sum_{\genfrac{}{}{0pt}{1}{i=1}{a_i \geq a_{\ell}+1}}^{r} \varphi(p^{s-a_i}) 
- p^{s-a_{\ell}-1} 
=  \Phi(p^s,\md(p^{a_{\ell+1}})) -p^{s-a_{\ell}-1} \leq 0,
\end{equation*}
such that $\vert\lambda_k(p^s,\md)\vert = p^{s-a_{\ell}-1} - \Phi(p^s,\md(p^{a_{\ell+1}}))$.


Let us start by looking at the special case $r=1$, i.e. $\md=\{1\}$, $a_1=0$ and $s\geq 1$. This means that Case 1 never occurs. 
Case 2 does occur for $j=s-1$ with corresponding $\lambda_k(p^s,\md)=p^{s-1}$.
This value equals $\Phi(2^s,\{1\})=\varphi(2^s)=2^{s-1}$ in case $p=2$ (and $s\geq 2$, since $s=1$ is outruled by our condition $p^s\geq 3$), hence $\Lambda(2^s,\{1\})=0$ (originating from Case 0). 
For any $p\geq 3$ and all $s\geq 1$, we have $p^{s-1}< \Phi(p^s,\{1\})$, which proves the Proposition in this situation.

From now on, we assume that $r\geq 2$.
We define
\begin{equation}    \label{m_D}
\mathscr{m}= {\bm{\mathscr{m}}}_{\md} := \left\{ 
                   \begin{array}{cl} 
                     \infty & \mbox{ if $\md$ is uni-regular,} \\ 
                     \min\limits_{\genfrac{}{}{0pt}{1}{2\leq \ell \leq r}{a_{\ell}-a_{\ell-1} \geq 2}} \hspace{-8pt}\ell
                     & \mbox{ otherwise. }  
                   \end{array} \right.
\end{equation}
For $\bm{\mathscr{m}}_{\md}=\infty$, Case 1 does not occur at all. Obviously 
\begin{equation*} \label{case1aa}
\Phi(p^s,\md) \geq \Phi(p^s,\md(p^{a_{\ell}})) > \Phi(p^s,\md(p^{a_{\ell+1}})) > 0
\end{equation*}
for $1\leq \ell \leq r-1$. If $\bm{\mathscr{m}}_{\md}<\infty$, Case 1 occurs for $\ell=\bm{\mathscr{m}}_{\md}$, but for no smaller $\ell$.  Therefore, the only candidate for $\Lambda(p^s,\md)$ originating from Case 1 is $\Phi(p^s,\md(p^{a_{\hspace{-.5pt}\bm{\mathscr{m}}}}))$. 
On the other hand, it is easily seen that 
\[
\Phi(p^s,\md) > p^{s-a_{\ell}-1}-\Phi(p^s,\md(p^{a_{\ell+1}})) \geq p^{s-a_{\ell+1}-1}-\Phi(p^s,\md(p^{a_{\ell+2}})) \geq 0
\]
for $1\leq \ell \leq r-1$. Hence the only candidate for $\Lambda(p^s,\md)$ originating from Case 2 is $p^{s-a_1-1}-\Phi(p^s,\md(p^{a_2}))= p^{s-1}-\Phi(p^s,\md(p^{a_2}))$.
Now let us compare the two candidates for $\Lambda(p^s,\md)$ found above. By the definition of $\bm{\mathscr{m}}=\bm{\mathscr{m}}_{\md}$, we obtain
\begin{align*}
\Phi(p^s,\md(p^{a_2})) + \Phi(p^s,\md(p^{a_{\hspace{-.5pt}\bm{\mathscr{m}}}})) &=
\sum_{i=2}^r \varphi(p^{s-a_i}) + \sum_{i=\bm{\mathscr{m}}}^r \varphi(p^{s-a_i}) \\
&= \sum_{i=2}^{\bm{\mathscr{m}}-1} \varphi(p^{s-a_i}) + 2\sum_{i=\bm{\mathscr{m}}}^r \varphi(p^{s-a_i}) \\
&=  p^{s-a_2}-p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-1} + 2\sum_{i=\bm{\mathscr{m}}}^r \varphi(p^{s-a_i}) \\
&\leq   p^{s-a_2}-p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-1} + 2 p^{s-a_{\hspace{-.5pt}\mathscr{m}}} \leq p^{s-1}.
\end{align*}
This implies $p^{s-1}-\Phi(p^s,\md(p^{a_2}))\geq \Phi(p^s,\md(p^{a_{\hspace{-.5pt}\bm{\mathscr{m}}}}))$, and we have 
\[
\Lambda(p^s,\md) = p^{s-1} -\Phi(p^s,\md(p^{a_2})) = p^{s-1} - \sum_{\genfrac{}{}{0pt}{1}{d\in\md}{d\neq 1}} \varphi\Big(\frac{p^s}{d}\Big).
\]
\end{proof}



Part (ii) of the following result was already proved in Proposition 4.1 (ii) of \cite{LS2}.
\begin{corollary}
\label{compPhiLamb}
Let $p^s\geq 3$ be a prime power, and let $\md \subseteq D(p^s)$ with $1\in \md$.
\begin{itemize}
\item[(i)] Then
\begin{equation}  \label{sumphilam}
\Phi(p^s,\md) + \Lambda(p^s,\md) = \left\{  \begin{array}{ll}
                                       2^{s-1} & \mbox{ if  $p=2$, $s\geq 2$ and $\md=\{1\}$}, \\
                                       p^s & \mbox{ otherwise. }
                                       \end{array}  \right.    
\end{equation}
\item[(ii)]
For all odd primes $p$, we have $\Lambda(p^s,\md)=0$ if and only if $\md=D(p^s)$. 
\end{itemize}
\end{corollary}

\begin{proof} 
The identity \eqref{sumphilam} follows right away from \eqref{capphi} and Proposition \ref{Lambda}. The second assertion is another consequence of Proposition \ref{Lambda}, because  
\[
\sum_{\genfrac{}{}{0pt}{1}{d\in\md}{d\neq 1}} \varphi\Big(\frac{p^s}{d}\Big)
\leq p^{s-1} 
\]
with equality if and only if $\md = D(p^s)$.
\end{proof}




\begin{corollary}
\label{Lambdacor}
Let $p^s\geq 3$ be a prime power, and let $\md \subseteq D^*(p^s)$ with $1\in \md$. Then 
$\Icg{\md}{p^s}$ is Ramanujan if and only if either $p=2$, $s\geq 2$ and $\md=\{1\}$ or, in all other cases, 
\begin{equation}  \label{Lambdacoreq}
\sum_{\genfrac{}{}{0pt}{1}{d\in\md}{d\neq 1}} \varphi\Big(\frac{p^s}{d}\Big)
\geq p^{s-1} -2\sqrt{p^s} +2,
\end{equation}
where the empty sum for $\md=\{1\}$ vanishes.
\end{corollary}

\begin{proof} 
The special case $p=2$, $s\geq 2$ and $\md=\{1\}$ is an immediate consequence of Proposition \ref{Lambda}.
By (\ref{ramc}) and Proposition \ref{Lambda}, it follows in all other situations that $\Icg{\md}{p^s}$ is Ramanujan if and only if 
$\Phi_2:=  %\Phi(p^s,\md(p))=
\sum_{d\in\md,\, d\neq 1} \varphi(\frac{p^s}{d})$ %(using the notation introduced in the proof of Proposition \ref{Lambda}) 
satisfies
\[
p^{s-1} - \Phi_2  \leq 2\sqrt{\Phi(p^s,\md)-1} = 2\sqrt{\varphi(p^s)+\Phi_2-1}.
\]
A short calculation reveals that this is equivalent with (\ref{Lambdacoreq}).
\end{proof}














\section{Proof of Theorem \ref{thmrama}}

Now we shall characterise all integral circulant graphs of prime power order which have the Ramanujan property.


\begin{proof}[Proof of Theorem \ref{thmrama}]
Let us assume that
$\md=\{p^{a_1},p^{a_2},\ldots,p^{a_r}\}$ for suitable integers 
$0\leq a_1<a_1<a_2< \ldots < a_{r-1} < a_r\leq s-1$. 
Since Ramanujan graphs have to be connected by definition, i.e. $1\in \md$, we necessarily have  
%$\md=\{p^{a_1},p^{a_2},\ldots,p^{a_r}\}$, say, for suitable integers 
$a_1=0$. %= a_1<a_2< \ldots < a_{r-1} < a_r\leq s-1$. 

We consider the case $r=1$, i.e. $\md=\{1\}$ separately. We know by Corollary \ref{Lambdacor} that $\Icg{\{1\}}{2^s}$ is Ramanujan for each $s\geq 2$. 
%(cf. upper table of our Theorem). 
For $p\geq 3$, the Ramanujan property requires $p^{s-1}-2p^{s/2}+2\leq 0$ by condition 
(\ref{Lambdacoreq}) of Corollary \ref{Lambdacor}. It is easy to check that this inequality holds if and only if $s=1$ or $s=2$.
%, both cases listed in the upper table as well.
For $r=1$, we thus have exactly the following types of Ramanujan ICGs, which were determined earlier by {\sc Droll} while characterising unitary Cayley Ramanujan graphs (see Theorem 1.2 (a), (b) and part of (d) in \cite{DRO}):
\begin{center}
%\begin{tabular}{lcl}
\begin{tabular}{|c|l|l|}
\hline
	 &	$p^s$ &$\md$ \\\hline\hline
		
	A &	$2^s ~(s \geq 2)$ & $\{1\}$ \\\hline
		
	B &	$p ~~ (p\geq 3)$ & $\{1\}$ \\\hline
		
	C &  $p^2 ~ (p\geq 3)$ & $\{1\}$ \\\hline
		\end{tabular}
\end{center}	
\bigskip	



In the sequel we may assume that $r\geq2$. Since $a_r\leq s-1$, we trivially have 
\[
\sum_{i=2}^r \varphi(p^{s-a_i}) \leq (p^{s-a_2}-p^{s-a_2-1}) +(p^{s-a_2-1}-p^{s-a_2-2})+ \ldots + (p-1) = p^{s-a_2}-1.
\]
Hence, by Corollary \ref{Lambdacor}, a necessary condition for $\Icg{\md}{p^s}$ to be Ramanujan is that
\begin{equation} \label{necess}
p^{s-a_2} \geq p^{s-1}-2\sqrt{p^s}+2.
\end{equation}
Let us first distinguish cases according to the value of $a_2$. If $a_2\geq 3$, thus $s\geq 4$, a simple calculation shows that (\ref{necess}) is never satisfied. Assume next that $a_2=2$, thus $s\geq 3$. It is easily seen that (\ref{necess}) requires $s\leq 5$, and we obtain only the pairs $(s,p)\in \{(3,2),(3,3),(4,2),(5,2)\}$ satisfying (\ref{necess}). Checking our Ramanujan condition (\ref{Lambdacoreq}) explicitly for these pairs, we precisely obtain Ramanujan ICGs as listed below:
\begin{center}
\begin{tabular}{|c|l|l|}
\hline
 &	$p^s$ & $\md$ \\\hline\hline
		
D & $p^3,~ 2\leq p \leq 3$ & $\{1,p^2\}$  \\\hline
		
% $3^3$ & $\{1,3^2\}$ \\\hline
	  
E & $2^4$ & $\{1,2^2\}$ or $\{1,2^2,2^3\}$ \\\hline	     
	  
F & $2^5$ & $\{1,2^2,2^3,2^4\}$ \\\hline
	\end{tabular}
\end{center}		
%as listed in the upper table.
\bigskip










We are left with the case $a_2=1$. Using the notation introduced in (\ref{m_D}), it follows that $\bm{\mathscr{m}}_{\md}\geq 3$, and we shall distinguish between $\bm{\mathscr{m}}_{\md}=\infty$ and $\bm{\mathscr{m}}_{\md}<\infty$. In the first case, i.e. for uni-regular divisor sets $\md$, we have $s\geq 2$ and
\[ 
\sum_{i=2}^r \varphi(p^{s-a_i}) = \sum_{i=2}^r \varphi(p^{s-(i-1)})  = p^{s-1}-p^{s-r}.
\]
Then Corollary \ref{Lambdacor} tells us that $\Icg{\md}{p^s}$ is Ramanujan if and only if
\begin{equation}  \label{cond2a}
p^{s-r} +2 \leq  2\sqrt{p^s}.
\end{equation}
For $s\leq 2r$, this condition is satisfied for all primes $p$, hence we obtain a Ramanujan graph $\Icg{\md}{p^s}$ for each prime power $p^s$ with $s\geq 2$ and uni-regular divisor sets $\md=\{1,p,\ldots,p^{r-1}\}$, where $\frac{s}{2}\leq r \leq s$. %These graphs are listed in the lower table. 
For $s\geq 2r+2$, condition (\ref{cond2a}) does not hold for any prime $p$. For the missing case $s=2r+1$, (\ref{cond2a}) yields the Ramanujan condition $\sqrt{p} +\frac{2}{p^{s/2}} \leq 2$, which is only satisfied for $p=2$ or $p=3$ and all odd $s\geq 5$. Therefore, we have two more types of Ramanujan ICGs:
\begin{center}
\begin{tabular}{|c|l|ll|}
\hline
 &	$p^s$ & $\md$ & \\\hline\hline
		
G &	$p^s ~ (p\in \mathbb{P},~ s\geq 2)$ & $\{1,p,\ldots,p^{r-1}\}$ & $(\min\{2,\frac{s}{2}\} \leq r \leq s)$ \\\hline
	
H &	$p^s ~ (p\in\{2,3\},~ s\geq 5,~2\nmid s)$ & $\{1,p,\ldots,p^{\frac{s-3}{2}}\}$ & \\\hline	
		\end{tabular}	
\end{center}
\bigskip


Now let us consider the case $\bm{\mathscr{m}}=\bm{\mathscr{m}}_{\md}<\infty$. We have 
\begin{align*}
\sum_{i=2}^r \varphi(p^{s-a_i}) = \sum_{i=2}^{\bm{\mathscr{m}}-1} \varphi(p^{s-a_i}) + \sum_{i=\bm{\mathscr{m}}}^r \varphi(p^{s-a_i})  
= p^{s-1}-p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-1} + \sum_{i=\bm{\mathscr{m}}}^r \varphi(p^{s-a_i}).  
\end{align*}
Then, by Corollary \ref{Lambdacor}, $\Icg{\md}{p^s}$ is Ramanujan if and only if
\begin{equation}  \label{cond2}
p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-1} +2 \leq  2\sqrt{p^s} + \sum_{i=\bm{\mathscr{m}}}^r \varphi(p^{s-a_i}).
\end{equation}
For $s\leq 2(a_{\bm{\mathscr{m}}-1}+1)$, i.e. $\frac{s}{2}\geq s-a_{\bm{\mathscr{m}}-1}-1$, the Ramanujan condition (\ref{cond2}) is satisfied for all primes $p$. By definition of $\bm{\mathscr{m}}=\bm{\mathscr{m}}_{\md}$, we have $a_{\bm{\mathscr{m}}-1}=\bm{\mathscr{m}}-2$. Hence $\Icg{\md}{p^s}$ is Ramanujan for any prime power $p^s$ and $\md=\{1,p,\ldots,p^{\bm{\mathscr{m}}-2},p^{a_{\hspace{-.5pt}\bm{\mathscr{m}}}},\ldots,p^{a_r}\}$, if $3\leq \bm{\mathscr{m}}\leq r$ satisfies $s\leq 2(\bm{\mathscr{m}}-1)$ and $a_{\bm{\mathscr{m}}}\geq \bm{\mathscr{m}}$, which requires $s\geq 4$. %and the corresponding Ramanujan ICGs are found in the lower table.
Setting $\ell := \bm{\mathscr{m}}-1$, we have found the next type of Ramanujan ICGs:
\begin{center}
\begin{tabular}{|c|l|ll|}
\hline
&	$p^s$ & $\md$ & \\\hline\hline
		
I &	$p^s ~ (p\in \mathbb{P},~ s\geq 4)$ & $\{1,p,\ldots,p^{\ell-1},p^{a_{\ell+1}},\ldots,p^{a_r}\}$ & $(\frac{s}{2} \leq \ell \leq a_{\ell+1}-1)$ \\\hline
		\end{tabular}	
\end{center}
\bigskip



For $s\geq 2(a_{\bm{\mathscr{m}}-1}+3)$, i.e. $\frac{s}{2}\leq s-a_{\bm{\mathscr{m}}-1}-3$, we obtain for all primes $p$
\[
p+\frac{2}{p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-1}}   > \; 2 \; \geq \frac{p^{\frac{s}{2}+1}}{p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-2}} +1
\geq \frac{2p^{\frac{s}{2}}}{p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-2}} +1,
\]
hence
\begin{align*}
p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-1} +2 &= p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-2} \left(p+\frac{2}{p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-2}}\right) \\
& >  p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-2} \left( \frac{2p^{\frac{s}{2}}}{p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-2}} +1 \right) 
= 2p^{\frac{s}{2}} + p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}-2} \\
&\geq  2p^{\frac{s}{2}} + p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}}}  
>  2\sqrt{p^s} + \sum_{i=\bm{\mathscr{m}}}^r \varphi(p^{s-a_i}).
\end{align*}
This contradicts (\ref{cond2}), which means that there are no Ramanujan graphs in this situation.


















It remains to consider the three special cases $s=2(a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}+1)+j$ with $j\in\{1,2,3\}$. This turns (\ref{cond2}) into the Ramanujan condition
\begin{equation}  \label{cond3}
p^{\frac{j}{2}} -2  \leq \frac{1}{p^{a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}+1+\frac{j}{2}}}
\left(\sum_{i=\bm{\mathscr{m}}}^r \varphi(p^{s-a_i}) -2\right).
\end{equation}
By definition of $\bm{\mathscr{m}}=\bm{\mathscr{m}}_{\md}$, we know that $a_{\bm{\mathscr{m}}}\geq a_{\bm{\mathscr{m}}-1}+2$. 
Since
\[
\sum_{i=\bm{\mathscr{m}}}^r \varphi(p^{s-a_i}) \leq p^{s-a_{\hspace{-.5pt}\bm{\mathscr{m}}}} -1 \leq p^{2(a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}+1)+j -(a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}+2)} -1 =p^{a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}+j}-1,
\]
careful calculations reveal that %for $a_m\geq a_{m-1}+3$ 
condition (\ref{cond3}) can only be satisfied for the pairs $(j,p)\in \{(1,2),(1,3),(1,5),(2,2),(3,2)\}$.
%three pairs $(j,p)\in \{(1,2), (1,3), (2,2)\}$, 
%where for $(j,p)=(2,2)$ the case $a_m=a_r=s-1$ has to be excluded. 
For the first two pairs, corresponding with $a_{\bm{\mathscr{m}}-1}=\frac{s-3}{2}$, the lefthand side of (\ref{cond3}) is negative, while the righthand side is non-negative except for the special case $p=2$ and $a_{\bm{\mathscr{m}}}=a_r=s-1$. However, a closer look shows that in this latter situation (\ref{cond3}) is still satisfied, and we obtain Ramanujan graphs $\Icg{\md}{p^s}$ for $p\in\{2,3\}$, where $\md = \{1,p,\ldots,p^{\frac{s-3}{2}},p^{a_{\frac{s+1}{2}}},\ldots,p^{a_r}\}$ with $a_{\frac{s+1}{2}}=a_{\bm{\mathscr{m}}} \geq a_{\bm{\mathscr{m}}-1}+2 =\frac{s-3}{2}+2 = \frac{s+1}{2}$, thus $s\geq 5$. 
Inserting the third pair $j=1$ and $p=5$ into (\ref{cond3}), a short computation discloses that the corresponding ICGs are Ramanujan if and only if $a_{\bm{\mathscr{m}}}=a_{\bm{\mathscr{m}}-1}+2$, and then $\md = \{\{1,5,\ldots,5^{\frac{s-3}{2}},5^{\frac{s+1}{2}},\ldots,5^{a_r}\}$ with $s\geq 5$.
To sum up, the Ramanujan ICGs for $(j,p)\in \{(1,2),(1,3),(1,5)\}$ are the following:
\begin{center}
\begin{tabular}{|c|l|ll|}
\hline
 &	$p^s$ & $\md$ & \\\hline\hline
	
J & $p^s ~ (p\in\{2,3\},~ s\geq 5,~2\nmid s)$ & $\{1,p,\ldots,p^{\frac{s-3}{2}},p^{a_{\frac{s+1}{2}}},\ldots,p^{a_r}\}$ & $(a_{\frac{s+1}{2}}\geq \frac{s+1}{2})$ \\\hline	

K & $5^s ~ (s\geq 5,~2\nmid s)$ & $\{1,5,\ldots,5^{\frac{s-3}{2}},5^{\frac{s+1}{2}},5^{a_{\frac{s+3}{2}}},\ldots,5^{a_r}\}$ &  \\\hline	

	\end{tabular}
\end{center}		
\bigskip
For $j=p=2$, the Ramanujan condition (\ref{cond3}) reads $\sum_{i=\bm{\mathscr{m}}}^r \varphi(p^{s-a_i}) \geq 2$, and this always holds unless $a_{\hspace{-.5pt}\bm{\mathscr{m}}}=a_r=s-1$, i.e.  
we obtain Ramanujan ICGs of type
\begin{center}
\begin{tabular}{|c|l|ll|}
\hline
&	$p^s$ & $\md$ & \\\hline\hline
		
L &	$2^s ~ (s\geq 6,~2\mid s)$ & $\{1,2,\ldots,2^{\frac{s-4}{2}},2^{a_{\frac{s}{2}}},\ldots,2^{a_r}\}$ & $(\frac{s}{2}\leq a_{\frac{s}{2}}\leq s-2)$\\\hline	

		\end{tabular}	
\end{center}
\bigskip
We are left with the case $j=3$ and $p=2$, where $s=2a_{\bm{\mathscr{m}}-1}+5 = 2(\bm{\mathscr{m}}-2)+5=2\bm{\mathscr{m}}+1$, and our Ramanujan condition (\ref{cond3}) becomes
\begin{align*}
2\sqrt{2}-2 
&\leq  \frac{1}{2^{a_{\hspace{-.5pt}\bm{\mathscr{m}}-1}+\frac{5}{2}}}
\left(\sum_{i=\bm{\mathscr{m}}}^r \varphi(2^{s-a_i}) -2\right) \\
&= \frac{1}{2^{\bm{\mathscr{m}}}\sqrt{2}}
\left(\sum_{i=\bm{\mathscr{m}}}^r 2^{s-a_i-1} -2\right)
= \frac{1}{\sqrt{2}} \left(\sum_{i=\bm{\mathscr{m}}}^r \frac{1}{2^{a_i-\bm{\mathscr{m}}}} -\frac{1}{2^{\bm{\mathscr{m}}-1}}\right).
\end{align*}
This is equivalent with
$
4-2\sqrt{2} \leq \sum_{i=\bm{\mathscr{m}}}^r \frac{1}{2^{a_i-\bm{\mathscr{m}}}} -\frac{1}{2^{\bm{\mathscr{m}}-1}}\,,
$
where we know that $a_i\geq i$ for all $i\geq \bm{\mathscr{m}}$. This immediately implies that the Ramanujan condition necessarily requires that $a_{\bm{\mathscr{m}}}=\bm{\mathscr{m}}$. Then our condition reads
\begin{equation} \label{finalramacond}
3-2\sqrt{2} \leq \sum_{i=\bm{\mathscr{m}}+1}^r \frac{1}{2^{a_i-\bm{\mathscr{m}}}} -\frac{1}{2^{\bm{\mathscr{m}}-1}}
= \sum_{i=\frac{s+1}{2}}^r \frac{1}{2^{a_i-\frac{s-1}{2}}} -\frac{1}{2^{\frac{s-3}{2}}} \,,
\end{equation}
and we have found our last type of Ramanujan ICGs
\begin{center}
\begin{tabular}{|c|l|ll|}
\hline
&	$p^s$ & $\md$ & \\\hline\hline
		
M &	$2^s ~ (s\geq 5,~2\nmid s)$ & $\{1,2,\ldots,2^{\frac{s-5}{2}},2^{\frac{s-1}{2}},2^{a_{\frac{s+1}{2}}},\ldots,2^{a_r}\}$ & $(a_{\frac{s+1}{2}},\ldots,a_r \mbox{ satisfy (\ref{finalramacond})})$\\\hline	
		\end{tabular}	
\end{center}









To complete the proof of Theorem \ref{thmrama} it remains to show that the Ramanujan ICGs of types A-M exactly constitute the Ramanujan graphs listed in the assertion.
The following table provides the interrelations between types A-M on one hand and cases (i)-(vii) on the other hand.
\begin{center}
\begin{tabular}{|c|l|}
\hline
%\\\hline\hline
(i) &  A $(s=2)$, B ($s=1$), C ($s=2$), G (s$\geq 2$), I ($s\geq 4$)  \\\hline
	  
(ii) &  A ($s\geq 3$) \\\hline	     
	  
(iii) &  D ($s=3$), H ($s\geq 5$ odd),  J ($s\geq 5$ odd)   \\\hline

(iv) &  E ($s=4$), L ($s\geq 6$ even) \\\hline
	  
(v) &  F ($s=5$) \\\hline	     
	  
(vi) &  K ($s\geq 5$ odd)\\\hline

(vii) &  M ($s\geq 5$ odd)\\\hline
	\end{tabular}
\end{center}
\end{proof}




















\begin{thebibliography}{10}



\bibitem{AHM}
O. Ahmadi, N. Alon, I.~F. Blake and I.~E. Shparlinski.
\newblock Graphs with integral spectrum.
\newblock
{\em Linear Algebra Appl.} 430:547--552, 2009.


\bibitem{AlBo} N. Alon.
\newblock Eigenvalues and expanders.
\newblock {\em Combinatorica} 6:83--96, 1986.


\bibitem{ANG} R.~J. Angeles-Canul, R. Norton, M. Oppermann, C. Paribello, M. Russel and C. Tamon.
\newblock Perfect state transfer, integral circulants and join of graphs.
\newblock {\em Quantum Inf. Comput.} 10:325--342, 2010. 


\bibitem{BIE} F. Bien.
\newblock Constuction of Telephone Networks by Group Representations.
\newblock {\em Notices of the Amer. Math. Society} 36(1):5--22, 1989.


\bibitem{BIG} N.~L. Biggs, 
\newblock {\em Algebraic Graph Theory}.
\newblock 2nd edition, Cambridge University Press, Cambridge, 1993.


\bibitem{BOP} R.~B. Boppana. 
\newblock Eigenvalues and graph bisection: an average case analysis.
\newblock  In {\em Proc. 28th Annual Symp. Found. Comp. Sci.}, pages 280--285. IEEE, 1987.


\bibitem{BRU} R.A. Brualdi.
\newblock {\em Energy of a graph}.
\newblock AIM Workshop Notes, 2006.



\bibitem{DRO} A. Droll.
\newblock A classification of Ramanujan unitary Cayley graphs.
\newblock {\em  Electronic J. Combin.} 17,  \#N29, 2010.

%
\bibitem{GOD} C. Godsil and G. Royle.
\newblock
{\em Algebraic graph theory}.
\newblock Vol. 207 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2001.



\bibitem{GUT} I. Gutman.
\newblock {\em The energy of a graph}.
\newblock Ber. Math.-Stat. Sekt. Forschungszent. Graz 103, 1978.


\bibitem{HLW} Sh. Hoory, N. Linial, A.Wigderson.
\newblock Expander graphs and their applications.
\newblock {\em  Bull. Amer. Math. Soc.} 43(4):439--561, 2006.
 

\bibitem{ILI} A. Ili\'{c}.
\newblock Distance spectra and distance energy of integral circulant graphs.
\newblock {\em Linear Algebra Appl.} 433:1005-1014, 2010.


\bibitem{KLO} W. Klotz and T. Sander.
\newblock Some properties of unitary Cayley graphs.
\newblock {\em   Electron. J. Combin.} 14, \#R45, 2007.


\bibitem{LS2} T.~A. Le and J.~W. Sander.
\newblock Extremal energies of integral circulant graphs via multiplicativity.
\newblock {\em Linear Algebra Appl.} 437:1408--1421, 2012.


\bibitem{LPS} A. Lubotzky, R. Phillips and P. Sarnak.
\newblock Ramanujan  graphs.
\newblock {\em Combinatorica} 8:261--277, 1988.


\bibitem{MUR} M.~R. Murty.
\newblock Ramanujan graphs.
\newblock {\em J. Ramanujan Math. Soc.} 18:33--52, 2003.


\bibitem{SA1} J.~W. Sander and T. Sander. 
\newblock The energy of integral circulant graphs with prime power order.
\newblock {\em App. Anal. Discrete Math.} 5:22--35, 2011.


\bibitem{SA2} J.~W. Sander and T. Sander. 
\newblock Integral circulant graphs of prime power order with maximal energy.
\newblock {\em Linear Algebra Appl.}  435:3212--3232, 2011.


\bibitem{SA5} J.~W. Sander and T. Sander.
\newblock The exact maximal energy of integral circulant graphs with prime power order.
\newblock {\em Contributions to Discr. Math.} (to appear).


\bibitem{SAX} N. Saxena, S. Severini and I.~E. Shparlinski.
\newblock Parameters of integral circulant graphs and periodic quantum dynamics.
\newblock {\em Int. J. Quantum Inf.} 5:417--430, 2007.        


\bibitem{SHP} I. Shparlinski.
\newblock On the energy of some circulant graphs.
\newblock {\em Linear Algebra Appl.} 414:378--382, 2006.


\bibitem{SO} W. So.
\newblock  Integral circulant graphs.
\newblock {\em Discrete Math.} 306:153--158, 2005.




\end{thebibliography}

\end{document}