% 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)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 m3$. 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}