% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.19}{24(3)}{2017}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

\usepackage{mathrsfs}
\usepackage{latexsym}
\usepackage{amsfonts}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,
linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{notation}[theorem]{Notation}%
\newtheorem{construction}[theorem]{Construction}%

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}



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

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

\title{\bf New constructions of self-complementary\\
 Cayley graphs}

% 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{Lei Wang\thanks{Supported by NASA grant ABC123.}\\
\author{Lei Wang\\
\small Beijing International Center\\[-0.8ex]
\small for Mathematical Research\\[-0.8ex]
\small Peking University\\[-0.8ex]
\small Beijing, 100871, P. R. China.\\ %\\[-0.9ex]
\small\tt wanglei-2468@163.com%\\[-1.0ex]
\and
% \author{Lei Wang\thanks{Supported by NASA grant ABC123.}\\
Cai Heng Li\\
\small Department of Mathematics\\[-0.8ex]
\small South University of Science and Technology\\[-0.8ex]
\small Shenzhen, Guangdong 518055, P. R. China\\ %\\[-0.8ex]
\small\tt lich@sustc.edu.cn%\\[-1.0ex]
\\
\and
Yin Liu\\
\small Department of Mathematics\\[-0.8ex]
\small Yunnan Normal University\\[-0.8ex]
\small Kunming, Yunnan 650500, P. R. China\\
\small\tt liuyinjiayou@sina.com
\and
Ci Xuan Wu\\
\small School of Statistics and Mathematics\\[-0.8ex]
\small Yunnan University of Finance and Economics\\[-0.8ex]
\small Kunming, Yunnan 650221, P. R. China\\
\small\tt wucixuan@gmail.com
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Dec 20, 2016}{Jul 17, 2017}{Jul 28, 2017}\\
\small Mathematics Subject Classifications:
Primary~05C25; Secondary~05E18}

\renewcommand{\proof}{\par\noindent{\it Proof.\ \ }}
\def\qed{\ifmmode\square\else\nolinebreak\hfill
$\Box$\fi\par\vskip12pt}

\def\ov{\overline} \def\un{\underline}
\def\l{\langle} \def\r{\rangle} \def\tr{{\rm tr}}
\def\div{\,\big|\,} \def\ddiv{\,\big\Vert\,}\def\notdiv{{\,\not\big|\,}}

\def\FF{\mathbb F}
\def\VV{\mathbb V}

\def\ZZ{{\rm C}}


\def\BB{{\mathcal B}} \def\CC{{\mathcal C}}\def\PP{{\mathcal P}}
\def\TT{{\mathcal T}}
\def\MM{{\mathcal M}} \def\CC{{\mathcal C}}
\def\PP{{\mathcal P}}  \def\SS{{\mathbb S}}

\def\calF{\mathbb F} \def\calZ{\mathbb Z} \def\calV{\mathbb V}
\def\calB{{\mathcal B}} \def\calC{{\mathcal C}}\def\calP{{\mathcal P}}
\def\calT{{\mathcal T}}
\def\calM{{\mathcal M}} \def\calS{{\mathbb S}}

\def\rmS{{\rm S}}

\def\soc{{\sf soc}} \def\Inndiag{{\sf InnDiag}}
\def\rad{{\sf rad}}

\def\HA{{\rm HA}} \def\HS{{\rm HS}} \def\HC{{\rm HC}}
\def\AS{{\rm AS}} \def\PA{{\rm PA}} \def\TW{{\rm TW}}
\def\SD{{\rm SD}} \def\CD{{\rm CD}}

\def\NQ{{\rm NQ}}

\def\PG{{\rm PG}}
\def\D{{\rm D}} \def\Q{{\rm Q}}
\def\S{{\rm S}} \def\G{{\rm G}}
\def\J{{\rm J}} \def\M{{\rm M}}
\def\rmF{{\rm F}}

\def\C{{\bf C}} \def\N{{\bf N}}
\def\Z{{\bf Z}} \def\O{{\bf O}}

\def\rmC{{\rm C}}
\def\rmO{{\rm O}}

\def\mod{{\sf mod~}} \def\core{{\sf core}}
\def\val{{\sf val}} \def\dia{{\sf diam}}
\def\Ker{{\sf Ker}}
\def\Aut{{\sf Aut}} \def\Inn{{\sf Inn}} \def\Out{{\sf Out}}
\def\Cay{{\sf Cay}}
\def\Cos{{\sf Cos}}
\def\Diag{{\sf Diag}}
\def\twr{{\sf twr}}

\def\K{{\bf K}}
\def\bfK{{\bf K}}

\def\bfi{{\tt i}}

\def\Ga{{\it \Gamma}}
\def\Ome{{\it \Omega}}
\def\Sig{{\it \Sigma}}
\def\Del{{\it \Delta}}
\def\char{\,{\sf char}\,}

\def\calO{{\mathcal O}}


\def\a{\alpha} \def\b{\beta} \def\d{\delta}\def\g{\gamma} \def\s{\sigma}
\def\t{\tau} \def\o{\omega} \def\va{\varepsilon} \def\ti{\tilde}

\def\GF{{\rm GF}}
\def\POmega{{\rm P}{\Omega}}
\def\Sp{{\rm Sp}}\def\PSp{{\rm PSp}}
\def\GammaL{{\rm \Gamma L}}
\def\AGammaL{{\rm A\Gamma L}}
\def\PGammaL{{\rm P\Gamma L}}
\def\PSigmaL{{\rm P\Sigma L}}
\def\A{{\rm A}}
\def\Sym{{\rm Sym}}
\def\Sy{{\rm S}}
\def\Ree{{\rm Ree}}
\def\Sz{{\rm Sz}}
\def\ord{{\rm ord}}
\def\Cay{{\rm Cay}}

\def\B{{\rm B}}
\def\PSL{{\rm PSL}}\def\PGL{{\rm PGL}}
\def\GL{{\rm GL}} \def\SL{{\rm SL}} \def\L{{\rm L}}
\def\AGL{{\rm AGL}}
\def\U{{\rm U}} \def\PSU{{\rm PSU}} \def\SU{{\rm SU}} \def\GU{{\rm GU}}
\def\Sz{{\rm Sz}} \def\McL{{\rm McL}} \def\He{{\rm He}}
\def\Ru{{\rm Ru}} \def\Th{{\rm Th}}
\def\E{{\rm E}} \def\F{{\rm F}} \def\D{{\rm D}} \def\G{{\rm G}}
\def\Suz{{\rm Suz}} \def\BM{{\rm BM}}
\def\Co{{\rm Co}} \def\HN{{\rm HN}} \def\Fi{{\rm Fi}}
\def\HS{{\rm HS}}


\begin{document}

\maketitle


\begin{abstract}
Self-complementary Cayley graphs are useful
in the study of Ramsey numbers,
but they are relatively very rare and hard to construct.
In this paper, we construct several families of new self-complementary Cayley graphs of order $p^4$
where $p$ is a prime and congruent to $1$ modulo $8$.

  % keywords are optional
\bigskip\noindent\textbf{Keywords:}
\small {self-complementary graph; Cayley graph;
lexicographic product; fixed-point-free automorphism.}
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
Throughout this paper, all graphs are
assumed to be undirected and simple.
A graph $\Ga=(V,E)$ consists of a vertex
set $V$ and an edge set $E$ which is a subset of the set $\{\{u,v\}\div u,v\in V,u\not=v\}$.
The complement $\ov\Ga$ of a graph $\Ga$
is the graph with the same vertex set $V$ such that
$\{u,v\}$ is an edge of $\ov\Ga$ if and only if $u\not=v$, and $\{u,v\}$ is not an edge of $\Ga$.
A graph $\Ga$ is called vertex-transitive
if $\Aut\Ga$ is transitive on $V$,
$\Ga$ is called self-complementary if
it is isomorphic to its complement graph, and an
isomorphism from $\Ga$ to $\ov\Ga$ is
called a complementary isomorphism of $\Ga$.

The graphs that are both self-complementary and
vertex-transitive are said to be
self-complementary vertex-transitive graphs.
One of the motivations of
studying self-complementary
vertex-transitive graphs is
to investigate Ramsey numbers.
For a positive integer $m$,
we wish to construct a graph $\Ga$
with vertex set $V$ such that neither
$\Ga$ nor $\ov\Ga$ contains a complete
subgraph $\K_m$ and $|V|$ is as big as possible. By intuition,
the distribution of pairs of elements of $V$ between $\Ga$ and $\ov\Ga$ should be ``balanced" so that
$\Ga$ and $\ov\Ga$ should not be very different. In the extreme case, $\Ga\cong \ov\Ga$. Furthermore,
since any induced subgraph of $\Ga$ is not isomorphic to $\K_m$,
the edges of $\Ga$ should be distributed ``homogeneously".
In the ideal case, $\Ga$ is vertex-transitive. Because of this,
self-complementary vertex-transitive graphs have been effectively
used as models to find good lower bounds of Ramsey numbers
(see \cite{Ramsey-Th,Clapham,Gulden,Rodl} for references).

The research of self-complementary
vertex-transitive graphs has a long history (see
the excellent survey of Beezer~\cite{Beezer}).
In 1962,  Sachs~\cite{Sachs}
constructed the first families of
self-complementary circulants
(that is, where the automorphism group
contains a transitive cyclic subgroup),
and since then this class of graphs has
been extensively studied (refer to \cite{Figueroa,Mathon,Rao,Zelinka}).
In 1990s, the orders of general self-complementary
vertex-transitive graphs
were completely determined by Muzychuck~\cite{Muzychuck},
and we also refer to the earlier
work in \cite{Alspach,FRJ} for the
orders of self-complementary circulants.
More constructions and characterisations of self-complementary vertex-transitive graphs can be
found in \cite{Jajcay,c-gps,Xujing,Liskovets}.
In 2001, Li and Praeger \cite{non-Cay-SC} constructed the first family of self-complementary vertex-transitive
graphs which are not Cayley graphs. After 2001,  the study of self-complementary vertex-transitive graphs has been
significantly developed by Li and Praeger~\cite{Tod}
and their joint work with Guralnick and Saxl~\cite{GLPS}
for the vertex-primitive case.
More recently, self-complementary vertex-transitive
graphs of order $pq$
where $p,q$ are primes are classified \cite{Rao-pq}, and
self-complementary metacirculants are studied
in \cite{Rao-meta}, which
form a subclass of self-complementary
vertex-transitive graphs.

To the best of our knowledge, examples of self-complementary
vertex-transitive graphs seem relatively rare and hard to construct.
In this paper, we present serval families of self-complementary
Cayley graphs of non-abelian and non-metacyclic
$p$-groups of order $p^4$. Our main
result in some sense complements the work of the second author
(with other collaborators) who has
constructed a family of self-complementary Cayley
graphs of nonabelian metacyclic $p$-groups (forthcoming).

\begin{theorem}\label{maint}
Let $G$ be a non-abelian and non-metacyclic $p$-group
of order $p^4$, where $p\equiv1\,(\mod 8)$
is a prime. Then there exist self-complementary Cayley graphs of $G$.
\end{theorem}



This paper is organized as follows. After this introduction, we give some preliminary results on both graph
theory and group theory in Section 2,
and subsequently construct some new examples of self-complementary Cayley graphs in
Section 3 and  in Section 4, respectively. Finally, we  summarize
the constructions in Section 5.


\section{Preliminaries}
In this section, we define some notation and
quote some preliminary results which will
be used later.

\subsection{Self-complementary graphs}
Let $\Ga=(V,E)$ be a self-complementary graph,
and let $\s\in\Sym(V)$ be a complementing
isomorphism from $\Ga$ to $\ov\Ga$.
Then $\s$ interchanges $\Ga$ and $\overline\Ga$,
and has order $o(\s)=2^eb$
for $e\geqslant 1$, where $b$ is an odd number.
Observe that $\s=\s^b\cdot\s^{1-b}$,
where $\s^b$ is a complementing isomorphism
of $2$-power order and $\s^{1-b}\in\Aut\Ga$.
Thus we may assume a complementary isomorphism
$\s$ to be of $2$-power order.
If $\s$ is  of order $2$, then $\s$
interchanges some vertices $u,v$ and fixes $\{u,v\}$,
which is impossible. So $4$ divides the order of $\s$.



\begin{lemma}\label{4}
A complementing isomorphism of a
self-complementary graph has order divisible by $4$.
\end{lemma}

For a regular self-complementary graph of
order $n$, a vertex has an equal number
of neighbours and non-neighbours,
and hence $n$ must be an odd number. Furthermore,
the graph has precisely half number of
edges of the complete graph, and so $n(n-1)/4$
is an integer, and $n\equiv1(\,\mod 4)$.

\begin{lemma}\label{regular}
The order of a regular self-complementary
graph is congruent to $1(\,\mod 4)$. % (modulo $4$).
\end{lemma}

%\vskip0.07in
We next introduce a classical method for
constructing self-complementary graphs.
For a finite group $G$, let $G^\#{:}=G\setminus\{1\}$,
the set of all non-identity elements of $G$.
For a subset $S\subseteq G^\#$ with $S=S^{-1}{:}=\{s^{-1}\div s\in S\}$,
the associated  {\it Cayley graph} $\Cay(G,S)$ is the graph
with vertex set $V=G$ and edge set
$E=\{\{a,b\}\div a,b\in G, ba^{-1}\in S\}$.

By the definition, the complement of
the Cayley graph $\Cay(G,S)$ is $\Cay(G,G^\#\setminus S)$.
Let $\Ga=\Cay(G,S)$. Then each automorphism
$\s\in \Aut(G)$ induces
an isomorphism from
$\Cay(G,S)$ to $\Cay(G,S^\s)$.
Hence, if there exist a subset
$S\subset G^\#$ and an automorphism $\s\in \Aut(G)$ such that
\[\mbox{$S^\s=G^\#\setminus S$},\]
then $\Ga$ is self-complementary, and
$\s$ is a complementing isomorphism because
\[\Ga=\Cay(G,S)\cong\Cay(G,S^\s)=\Cay(G,G^\#\setminus S)=\overline\Ga.\]
We call such a subset $S$ an {\it SC-subset}
(short form for self-complementing subset),
and such an automorphism $\s$ a normal complementing isomorphism.
For convenience, we shall refer such a
self-complementary Cayley graph as an {\it SCI graph}
of $G$ (SCI stands for {\it Self-complementary Cayley Isomorphism}).

\vskip0.07in
Another construction method of self-complementary
vertex-transitive graphs is
based on the so-called {\it lexicographic product}
(sometimes called the {\it wreath product}).
In general, for a graph $\Ga_1$ with vertex
set $V_1$ and a graph $\Ga_2$ with vertex set $V_2$,
the lexicographic product $\Ga_1[\Ga_2]$ is the graph
with vertex set $V_1\times V_2$ such that two vertices
$(u_1,u_2)$ and $(v_1,v_2)$ are adjacent if and only
if  either $u_1$ is adjacent to $v_1$ in $\Ga_1$
or $u_1=v_1$ and $u_2$ is adjacent in $\Ga_2$ to $v_2$.
The lexicographic product provides a method for
constructing self-complementary graphs based
on the following properties
(see \cite{Beezer} for references).

\begin{lemma}\label{lexico}
If both $\Ga_1$ and $\Ga_2$ are self-complementary
(vertex-transitive),
then so is $\Ga_1[\Ga_2]$.
\end{lemma}


\subsection{\texorpdfstring{Finite $p$-groups.}{Finite p-groups.}}
For a finite group $G$, the Frattini
subgroup $\Phi(G)$ of
$G$ is defined to be the intersection of all maximal
subgroups. An element $g$ of $G$ is called
a nongenerator of $G$ if $G=\l T,g\r$
implies $G=\l T\r$ for any subset $T$ of $G$.

\begin{lemma}\label{Robinson1}
{\rm (\cite[5.2.12]{Robinson})}
If $G$ is a finite, then % $G$, 
$\Phi(G)$ equals
the set of nongenerators of $G$.
\end{lemma}

Let $G$ be a finite $p$-group.
Denote by $G'$ the derived subgroup of $G$.
Set $G^p=\l g^p\div g\in G\r$.
The following lemma is called the Burnside Basis Theorem:

\begin{lemma}\label{Robinson2}
{\rm(\cite[5.3.2]{Robinson})}
Let $G$ be a finite $p$-group, where $p$ is a prime.
 Then $\Phi(G)=G'G^p$. If $|G{:}\Phi(G)|=p^r$,
then every generating set of $G$ has a
subset of $r$ elements which also generates $G$. In
particular, $G/\Phi(G)=\ZZ_p^r$, which is
elementary abelian of order $p^r$.
\end{lemma}

Let $G$ be a finite $p$-group.
Denote by $c(G)$ the nilpotent class of $G$.
%Clearly,  $c(G)<n$ if $|G|=p^n$, and $G$ is abelian if and only if $c(G)=1$.
The exponent of $G$ is
the largest order of the elements in $G$,
denoted by ${\rm exp}(G)$. The group
$G$ is called $p$-abelian if
$(xy)^p=x^py^p$ for any $x,y\in G$.

\begin{lemma}\label{Brisley}{\rm(\cite[Theorem~3.1]{Brisley})}
Let $G$ be a finite $p$-group which is generated by two
elements and whose derived subgroup $G'$ is abelian.
Then $G$ is $p$-abelian if and only if
${\rm exp}(G')\leqslant p$ and $c(G)<p$.
\end{lemma}

For an odd prime $p$ and a positive integer $m$,
we write  $p_{+}^{1+2m}$ for the extraspecial
group of exponent $p$, and
$p_{-}^{1+2m}$ for the one of exponent $p^2$.
A classification of the non-abelian groups of
order $p^4$ for an odd prime $p$ was
given by Huppert
\cite[Chapter~3, Theorem~12.6 and Exercise~
29]{Huppert}. Thus we have the following lemma.

\begin{lemma}\label{Huppert}
Let $p$ be an odd prime and $G$ a non-abelian
and non-metacyclic group of
order $p^4$. Then $G$ is one of
the following groups:
\begin{itemize}
\item[\rm(1)]
$G_1(p)=\l a,b\div a^{p^2}=b^p=c^p=1,
[a,b]=c,[c,a]=[c,b]=1\r$;

\item[\rm(2)]
$G_2(p)=\l a,b,c\div a^{p^2}=b^p=c^p=1,
[b,c]=a^p,[a,b]=[a,c]=1\r$;

\item[\rm(3)]
$G_3(p)=\l a,b\div a^{p^2}=b^p=c^p=1,
[a,b]=c,[c,a]=a^p,[c,b]=1\r$;

\item[\rm(4)]
$G_4(p)=\l a,b\div a^{p^2}=b^p=c^p=1,
[a,b]=c,[c,a]=1,[c,b]=a^{\nu p}\r$,
where $\nu$ is $1$ or a non-quadratic residue modulo $p$;

\item[\rm(5)]
$G_5(p)=\l a,b\div a^p=b^p=c^p=d^p=1,[a,b]=c,[c,b]=d,
[a,d]=[b,d]=[c,d]=[c,a]=1\r$ for $p>3$;

\noindent $G_5(3)=\l a,b,c\div a^9=b^3=c^3=1,[a,b]=1,[a,c]=b,[b,c]=a^{-3}\r$;

\item[\rm(6)]
$G_6(p)=p_{-}^{1+2}\times\ZZ_p$,
where $\ZZ_p$ is cyclic of order $p$;

\item[\rm(7)]
$G_7(p)=p_{+}^{1+2}\times\ZZ_p$.

\end{itemize}
\end{lemma}

\section{SCI graphs}
In this section, we will construct
self-complementary Cayley graphs via
fixed-point-free automorphisms of groups of order $p^4$,
where $p$ is an odd prime.
Lemma~\ref{fpf-cons-scvt} below provides a generic
method for constructing self-complementary
Cayley graphs based on fixed-point-free automorphisms of groups.
The following lemma is possibly known.
As the authors find no proper references, a proof is given.

\begin{lemma}\label{fpf-cons-scvt}
Let $G$ be a finite group.
Then  there exist SCI graphs of $G$
if and only if $G$ has an automorphism
$\s$ of order a power of
$2$ such that $\s^2$ is fixed-point-free.
\end{lemma}
\proof Let $\Ga=\Cay(G,S)$, where $S\subset G^\#=G\setminus\{1\}$.
Assume first that $\Ga$ is an SCI graph.
Notice that $S^\s=G^\#\setminus S$, we have
$S\cap S^\s=\emptyset$, and hence
the automorphism $\s$ is fixed-point-free, namely,
$\s$ fixes no non-identity elements of $G$.
Moreover, since $S=S^{-1}$, and $\s$ cannot
interchange any pair of
vertices, we further obtain that
$\s^2$ is fixed-point-free too,
and as $\s^2$ fixes both $S$ and $G^\#\setminus S$, we may
assume that $\s$ is a $2$-element, that is,
the order $o(\s)=2^e$ for some $e$.

On the other hand, suppose that $G$ has
an automorphism $\s$ of order $2^e$
such that $\s^2$ is fixed-point-free.

Let $\Delta$ be an orbit of $\l\s^2\r$ acting on $G^\#$. Let $\Delta^{-1}=\{h^{-1}\div h\in\Delta\}$.
Then, for any $g\in\Delta$, we have $\Delta=g^{\l\s^2\r}$, and $\Delta^{-1}=(g^{-1})^{\l\s^2\r}$,
namely, $\Delta^{-1}$ is an orbit of $\l\s^2\r$ on $G^\#$.
We claim that $\Delta^\s\cap\Delta^{-1}=\emptyset$.
Assume otherwise. Then $g^{\s^{2l+1}}=(g^{\s^{2l}})^\s=g^{-1}$
for some $g\in\Delta$, and hence
$g^{\s^{2(2l+1)}}=g$. Since $\s$ is of order $2^e$, we have $g^{\s^2}=g$,
which contradicts the fact that $\s^2$ is fixed-point-free.
Thus $\Delta^{-1}\cap\Delta^\s=\emptyset$, and $\l\s\r$ acts
on the set $\{\{g,g^{-1}\}\div g\in G^\#\}$ with no fixed element.

Let $\Delta_1,\Delta_2,\ldots,\Delta_{2k}$ be the orbits of $\l\s^2\r$ acting on $\{\{g,g^{-1}\}\div g\in G^\#\}$
such that \[\Delta^{\s}_{2i-1}=\Delta_{2i}\,\,\mbox{for}\,\,1\leqslant i\leqslant k.\]
Then $\Delta_{2i}^\s=\Delta_{2i-1}$. Let
\[S=\Delta_1\cup\Delta_3\cup\cdots\cup\Delta_{2k-1}.\]
Since $\Delta_j^{-1}=\Delta_j$, we have $S^{-1}=S$. Moreover,
\[G^\#\setminus S=\Delta_2\cup\Delta_4\cup\cdots\cup\Delta_{2k}
\,\,\mbox{and}\,\, S^\s=G^\#\setminus S.\]
It follows that the Cayley graph $\Ga{:}=\Cay(G,S)\cong\Cay(G,S^\s)=\Cay(G,G^\#\setminus S)=\ov\Ga$.
Therefore, $\Cay(G,S)$ is self-complementary and the complementing isomorphism is produced
by the automorphism $\s$ of $G$.
\qed

For the sake of stating our main results,
we derive an elementary number theoretic result.
Let $n,\lambda$ be coprime positive integers.
The order of $\lambda$ modulo $n$ is the least
positive integer $m$ such that
$\lambda^m\equiv1\,(\mod n)$, denoted by $\ord_n(\lambda)$.
As usual, the order of $\lambda$ modulo
$n$ is a divisor of $\varphi(n)$.
If $\ord_n(\lambda)=\varphi(n)$,
then $\lambda$ is called a primitive root modulo $n$.

\begin{lemma}\label{prime}
Let $p,\lambda$ be coprime positive integers,
where $p$ is an odd prime.
Assume $\ord_{p^n}(\lambda)=p^{n-1}(p-1)$.
Then $\ord_{p^m}(\lambda)=p^{m-1}(p-1)$
where $1\leqslant m<n$.
\end{lemma}
\proof
By Euler's~Theorem, $\lambda^{p^{m-1}(p-1)}\equiv1\, (\mod p^m)$.
Assume $\ord_{p^m}(\lambda)=\mu$, where $\mu$ is a proper
divisor of $p^{m-1}(p-1)$.
%Then there exists some  proper divisor $\mu$ of
%such that $\lambda^\mu\equiv1\, (\mod p^m)$.
Calculation shows that
$\lambda^{\mu p^{n-m}}\equiv1\, (\mod p^n)$,
which contradicts the hypothesis.
Thus the statement follows.
\qed

\begin{lemma}\label{G_3}
Let  $G=G_1(p)$, $G_5(p)$ or $G_7(p)$ be
the group defined in
Lemma~$\ref{Huppert}$. If
$p\equiv1\,(\mod 8)$, then $G$ has
two fixed-point-free automorphisms
$\s$ and $\s^2$ of $2$-power orders.
\end{lemma}
\proof Assume first that $G=G_1(p)$.
By Lemma~\ref{Huppert}, we have
\[G_1(p)=\l a,b\div a^{p^2}=b^p=c^p=1,[a,b]=c,[c,a]=[c,b]=1\r.\]

Now pick a positive integer $\lambda_1$ such that $\ord_{p^2}(\lambda_1)=p(p-1)$.
By Lemma~\ref{prime}, we have $\ord_p(\lambda_1)=p-1$.
Let $\s$ be such that
\[a^\s=a^{\lambda_1^p},\,\,\,b^\s=b^{\lambda_1}
\,\,\,\mbox{and}\,\,\,\, c^\s=c^{\lambda_1^2}.\]
It is simple to show that $\s$ is
an automorphism of $G$ of order  $p-1$.
Assume that $p\equiv1\,(\mod 8)$.  Write $p-1=2^em$ with $m$ an odd number and $e\geqslant3$.
Then \[\mbox{$a^{\s^{m}}=a^{\lambda_1^{mp}}$, $b^{\s^m}=b^{\lambda_1^m}$
and $c^{\s^m}=c^{\lambda_1^{2m}}$.}\]
%We claim that  $\s^m$ and $\s^{2m}$
%are two fixed-point-free automorphisms of $G$.
Suppose, if possible, that there exists some
$1\not=x\in G$ such that $x^{\s^m}=x$.
By definition of $G_1(p)$, we have $x=a^{i_1}b^{i_2}c^{i_3}$, where $0\leqslant i_1\leqslant p^2-1$, and
$0\leqslant i_2,i_3\leqslant p-1$.
If $i_1=0$ and $i_2=0$, then $x=c^{i_3}$ where $i_3\not=0$. Thus
\[(c^{i_3})^{\lambda_1^{2m}}=x^{\s^m}=x=c^{i_3}.\]
It follows that $\lambda_1^{2m}\equiv1\,(\mod p)$,
which is a contradiction.
Thus, either $i_1\not=0$ or $i_2\not=0$.
Observe that $G'=\l c\r$.
Let $\ov G=G/G'$.
For any $z\in G$, we denote by $\ov z$ the image of $z$ in $\ov G$.
%Denote by $\ov a$ and $\ov b$ the
%images of $a$ and $b$ in $\ov G$, respectively.
Write $\ov G=\l \ov a,\ov b\r$.
%Let $\ov x$ be the image of $x$ in $\ov G$.
Then $\ov x=\ov a^{i_1}\ov b^{i_2}\not=1$.
Since $G'$ is a characteristic subgroup of $G$,
$\s^m$ induces an
automorphism $\t$ of $\ov G$, namely,
\[(\ov a^i\ov b^j)^{\t}=\ov{a^ib^j}^\t
=\ov{(a^ib^j)^{\s^m}}
=\ov{(a^i)^{\lambda_1^{mp}}}~\ov{(b^j)^{\lambda_1^m}}
=(\ov a^i)^{\lambda_1^{mp}}(\ov b^j)^{\lambda_1^m},\] where
$i,j$ are integers. Then we have
\[(\ov a^{i_1})^{\lambda_1^{mp}}(\ov b^{i_2})^{\lambda_1^m}
=\ov x^{\t}=\ov {x^{\s^m}}=\ov x=\ov a^{i_1}\ov b^{i_2}.\]
This implies that
$\lambda_1^{mp}\equiv1\,(\mod p^2)$, again a contradiction.
Thus $\s^m$ is a fixed-point-free automorphism
of order $2^e$. Similarly,
$\s^{2m}$ is also fixed-point-free and of order $2^{e-1}$.

Assume now that $G=G_5(p)$. By Lemma~\ref{Huppert}, we have
\[G_5(p)=\l a,b\div a^p=b^p=1,[a,b]=c,[c,b]=d,
[a,c]=[a,d]=[b,d]=1\r.\]

Let $\ord_p(\lambda_2)=p-1$.  Let $\s$ be such that
\[\mbox{$a^{\s}=a^{\lambda_2}$, $b^{\s}=b^{\lambda_2}$, $c^{\s}=c^{\lambda_2^2}d^{\frac{\lambda_2^2(\lambda_2-1)}{2}}$
and $d^{\s}=d^{\lambda_2^3}$}.\]
It is easy to verify  that $\s$ is an
automorphism of $G$ of  order $p-1$.
Assume $p\equiv1\,(\mod 8)$. Write
$p-1=2^em$ with $m$ an odd number and $e\geqslant3$.
By the definition of $\s$, we have
\[\mbox{$a^{\s^m}=a^{\lambda_2^m}$, $b^{\s^m}=b^{\lambda_2^m}$, $c^{\s^m}=c^{\lambda_2^{2m}}d^{\ell}$
and $d^{\s^m}=d^{\lambda_2^{3m}}$},\]
where $\ell$ is an integer.
Arguing similarly as above, we can obtain that
$\s^{m}$ and $\s^{2m}$ are fixed-point-free automorphisms
of order $2^e$ and $2^{e-1}$, respectively.

Assume finally that $G=G_7(p)$.
Let $H=\l a,b\div a^p=b^p=1,[a,b]=c,c^a=c^b=c\r$.
By Lemma~\ref{Huppert}, we have that
$G=H\times\l d\r\cong p_{+}^{1+2}\times\ZZ_p$.

Let $\ord_p(\lambda_3)=p-1$.
Let $\s$ be such that
\[a^\s=a^{\lambda_3},\,\,\, b^\s=b^{\lambda_3},\,\,\, c^\s=c^{\lambda_3^2}\,\,\,\mbox{and}\,\,\,\, d^\s=d^{\lambda_3}.\]
It is straightforward to check that $\s$ is an
automorphism of $G$ of order $p-1$.
Assume that $p\equiv1\,(\mod 8)$.  Let $p-1=2^em$,
where $m$ is an odd number and $e\geqslant3$.
Then \[a^{\s^m}=a^{\lambda_3^m},\,\,\,b^{\s^m}=b^{\lambda_3^m},\,\,\, c^{\s^m}=c^{\lambda_3^{2m}}\,\,\,\mbox{and}\,\,\,\, d^{\s^m}= d^{\lambda_3^m}.\]
Arguing as for the group $G_1(p)$, we
obtain that $\s^m$ and
$\s^{2m}$ are fixed-point-free automorphisms
of order $2^e$ and $2^{e-1}$, respectively.
This completes the proof of Lemma~\ref{G_3}.
\qed

\begin{lemma}\label{G_1}
Let $G=G_2(p)$ be the group defined
in Lemma~$\ref{Huppert}$.
If $p\equiv1\,(\mod 4)$, then $G$ has
two fixed-point-free automorphisms $\s$
and $\s^2$ of $2$-power orders.
\end{lemma}
\proof By Lemma~\ref{Huppert}, we have
\[G_2(p)=\l a,b,c\div a^{p^2}=b^p=c^p=1,[b,c]=a^p,[a,b]=[a,c]=1\r.\]

Now take a positive integer $\lambda$ such that $\ord_{p^2}(\lambda)=p(p-1)$.
By Lemma~\ref{prime}, we have
$\ord_p(\lambda)=p-1$. Let $\s$ be such that
\[\mbox{$a^\s=a^{-\lambda^p}$, $b^\s=c^\lambda$ and $c^\s=b$.}\]
It is easy to show that $\s$ is an
automorphism of $G$ of order $2(p-1)$.
Assume $p\equiv1\,(\mod 4)$. Write $p-1=2^em$
with $m$ an odd number and $e\geqslant2$.
Then \[\mbox{$a^{\s^{m}}=a^{-\lambda^{pm}}$, $b^{\s^m}=c^{\lambda^{\frac{m+1}{2}}}$ and $c^{\s^m}=b^{\lambda^{\frac{m-1}{2}}}$.}\]
Arguing similarly as in Lemma~\ref{G_3},
$\s^m$ and $\s^{2m}$ are fixed-point-free
automorphisms of order $2^{e+1}$ and $2^e$,
respectively.
\qed

Combining Lemma~\ref{fpf-cons-scvt}
with Lemmas~\ref{G_3}-\ref{G_1},
we obtain an important conclusion
in the next proposition.

\begin{proposition}\label{5}
Let $G$ be a $p$-group of order $p^4$, where $p$
is an odd prime. Then one of the following holds:
\begin{itemize}
\item[\rm(i)]
if $p\equiv1\,(\mod 4)$,
then there exist SCI graphs of $G$
when $G=G_2(p)$;

\item[\rm(ii)]
if $p\equiv1\,(\mod 8)$, then
there exist SCI graphs of $G$
when $G=G_1(p)$, $G_5(p)$ or $G_7(p)$.

\end{itemize}
\end{proposition}

\section{Non-SCI graphs}
In this section, we construct self-complementary Cayley graphs
of the groups $G_3(p)$, $G_4(p)$ and $G_6(p)$.
For such groups, we have the following lemma.

\begin{lemma}\label{free}
Let $G=G_3(p)$, $G_4(p)$ or
$G_6(p)$ be the group defined in
Lemma~$\ref{Huppert}$.
Then the square of each automorphism of $G$
is not fixed-point-free.
\end{lemma}
\proof By Lemma~\ref{Huppert}, we have
\[\begin{array}{l}
G_3(p)=\l a,b\div a^{p^2}=b^p=c^p=1,
[a,b]=c,[c,a]=a^p,[c,b]=1\r,\\
G_4(p)=\l a,b\div a^{p^2}=b^p=c^p=1,
[a,b]=c,[c,a]=1,[c,b]=a^{\nu p}\r.\\
\end{array}\]
Let $G=G_3(p)$ or $G_4(p)$.
In either case, $\Phi(G)=\l a^p,c\r$ and $\Z(G)=\l a^p\r$.
For any $\s\in\Aut(G)$, if $p=3$, then
$\s^2$ centralises $\Z(G)$, and hence
$\s^2$ is not fixed-point-free.
Thus we may assume $p>3$.
By Lemma~\ref{Brisley}, $G$ is $p$-abelian.

Assume first that $G=G_3(p)$. By the previous paragraph,
we may assume
\[\mbox{$a^\s=a^{k_1}b^{k_2}c^{k_3}$,
$b^\s=a^{pl_1}b^{l_2}c^{l_3}$ and $c^\s=c^ka^{p l}$},\]
where $1\leqslant k_1\leqslant p^2-1$, $(k_1, p)=1$, and
$0\leqslant k_i,l_j,k,l\leqslant p-1$ for $i=2$
or $3$, and $j=1$, $2$ or $3$.
In particular, $(a^p)^\s=(a^{k_1}b^{k_2}c^{k_3})^p=a^{pk_1}$
since $G$ is $p$-abelian.

By $[c^\s,a^\s]=(a^p)^\s$, we calculate that $[c^k,a^{k_1}]=a^{pk_1}$, and so $a^{pkk_1}=a^{pk_1}$.
Thus $pkk_1\equiv pk_1\,(\mod p^2)$. Since $(k_1,p)=1$,
we obtain $k=1$.
Let $r=c^{ t_1}a^{pt_2}$ where $1\leqslant t_1,t_2\leqslant p-1$.
Then $r^\s=c^{ t_1}a^{p(k_1t_2+lt_1)}$.
If $k_1=1$, then $(a^p)^\s=a^p$. Otherwise,
let $t_2=\frac{l}{1-k_1}t_1$, and
then $r^\s=r$.
It follows that $G$ has no fixed-point-free automorphism.

Assume next that $G=G_4(p)$.
For any $\s\in\Aut(G)$, we may assume
\[\mbox{$a^{\s}=a^{\ov k_1}c^{\ov k_2}$,
$b^{\s}=a^{p\ov l_1}b^{\ov l_2}c^{\ov l_3}$
and $c^{\s}=a^{p\ov l}c^{\ov k}$},\]
where $1\leqslant\ov k_1\leqslant p^2-1$, $(\ov k_1, p)=1$,
and  $0\leqslant \ov k_i,\ov l_j,\ov k,\ov l\leqslant p-1$,
$(\ov k,p)=1$ for $i=2$ or $3$ and $j=1,2$ or $3$.
By $[c^\s,b^\s]=(a^{vp})^\s$, we compute that
$a^{vp\ov k \ov l_2}=a^{vp\ov k_1}$, and thus
$\ov k_1\equiv\ov k~\ov l_2\,(\mod p)$.
By $[a^\s,b^\s]=c^\s$, we obtain
$c^{\ov k_1\ov l_2}=c^{\ov k}$,
and so $\ov k\equiv\ov k_1 \ov l_2\,(\mod p)$.
Since $(\ov k_1,p)=1$, we conclude that
$\ov l_2\equiv \pm1\,(\mod p)$.

Let $\ov G=G/\Phi(G)$.
For any $x\in G$, we denote by $\ov x$
the image of $x$ in $\ov G$.
Since $G'$ is a characteristic subgroup of $G$,
$\s$ induces an automorphism $\ov\s$ of $\ov G$,
that is,
\[(\ov a^i\ov b^j)^{\ov\s}=
\ov{a^ib^j}^{\ov\s}=\ov{(a^ib^j)^\s}=
\ov{a^{i\ov k_1}}~\ov{b^{j\ov l_2}}
=\ov a^{i\ov k_1}\ov b^{j\ov l_2},\]
where $i,j$ are integers.
This implies that
$\ov b^{\ov\s}=\ov b^{\ov l_2}$, and
so $\ov b^{\ov\s^2}=\ov b$.
In other words, $\ov\s^2$ is not fixed-point-free.
By \cite[p.335, Lemma~1.3]{Goren},
$\s^2$ is not a
fixed-point-free automorphism of $G$.
Since $\s$ is arbitrary, the statement holds.

Assume finally that $G=G_6(p)$.
Arguing similarly as above, $G$ has
no fixed-point-free automorphism.
This completes the proof of Lemma~\ref{free}.
\qed

We remark that when $G=G_3(p)$ or $G_6(p)$, $G$
has no fixed-point-free automorphisms, and when
$G=G_4(p)$, the square of each automorphism of $G$
is not fixed-point-free.
If there exist self-complementary Cayley graphs of $G$, then
the complementing isomorphism can not be produced
by special automorphisms of the group $G$,
see Lemma~\ref{fpf-cons-scvt}.

\vskip0.1in
In order to state the following construction,
we need the next lemma.

\begin{lemma}\label{p_{+}}
Let $G=p_{+}^{1+2}\cong\ZZ_p^2{:}\ZZ_p$,
where $p$ is an odd prime.
If $p\equiv1\,(\mod 8)$, then $G$ has two
fixed-point-free automorphisms $\s$ and
$\s^2$ of $2$-power orders.
\end{lemma}
\proof Now we may write  $G$ as follows:
\[G=\l a, b, c\div  a^p=
b^p= c^p=1, [a, b]=c,[a,c]=[b,c]=1\r.\]

Assume that $p-1=2^em$, where $m$ is an odd
number, and $e\geqslant3$.
Let $\lambda$ be a positive integer
such that $\ord_p(\lambda)=2^e$.
Let $\s$ be such that
\[\mbox{$a^\s=a^\lambda$, $b^\s=b^\lambda$ and $c^\s=c^{\lambda^2}$}.\]
It is clear that $\s$ and $\s^2$ are two
fixed-point-free automorphisms of  $2$-power orders.
\qed

\vskip0.1in
Let $p\equiv1\, (\mod 8)$ be a prime.
Write $p-1=2^em$ with $e\geqslant3$, and $m$ an odd number.
Let \[G=G_3(p)=\l a,b\div a^{p^2}=b^p=c^p=1,[a,b]=c,[c,a]=a^p,[c,b]=1\r.\]
Clearly, $\Z(G)=\l a^p\r\cong\ZZ_p$.
Set $H=\l a^p,b,c\r\cong\ZZ_p^3$.

Pick a positive integer $\lambda$
such that $\ord_p(\lambda)=2^e$.
Then we choose $\s\in\Aut(H)$ such that
\[\mbox{$(a^p)^{\s}=(a^p)^\lambda$,\,
$b^{\s}=b^{\lambda}$\, and\, $c^{\s}=c^{\lambda^2}$}.\]
Obviously, $\s$ is a fixed-point-free
automorphism of order $2^e$.
So is $\s^2$ of order  $2^{e-1}$
as $e\geqslant3$.
By Lemma~\ref{fpf-cons-scvt}, there exists
$S_1\subset H$ such that $S_1$ is an
SC-subset with respect to $\s$.
Then $S_1^{\s}=H^\#\setminus S_1$,
and so for any elements $x=a^{pi_1}b^{j_1}c^{k_1}$ and $y=a^{pi_2}b^{j_2}c^{k_2}$,
\begin{align*}
& a^{p(i_2-i_1)}b^{j_2-j_1}c^{k_2-k_1}=yx^{-1}\in S_1 \\
 \Leftrightarrow & a^{\lambda p(i_2-i_1)}b^{\lambda(j_2-j_1)}c^{\lambda^2(k_2-k_1)}
 =y^\s(x^\s)^{-1}\not\in S_1.
\end{align*}

Let $\t\in\Aut(\l a\r)$ be such that $a^{\t}=a^\lambda$, where $\lambda$ is as above.
Let $\ov G=G/\Z(G)=\l\ov a,\ov b,\ov c\r=\ZZ_p^2{:}\ZZ_p$.
By Lemma~\ref{p_{+}}, the pair $(\s,\t)$ induces a fixed-point-free automorphism $\ov\rho$
of $\ov G$. So does $\ov\rho^2$ for $e\geqslant3$.

Again by Lemma~\ref{fpf-cons-scvt}, we may let $\ov S_2\subset\ov G^\#$ be an SC-subset with respect to $\ov\rho$.
Then $\ov S_2^{\ov\rho}=\ov G^\#\setminus\ov S_2$, and Cayley graph
\[\Sigma=\Cay(\ov G,\ov S_2)\]
is self-complementary with complementing isomorphism $\ov\rho$.

Let $I=\{(i,j,k)\div \ov a^i\ov b^j\ov c^k\in\ov S_2,0\leqslant i,j,k\leqslant p-1\}$.
Set
\[\begin{array}{rcl}
S_2&=&\cup_{(i,j,k)\in I}a^ib^jc^k\l a^p\r,\\
\Ga_2&=&\Cay(G,S_2).
\end{array}\]

Let $a^p=d$. We observe that each element
of $G$ can be written as
\[\mbox{$a^ib^jc^kd^l$ where
$0\leqslant i,j,k,l\leqslant p-1$.}\]

By the definition, we have the conclusion in the next lemma.

\begin{lemma}\label{Lex}
The Cayley graph $\Ga_2=\Sigma[\ov{\bf K_p}]$,
and for any elements $x=a^{i_1}b^{j_1}c^{k_1}d^{l_1}$
and $y=a^{i_2}b^{j_2}c^{k_2}d^{l_2}$
with $(i_1,j_1,k_1)\not=(i_2,j_2,k_2)$,
we have
\[yx^{-1}\in S_2\Leftrightarrow
\ov{y}~\ov{x}^{-1}\in\ov S_2
\Leftrightarrow \ov{y}^{\ov\rho}
(\ov{x}^{\ov\rho})^{-1}\not\in\ov S_2.\]
\end{lemma}

With this preparation, we are ready to present
our construction of self-complementary
Cayley graphs of the group $G_3(p)$.

\begin{construction}\label{cons}
{\rm
With the notation above, let
\[\begin{array}{rcl}
S&=&S_1\cup(S_2\setminus H)~~ \mbox{and} \\
\Ga&=&\Cay(G,S).
\end{array}\]
Define a permutation $\rho$ of the set $G$ as follows:
\[\rho: \,\,a^ib^jc^kd^l\mapsto a^{\lambda i}b^{\lambda j}c^{\lambda^2 k}d^{\lambda l'},\]
where $l'=l+\frac{ij[(\lambda^2-1)i+\lambda-1]}{2}
+(\lambda^2-1)ik$\, and\,
$0\leqslant i,j,k,l\leqslant p-1$.
}
\end{construction}
We remark that the map $\rho$ only
fixes the identity of $G$,
but by Lemma~\ref{free}, $\rho$
is not an automorphism of $G$.
The next lemma shows that $\rho$ maps
$\Ga$ to its complement $\ov\Ga$.

\begin{lemma}\label{3}
The Cayley graph $\Ga$ defined in
Construction~$\ref{cons}$ is self-complementary,
and $\rho$ is a complementing isomorphism.
\end{lemma}
\proof Take two vertices $x=a^{i_1}b^{j_1}c^{k_1}d^{l_1}$
and $y=a^{i_2}b^{j_2}c^{k_2}d^{l_2}$, where $0\leqslant i_t,j_t,l_t,k_t\leqslant p-1$ with $t=1,2$.
By the definition of $G$, we have

\[yx^{-1} = a^{i_2}b^{j_2-j_1}c^{k_2-k_1}a^{-i_1}d^{l_2-l_1}.\]

By the definition of $\rho$, we obtain
\[\begin{array}{rcl}
(x^\rho)^{-1}&=&c^{-\lambda^2 k_1}b^{-\lambda j_1}a^{-\lambda i_1}d^{-\lambda(l_1+\frac{i_1j_1[(\lambda^2-1)i_1+\lambda-1]}{2}
+(\lambda^2-1)i_1k_1)},\\
y^\rho&=&a^{\lambda i_2}b^{\lambda j_2}c^{\lambda^2 k_2}d^{\lambda(l_2+\frac{i_2j_2[(\lambda^2-1)i_2+\lambda-1]}{2}
+(\lambda^2-1)i_2k_2)}.
\end{array}\]

Assume first that $i_1=i_2$. Then, by the
previous three equations,
\[\begin{array}{rcl}
yx^{-1}&=&b^{j_2-j_1}c^{i_2(j_2-j_1)+k_2-k_1}
d^{l_2-l_1-\frac{i_2(j_2-j_1)
(i_2+1)}{2}-i_2(k_2-k_1)},\\

y^\rho(x^\rho)^{-1}&=&b^{\lambda(j_2-j_1)}
c^{\lambda^2[i_2(j_2-j_1)+k_2-k_1]}
d^{\lambda[l_2-l_1-\frac{i_2(j_2-j_1)
(i_2+1)}{2}-i_2(k_2-k_1)]}.
\end{array}\]

By the above two equations, we obtain that both $yx^{-1}$ and $y^\rho(x^\rho)^{-1}$ belong to $H$.
Recall that $S_1\subset H$ is an SC-subset with respect to $\s$.
By the definition of $\rho$,  $S_1$ is also an
SC-subset with respect to $\rho$.
It follows that
$yx^{-1}$ belongs to $S_1$ if and only
if $y^\rho(x^\rho)^{-1}$ does not belong to $S_1$.

Assume now that $i_1\not=i_2$.  It is easy to show that
neither $yx^{-1}$ nor $y^\rho(x^\rho)^{-1}$ belongs to $H$.
Calculation shows that
\[\begin{array}{rcl}
\ov{y}~\ov{x}^{-1}&=&\ov a^{i_2-i_1}\ov b^{j_2-j_1}\ov c^{i_1(j_2-j_1)+k_2-k_1},\,\,\,\mbox{and}\\
\ov{y}^\rho(\ov{x}^\rho)^{-1}&=&\ov a^{\lambda(i_2-i_1)}
\ov b^{\lambda(j_2-j_1)}\ov c^{\lambda^2[i_1(j_2-j_1)+k_2-k_1]}.
\end{array}\]
Lemma~\ref{Lex} along with the above two equations imply that
\[yx^{-1}\in S_2\Leftrightarrow \ov y~\ov x^{-1}\in\ov S_2\Leftrightarrow
\ov y^\rho(x^\rho)^{-1}\notin\ov S_2\Leftrightarrow y^\rho(x^\rho)^{-1}\notin S_2.\]
It follows that $x,y$ are adjacent in $\Ga$ if and only if $x^{\rho},y^{\rho}$
are not adjacent in $\Ga$, and so
$\rho$ is an isomorphism between $\Ga$ and $\ov\Ga$.
In particular, $\Ga\cong\ov\Ga$.
\qed

Notice that, with the same method,
a similar construction will also
work for the groups $G_4(p)$ and $G_6(p)$.


\section{Proof of Theorem~\ref{maint}}

Combining Proposition~\ref{5} and Lemma~\ref{3}
along with Construction~\ref{cons}, we obtain
an important conclusion in the next proposition.

\begin{proposition}\label{6}
Let $G$ be a $p$-group of order $p^4$,
where $p$ is an odd prime.
Then one of the following holds:
\begin{itemize}
\item[\rm(i)]
if $p\equiv1\,(\mod 4)$,
then there exist self-complementary Cayley graphs of $G$
when $G=G_2(p)$;

\item[\rm(ii)]
if $p\equiv1\,(\mod 8)$, then
there exist self-complementary Cayley graphs of $G$
when $G=G_i(p)$ for $i=1$ or $3\leqslant i\leqslant7$.

\end{itemize}
\end{proposition}

We remark that the groups $G_1(p)$, $G_2(p)$,
$G_5(p)$ and $G_7(p)$
have fixed-point-free automorphisms
by Lemmas~\ref{G_3}-\ref{G_1}.
Therefore, the self-complementary
Cayley graphs appearing in Proposition~\ref{6}
can be produced by fixed-point-free
automorphisms of the groups.

\vskip0.1in
The assertion of Theorem~\ref{maint}
follows from Lemma~\ref{Huppert} and Proposition~\ref{6}.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \subsection*{Acknowledgements}
% Thanks to Professor Querty for suggesting the proof of
% Lemma~\ref{lem:Technical}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{99}
\bibitem{Alspach}
B. Alspach, J. Morris, V. Vilfred,
Self-complementary circulant graphs,
{\it Ars Combin}. {\bf53} (1999) 187-191.

\bibitem{Beezer}
R. A. Beezer, Sylow subgraphs in
self-complementary vertex transitive graphs,
{\it Expo. Math}. {\bf24(2)} (2006) 185-194.

\bibitem{Brisley}
W. Brisley, I. D. Macdonald,
Two classes of metabelian $p$-groups,
{\it Math. Z}. {\bf 112} (1969) 5-12.

\bibitem{Ramsey-Th}
V. Chv\'{a}tal, P. Erd\H{o}s, Z. Hedrl\'{i}n,
Ramsey's theorem and self-complementary graphs,
{\it Disc. Math}. {\bf3} (1972) 301-304.

\bibitem{Clapham}
C. R. J. Clapham, A class of self-complementary
graphs and lower bounds of some Ramsey numbers,
{\it J. Graph Theory}. {\bf3} (1979) 287-289.

\bibitem{Figueroa}
R. Figueroa, R. E. Giudici, Group generation
of self-complementary graphs,
{\it Combinatorics and graph theory},
Hefei. (1992) 131-140.

\bibitem{FRJ}
D. Fron\v{c}ek, A. Rosa, J. \v{S}ir\'{a}\v{n},
The existence of selfcomplementary circulant graphs,
{\it European J. Combin}. {\bf17} (1996) 625-628.

\bibitem{Goren}
D. Gorenstein,
Finite Groups, 2nd ed, Chelsea,  New York, 1980.

\bibitem{Gulden}
F. Gulden, P. Tomasta, New lower bounds
of some diagonal Ramsey numbers,
{\it J. Graph Theory}. {\bf7} (1983) 149-151.

\bibitem{GLPS}
R. Guralnick, C. H. Li, C. E. Praeger,
J. Saxl, On orbital partitions and exceptionality of
primitive permutation groups,
{\it Trans. Amer. Math. Soc}. {\bf356} (2004) 4857-4872.

\bibitem{Huppert}
B. Huppert, Eudiche Gruppen I, Springer-Verlag, 1967.

\bibitem{Jajcay}
R. Jajcay, C. H. Li, Constructions of
self-complementary circulants with
no multiplicative isomorphisms,
{\it European J. Combin}. {\bf22} (2001) 1093-1100.

\bibitem{non-Cay-SC}
C. H. Li, C. E. Praeger, Self-complementary
vertex-transitive graphs need not be Cayley graphs,
{\it Bull. London Math. Soc}. {\bf33(6)} (2001) 653-661.

\bibitem{Tod}
C. H. Li, C. E. Praeger, On partitioning
the orbitals of a transitive permutation group,
{\it Trans. Amer. Math. Soc}. {\bf355} (2003) 637-653.

\bibitem{c-gps}
C. H. Li, C. E. Praeger, Finite permutation
groups with a transitive cyclic subgroup,
{\it J. Algebra}. {\bf349} (2012) 117-127.

\bibitem{Rao-pq}
C. H. Li, G. Rao, Self-complementary
vertex-transitive graphs of order a product of two primes,
{\it Bull. Aust. Math. Soc}. {\bf89} (2014) 322-330.

\bibitem{Rao-meta}
C. H. Li, G. Rao, S. J. Song, On finite
self-complementary metacirculants,
{\it J. Algebraic Combin}. {\bf40} (2014) 1135-1144.

\bibitem{Xujing}
C. H. Li, S. H. Sun, J. Xu, Self-complementary
circulants of prime-power order,
{\it Siam J. Discrete Math}. {\bf28} (2014) 8-17.


\bibitem{Liskovets}
V. Liskovets, R. P\"{o}schel, Non-Cayley-isomorphic
self-complementary circulant graphs,
{\it J. Graph Theory}. {\bf34} (2000) 128-141.

\bibitem{Mathon}
R. Mathon, On self-complementary strongly regular graphs,
{\it Disc. Math}. {\bf69} (1988) 263-281.

\bibitem{Muzychuck}
M. Muzychuck, On Sylow subgraphs of vertex-transitive self-complmentary graphs,
{\it Bull. London Math. Soc}. {\bf31(5)} (1999)  531-533.

\bibitem{Rao}
S. B. Rao, On Regular and strongly regular
selfcomplementary graphs,
{\it Disc. Math}. {\bf54} (1985) 73-82.

\bibitem{Robinson}
D. J. Robinson,
A Course in the Theory of Groups,
second ed. Springer, New York, 1996.

\bibitem{Rodl}
V. R\"{o}dl, E. \v{S}i\v{n}ajov\'{a},
Note on Ramsey numbers and self-complementary graphs,
{\it Math. Slovaca}. {\bf45} (1995) 155-159.

\bibitem{Sachs}
H. Sachs, \"{U}ber selbstcomplement\"{a}re graphen,
{\it Publ. Math. Debrecen}. {\bf9} (1962) 270-288.

\bibitem{Zelinka}
B. Zelinka, Self-complementary vertex-transitive
undirected graphs,
{\it Math. Slovaca}. {\bf29} (1979) 91-95.
\end{thebibliography}

\end{document}
