% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % 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} % 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} \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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\inv}{\mathop{\rm inv}\nolimits} \def\a{\alpha} \def\b{\beta} \def\g{\gamma} \def\d{\delta} \def\e{\varepsilon} \def\r{\rho} \def\s{\sigma} \def\t{\tau} \def\om{\omega} \def\k{\kappa} \def\th{\theta} \def\ld{\lambda} \def\ph{\varphi} \def\Th{\Theta} \def\Ld{\Lambda} \def\si{\Sigma} %\def\O{\Omega} \def\G{\Gamma} \def\D{\bf D} \def\B{\mathcal B} \def\Om{\Omega} \def\oa{\overline A} \def\og{\overline G} \def\oh{\overline H} \def\ob{\overline B} \def\oc{\overline C} \def\od{\overline D}\def\oq{\overline Q} \def\ok{\overline K} \def\ol{\overline L} \def\om{\overline M} \def\on{\overline N} \def\op{\overline P} \def\os{\overline S} \def\ot{\overline T} \def\ou{\overline U} \def\ov{\overline V} \def\ow{\overline W} \def\ox{\overline X} \def\oy{\overline Y} \def\olg{\overline g} \def\ola{\overline \alpha} \def\olh{\overline h} \def\wtd{\widetilde } \def\o{\overline} \def\oli{\overline i} \def\olj{\overline j} \def\di{\bigm|} \def\lg{\langle} \def\rg{\rangle} \def\nd{\mathrel{\bigm|\kern-.7em/}} \def\edi{\bigm|\bigm|} \def\f{\noindent} \def\maxsgp{<\!\!\!\cdot} \def\PSL{\hbox{\rm PSL}} \def\SL{\hbox{\rm SL}} \def\GL{\hbox{\rm GL}} \def\PGL{\hbox{\rm PGL}} \def\Hom{\hbox{\rm Hom}} \def\End{\hbox{\rm End}} \def\Aut{\hbox{\rm Aut}} \def\Inn{\hbox{\rm Inn}} \def\Syl{\hbox{\rm Syl}} \def\Ker{\hbox{\rm Ker }} \def\soc{\hbox{\rm soc}} \def\Fix{\hbox{\rm Fix}} \def\cay{\hbox{\rm Cay}} \def\Cay{\hbox{\rm Cay}} \def\Cov{\hbox{\rm Cov}} \def\CT{\hbox{\rm CT}} \def\Sab{\hbox{\rm Sab }} \def\mod{\hbox{\rm mod }} \def\Core{\hbox{\rm Core}} \def\Cov{\hbox{\rm Cov}} \def\GP{\hbox{\rm GP}} \def\D{\hbox{\rm Dih}} \def\H{{\mathcal H}} \def\demo{{\bf Proof}\hskip10pt} \def\case{{\bf Case}\hskip5pt} \def\mz{{\mathbb Z}} \def\qed{\hskip10pt $\Box$\vspace{3mm}} \def\qqed{\hskip10pt $\Box$\vspace{3mm}} \renewcommand{\thefootnote}{\fnsymbol{footnote}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Cubic non-Cayley vertex-transitive bi-Cayley graphs over a regular $p$-group} % 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{Jin-Xin Zhou, Yan-Quan Feng\\ \small Department of Mathematics\\[-0.8ex] \small Beijing Jiaotong University\\[-0.8ex] \small Beijing 100044, P.R. China\\ \small\tt jxzhou@bjtu.edu.cn, yqfeng@bjtu.edu.cn\\ } % \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 29, 2013}{July 27, 2016}\\ \small Mathematics Subject Classifications: 05C25, 20B25} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} A bi-Cayley graph is a graph which admits a semiregular group of automorphisms with two orbits of equal size. In this paper, we give a characterization of cubic non-Cayley vertex-transitive bi-Cayley graphs over a regular $p$-group, where $p>5$ is a prime. As an application, a classification of cubic non-Cayley vertex-transitive graphs of order $2p^3$ is given for each prime $p$. % keywords are optional \bigskip\noindent \textbf{Keywords:} bi-Cayley graph; vertex-transitive; automorphism group; Cayley graph \end{abstract} \section{Introduction} All groups considered in this paper are finite, and all graphs are finite, connected, simple and undirected. For the group-theoretic and graph-theoretic terminology not defined here we refer the reader to \cite{BMBook,WI}. A graph is said to be a {\em bi-Cayley graph} over a group $H$ if it admits $H$ as a semiregular automorphism group with two orbits of equal size. (Some authors have used the term semi-Cayley instead~\cite{Gao2010,Gao2011,dJ,LM}. In this paper, we follow~\cite{kovacs} to use the term bi-Cayley.) Note that every bi-Cayley graph admits the following concrete realization. Let $R,L$ and $S$ be subsets of a group $H$ such that $R=R^{-1}$, $L=L^{-1}$ and $R\cup L$ does not contain the identity element of $H$. Define the graph BiCay$(H, R, L, S)$ to have vertex set the union of the {\em right part} $H_0=\{h_0\ |\ h\in H\}$ and the {\em left part} $H_1=\{h_1\ |\ h\in H\}$, and edge set the union of the {\em right edges} $\{\{h_0, g_0\}\ |\ gh^{-1}\in R\}$, the {\em left edges} $\{\{h_1, g_1\}\ |\ gh^{-1}\in L\}$ and the {\em spokes} $\{\{h_0, g_1\}\ |\ gh^{-1}\in S\}$ (Note that some authors label the vertices of a bi-Cayley graph for a group $H$ with ordered pairs $(h, i)$ for $h\in H$ and $i\in\{0, 1\}$, while we are using $h_i$ to denote $(h, i)$). For the case when $|S|=1$, the bi-Cayley graph BiCay$(H, R, L, S)$ is also called {\em one-matching bi-Cayley graph} (see~\cite{kovacs}). Also, if $|R|=|L|=s$, then ${\rm BiCay}(H,R,L,S)$, is said to be an {\em $s$-type bi-Cayley graph}, and if $H$ is abelian, then ${\rm BiCay}(H,R,L,S)$ is simply called an {\em abelian bi-Cayley graph}. In the study of bi-Cayley graphs, a natural problem is to characterize or classify bi-Cayley graphs over a given group with certain valency and specific symmetric property. Some partial answers for this problem have been obtained. For example, in~\cite{Pisanski} Pisanski classified cubic bi-Cayley graphs over cyclic groups, and in~\cite{kovacs}, Kov\'acs et al. gave a description of arc-transitive one-matching bi-Cayley graphs over abelian groups, from which one can obtain the classification of cubic arc-transitive one-matching bi-Cayley graphs over abelian groups. In~\cite{ZF}, the automorphisms of the bi-Cayley graphs were investigated. In particular, some sufficient conditions for a bi-Cayley graph being vertex-transitive or Cayley were given, and moreover, for a one-matching bi-Cayley graph $\G$ over a group $H$, the normalizer of the group $H$ in $\Aut(\G)$ was determined. By using this, a classification of cubic vertex-transitive bi-Cayley graphs over abelian groups was given. The facts listed above provide the motivation for us to consider the following problem. \begin{problem}\label{prob} Characterize cubic non-Cayley vertex-transitive bi-Cayley graphs over a $p$-group for an odd prime $p$. \end{problem} Another motivation for us to consider this problem is: it is also related to the study of non-Cayley vertex-transitive graphs which is very active in 1980's. Let $p>3$ be a prime. It is easy to prove that every connected cubic non-Cayley vertex-transitive graph of order $2p^n (n\geq 1)$ is a bi-Cayley graph over a $p$-group (see Lemma~\ref{isbicayley}). So the above problem is equivalent to the problem of characterizing cubic non-Cayley vertex-transitive graphs of order $2p^n$. By \cite{FK3}, every cubic symmetric graph of order $2p^n$ ($p>5$ is a prime) is a Cayley graph (see Proposition~\ref{2pnsymmetric}). Clearly, this is not true for the case when $p=5$ because the Petersen graph is non-Cayley. In fact, one may construct infinitely many cubic non-Cayley symmetric graphs of order $2\cdot5^n$ by considering the regular coverings of the Petersen graph. It is known that for a prime $p$, every cubic non-Cayley vertex-transitive graph of order $2p$ or $2p^2$ is a generalized Petersen graph~(see \cite{Marusic,Zhouadv}). In~\cite{KMZ}, the authors proved that every cubic non-Cayley vertex-transitive graph of order $2p^n$, where $p>7$ is a prime and $n\leq p$, is a bi-Cayley graph over a $p$-group $P$ generated by two elements $a$ and $b$ of the same order and admitting an automorphism $\a\in\Aut(P)$ of order $4$ such that $a^\a=b$ and $b^\a=a^{-1}$. In this paper, we solve the above problem for the case when $P$ is a regular $p$-group where $p>5$ is a prime. It is proved that a connected cubic vertex-transitive bi-Cayley graph over a regular $p$-group $P$, where $p>5$ is a prime, is non-Cayley if and only if $\G={\rm BiCay}(P,R,L,\{1\})$ is $2$-type, and $\Cay(P,R\cup L)$ is a tetravalent normal arc-transitive Cayley graph with $\Aut(P,R\cup L)\cong\mz_4$. As an application, a classification of cubic non-Cayley vertex-transitive graphs of order $2p^3$ is given for each prime $p$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries} In this section, we shall introduce some notations, terminology and preliminary results. Let $n$ be a positive integer. Denote by $\mz_n$ the cyclic group of order $n$, by $\mz_n^*$ the multiplicative group of $\mz_n$ consisting of numbers coprime to $n$, and by $D_{2n}$ the dihedral group of order $2n$, respectively. %by $S_n$ the symmetric group of degree $n$ For a finite, simple and undirected graph $X$, we use $V(X)$, $E(X)$, $A(X)$ and $\Aut(X)$ to denote its vertex set, edge set, arc set and full automorphism group, respectively. For $u,v\in V(X)$, $u\sim v$ means that $u$ is adjacent to $v$ and denote by $\{u,v\}$ the edge incident to $u$ and $v$ in $X$. For any subset $B$ of $V(X)$, the subgraph of $X$ induced by $B$ will be denoted by $X[B]$. A graph $X$ is said to be {\em vertex-transitive}, and {\em arc-transitive} (or {\em symmetric}) if $\Aut(X)$ acts transitively on $V(X)$ and $A(X)$, respectively. Let $G$ be a permutation group on a set $\Omega$ and $\a\in \Omega$. Denote by $G_\a$ the stabilizer of $\a$ in $G$, that is, the subgroup of $G$ fixing the point $\a$. We say that $G$ is {\em semiregular} on $\Omega$ if $G_\a=1$ for every $\a\in \Omega$ and {\em regular} if $G$ is transitive and semiregular. Given a finite group $G$ and an inverse closed subset $S\subseteq G\setminus\{1\}$, the {\em Cayley graph} $\Cay(G,S)$ on $G$ with respect to $S$ is defined to have vertex set $G$ and edge set $\{\{g,sg\}\mid g\in G,s\in S\}$. A Cayley graph $\Cay(G,S)$ is connected if and only if $S$ generates $G$. Given a $g\in G$, define the permutation $R(g)$ on $G$ by $x\mapsto xg, x\in G$. Then $R(G)=\{R(g)\ |\ g\in G\}$, called the {\em right regular representation} of $G$, is a permutation group isomorphic to $G$. It is well-known that $R(G)\leq\Aut(\Cay(G,S))$. So, $\Cay(G,S)$ is vertex-transitive. In general, a vertex-transitive graph $X$ is isomorphic to a Cayley graph on a group $G$ if and only if its automorphism group has a subgroup isomorphic to $G$, acting regularly on the vertex set of $X$ (see \cite[Lemma~16.3]{B}). A Cayley graph $\Cay(G, S)$ is said to be {\em normal} if $R(G)$ is normal in $\Aut(\Cay(G, S))$ (see~\cite{X1}). %Let $\Cay(G,S)$ be a Cayley graph on a group $G$ with respect to a %subset $S$ of $G$. Set $A=\Aut(\Cay(G,S))$ and $\Aut(G,S)=\{\a\in \Aut(G)\ |\ S^\a=S\}$. \begin{proposition} {\rm\cite[Proposition~1.5]{X1}} \label{stabi} The Cayley graph $\Cay(G,S)$ is normal if and only if $A_1=\Aut(G,S)$, where $A_1$ is the stabilizer of the identity $1$ of $G$ in $A$. \end{proposition} Let $p$ be a prime. A finite $p$-group $P$ is called a {\em regular $p$-group} if for any two elements $x$ and $y$ in $P$, there exist $c_1, c_2, \cdots, c_r$ in the derived group of $\lg x, y\rg$ such that $(xy)^p=x^py^pc_1^pc_2^p\cdots c_r^p$. \begin{proposition}{\rm\cite[Theorem~3.1]{FXregular}}\label{regular-p} Let $p$ be a prime and $G$ a regular $p$-group with $p\neq 2, 5$. Let $X=\Cay(G, S)$ be a connected tetravalent Cayley graph on $G$. Then we have $\Aut(\Cay(G, S))= R(G)\rtimes \Aut(G, S)$. \end{proposition} \begin{proposition}{\rm \cite[Corollary~3.4]{FK3}}\label{2pnsymmetric} Let $p>5$ be a prime. Then every connected cubic symmetric graph of order $2p^n$ is a Cayley graph. \end{proposition} The following proposition lists all of the tetravalent connected arc-transitive Cayley graphs of order $p^3$ for each prime $p$. \begin{proposition}{\rm\cite[Theorem~4.1]{FXp3}}\label{p3} Let $p$ be a prime and let $X=\Cay(G,S)$ be a tetravalent connected arc-transitive Cayley graph of order $p^3$. Then one of the following holds. \begin{enumerate} \item [{\rm (1)}]\ $G=\mz_{p^3}=\lg a\rg$, $S=\{a,a^{-1},a^\ld,a^{-\ld}\}$ $(\ld^2\equiv-1\ (\mod p^3))$. \item [{\rm (2)}]\ $G=\mz_{p^2}\times\mz_p=\lg a\rg\times\lg b\rg$, $S=\{a,a^{-1},a^\ld b,(a^\ld b)^{-1}\}$ $(\ld^2\equiv-1\ (\mod p))$. \item [{\rm (3)}]\ $G=\mz_{p^2}\times\mz_p=\lg a\rg\times\lg b\rg$, $S=\{a,a^{-1},ab,(ab)^{-1}\}$. \item [{\rm (4)}]\ $G=\lg a,b,c\ |\ a^p=b^p=c^p=1, c=[a,b], [a,c]=[b,c]=1\rg$, $S=\{a,a^{-1},b,b^{-1}\}$. \end{enumerate} \end{proposition} To end this section, we give some results regarding the bi-Cayley graphs. For the proof of these results, one may see ~\cite{ZF}. Let $\G=$ BiCay$(H,R,L,S)$ be a connected bi-Cayley graph over a group $H$. The following proposition gives some basic properties of $\G$. \begin{proposition}\label{basicprop} The following hold. \begin{enumerate} \item [{\rm (1)}]\ $H$ is generated by $R\cup L\cup S$. \item [{\rm (2)}]\ If $S\neq\emptyset$, then $S$ can be chosen to contain the identity element of $H$. \item [{\rm (3)}]\ For any automorphism $\a$ of $H$, {\rm BiCay}$(H,R,L,S)\cong${\rm BiCay}$(H,R^\a,L^\a,S^\a)$. \end{enumerate} \end{proposition} Let $R(H)$ denote the right regular representation of $H$. Then $R(H)$ can be regarded as a group of automorphisms of BiCay$(H, R, L, S)$ acting on its vertices by the rule $$h_i^{R(g)}=(hg)_i, \forall i\in\mz_2, h,g\in H.$$ For an automorphism $\a$ of $H$, define two permutations on $V(\G)=H_0\cup H_1$ as follows: \begin{equation}\label{eq-auto} \begin{array}{ll} \d_\a:& h_0\mapsto (h^\a)_1, h_1\mapsto (h^\a)_0, \forall h\in H,\\ \s_\a:& h_0\mapsto (h^\a)_0, h_1\mapsto (h^\a)_1, \forall h\in H. \end{array} \end{equation} Set \begin{equation}\label{eq-autoset} \begin{array}{lll} {\rm I}&=& \{\d_\a\ |\ \a\in\Aut(H)\ s.t.\ R^\a=L, L^\a=R, S^\a=S^{-1}\},\\ {\rm F} &=&\lg \s_\a\ |\ \a\in\Aut(H)\ s.t.\ R^\a=R, L^\a=L, S^\a=S\rg. \end{array} \end{equation} \begin{proposition}\label{automorphism2} Each element in ${\rm I}\cup{\rm F}$ is an automorphism of $\G$. Furthermore, for any $\d_\a\in{\rm I}$, if $\a$ has order $2$, then $\lg R(H),\d_\a\rg=R(H)\rtimes\lg \d_\a\rg$ acts regularly on $V(\G)$. \end{proposition} \begin{proposition}\label{one-matching} Let $\G=${\rm BiCay}$(H,R,L,\{1\})$ be a connected one-matching bi-Cayley graph over the group $H$. Then $\Aut(\G)$ contains a regular subgroup containing $R(H)$ if and only if there exists an automorphism $\a\in\Aut(H)$ of order at most $2$ such that $R^\a=L$. \end{proposition} \section{Characterization} \begin{lemma}\label{isbicayley} Let $p>3$ be a prime. Then every connected cubic non-Cayley vertex-transitive graph of order $2p^n (n\geq 1)$ is a bi-Cayley graph over a $p$-group. \end{lemma} \begin{proof} Let $\G$ be a cubic non-Cayley vertex-transitive graph of order $2p^n$ with $p>3$ a prime. Set $A=\Aut(\G)$. By Proposition~\ref{2pnsymmetric}, either $\G$ is non-symmetric or $\G$ is symmetric and $p=5$. Let $P$ be a Sylow $p$-subgroup of $A$. If $\G$ is non-symmetric, then the vertex-stabilizer $A_v$ of $v\in V(\G)$ is a $2$-group, and so $P$ is semiregular on $V(\G)$. If $\G$ is symmetric and $p=5$, then $A_v$ is a $\{2,3\}$-group, and so $P$ is also semiregular on $V(\G)$. Consequently, $P$ is always semiregular and has two orbits of equal size. This implies that $\G$ must be a bi-Cayley graph over $P$. \end{proof} Now we introduce the concept of quotient graph which will be used in the proof of the following lemma. Let $\G$ be a connected vertex-transitive graph, and let $G\leq \Aut(\G)$ be vertex-transitive on $\G$. For a $G$-invariant partition $\B$ of $V(\G)$, the {\em quotient graph} $\G_\B$ is defined as the graph with vertex set $\B$ such that, for any two vertices $B,C\in \B$, $B$ is adjacent to $C$ if and only if there exist $u\in B$ and $v\in C$ which are adjacent in $\G$. Let $N$ be a normal subgroup of $G$. Then the set $\B$ of orbits of $N$ in $V(\G)$ is a $G$-invariant partition of $V(\G)$. In this case, the symbol $\G_\B$ will be replaced by $\G_N$. \begin{lemma}\label{normal} Let $\G={\rm BiCay}(P,R,L,S)$ be a connected cubic non-Cayley vertex-transitive bi-Cayley graph over a regular $p$-group $P$, where $p>5$ is a prime. Let $A=\Aut(\G)$. Then $R(P)$ is a normal Sylow $p$-subgroup of $A$. \end{lemma} \begin{proof} By Proposition~\ref{2pnsymmetric}, $\G$ must be non-symmetric. It follows that the vertex-stabilizer $A_v$ of any $v\in V(\G)$ in $A$ is a $2$-group. This implies that $A_v/A_v^*\leq\mz_2$, where $A_v^*$ is the kernel of $A_v$ acting on the neighborhood of $v$. Since $\G$ is non-Cayley, one has $A_v>1$. If $A_v/A_v^*=1$, then $A_v(=A_v^*)$ fixes all neighbors of $v$, and by the vertex-transitivity and connectedness of $\G$, we get that $A_v$ fixes all vertices of $\G$, forcing that $A_v=1$, a contradiction. Thus, $A_v/A_v^*\cong\mz_2$, and so there is one and only one neighbor, say $u$, of $v$ such that $A_u=A_v$. By the arbitrariness of $v$, the following set $$\B=\{\{u,v\}\ |\ u,v\in V(\G)\ {\rm such\ that}\ A_u=A_v\}.$$ is a $1$-factor of $\G$. Clearly, for any $g\in A$, $A_{u^g}=A^g_u=A^g_v=A_{v^g}$. It follows that $\B$ is also an $A$-invariant partition of $V(\G)$. Consider the quotient graph $\G_\B$ of $\G$ relative to $\B$, and let $K$ be the kernel of $A$ acting on $V(\G_\B)$. Then $A/K$ is vertex-transitive on $\G_\B$ and so $\G_\B$ has regular valency. Since $\G$ is cubic, $\G_\B$ has valency at most $4$, and since $|\G_\B|=|P|$ is odd, the valency of $\G_\B$ is $2$ or $4$. Since $p$ is odd and $K$ is a $2$-group, $R(P)\cong R(P)K/K$ must be regular on $V(\G_\B)$. Suppose $K\neq 1$. Then, $\B$ is the set of orbits of $K$. Since each orbit of $K$ is just an edge of $\G$, the quotient graph $\G_\B$ must be a cycle of length $p^n$, where $p^n=|P|$, and moreover, since $\G$ has valency $3$, the edges between any two adjacent orbits of $K$ form a perfect matching. It follows that the neighbors of any $v\in V(\G)$ are in three different orbits of $K$. Thus, $K_v$ fixes each neighbor of $v$. By the connectedness of $\G$, we obtain that $K_v=1$ and hence $K\cong\mz_2$. As $R(P)K/K$ is regular on $V(\G_\B)$, $R(P)K=R(P)\times K$ is regular on $V(\G)$, implying that $\G$ is a Cayley graph, a contradiction. Now we know that $K=1$. Then $A$ acts faithfully on $\B$, and so $A\leq\Aut(\G_\B)$. Since $R(P)=R(P)K/K$ acts regularly on $V(\G_\B)$, $\G_\B$ can be viewed as a Cayley graph on $P$. If $\G_\B$ has valency $2$, then $\G_\B$ is a cycle of length $p^n$ and $\Aut(\G_\B)\cong D_{2p^n}$. It follows that $|A|=2p^n=2|P|$, contradicting that $A$ is not regular on $V(\G)$. Thus, $\G_\B$ has valency $4$. Since $P$ is a regular $p$-group with $p\neq 2,5$, by Proposition~\ref{regular-p}, $\G_\B$ is a normal Cayley graph on $P$. It follows that $R(P)\unlhd\Aut(\G_\B)$, and since $A\leq \Aut(\G_\B)$, one has $R(P)\unlhd A$, as required. \end{proof} By Huppert \cite[III, Theorem 10.2]{H}, a $p$-group of order $p^n$ with $n\leq p$ is regular. By Lemma~\ref{isbicayley}, the following corollary is straightforward. \begin{corollary}{\rm \cite[Lemma~4.2]{KMZ}} Let $\G$ be a connected cubic vertex-transitive graph of order $2p^n$, where $p>7$ is a prime and $n\leq p$. Then a Sylow $p$-subgroup of $\Aut(\G)$ is normal. \end{corollary} The following is the main result of this section. \begin{theorem}\label{characterize} Let $\G={\rm BiCay}(P,R,L,S)$ be a connected cubic vertex-transitive bi-Cayley graph over a regular $p$-group $P$, where $p>5$ is a prime. Then $\G$ is non-Cayley if and only if $\G={\rm BiCay}(P,R,L,\{1\})$ is $2$-type, and $\Cay(P,R\cup L)$ is a tetravalent normal arc-transitive Cayley graph with $\Aut(P,R\cup L)\cong\mz_4$. \end{theorem} \begin{proof} We first prove the sufficiency. Since $R=R^{-1}$ and $L=L^{-1}$, we may assume that $R=\{a,a^{-1}\}$ and $L=\{b,b^{-1}\}$. Since $\Aut(P,R\cup L)\cong\mz_4$, we may assume that $\Aut(P,R\cup L)=\lg \a\rg$ such that $a^\a=b, b^\a=a^{-1}$. In particular, $\a$ interchanges $R$ and $L$. By the definition of $\d_\a$ (see Eq~\ref{eq-auto})), $\d_\a$ interchanges the two orbits of $R(P)$. It follows from Proposition~\ref{automorphism2} that $\G$ is vertex-transitive. Suppose that $\G$ is Cayley. Since $\G={\rm BiCay}(P,R,L,\{1\})$ is $2$-type, by Proposition~\ref{one-matching} there is an automorphism $\b\in\Aut(P)$ of order at most $2$ such that $R^\b=L$. This implies that $\b\in\Aut(P,R\cup L)=\lg \a\rg$. Clearly, $R\neq L$, so $\b$ has order $2$. It follows that $\b=\a^2$. However, $R^{\a^2}=R$ and $L^{\a^2}=L$, a contradiction. Thus, $\G$ is non-Cayley. For the necessity, since $p$ is odd, the subgraph induced by each orbit of $R(P)$ must have even valency. It follows that $\G$ is $0$- or $2$-type. \medskip \f{\bf Case~1}\ $\G$ is $0$-type. By Lemma~\ref{normal}, $R(P)\unlhd\Aut(\G)$. Since $R(P)$ has two orbits on $V(\G)$, the quotient graph $\G_{R(P)}$ of $\G$ relative to $R(P)$ is the $3$-dipole Dip$_3$ (see Fig.~(\ref{fig-1})). \begin{figure}[ht] \begin{center} \unitlength 4mm \begin{picture}(10,6) \put(2, 3){\circle*{0.4}}\put(8, 3){\circle*{0.4}} \qbezier(2, 3)(5, 6)(8, 3)\qbezier(2, 3)(5, 0)(8, 3)\put(2,3){\line(1, 0){6}} \end{picture} \end{center}\vspace{-.5cm} \caption{The $3$-dipole Dip$_3$} \label{fig-1} \end{figure} This implies that $\G$ is a regular cover of Dip$_3$, and so $\Aut(\G)$ can project to a subgroup of $\Aut(\G_{R(P)})$. Since $\Aut($Dip$_3)\cong S_3\times\mz_2$, $\Aut(\G)/R(P)\leq\mz_2\times\mz_2$ because $\G$ is not symmetric by Proposition~\ref{2pnsymmetric}. Since $p>2$, $\Aut(\G)=R(P)\rtimes Q$, where $12$. Suppose $|R\cap L|=0$. In this case, the neighbors of $\{1_0,1_1\}$ in $\G_\B$ are $\{a_0,a_1\},$ $\{b_0,b_1\},$ $\{x_0,x_1\}$ and $\{y_0,y_1\}$. So, $\G_\B$ is a tetravalent Cayley graph on $P$. Note that $A_{1_0}=A_{1_1}$. Since $A$ is not regular on $V(\G)$, $A_{1_0}$ interchanges $a_0$ and $b_0$, and also interchanges $x_1$ and $y_1$. Since $\{1_0,1_1\}$ is a block of $A$, $A$ contains an element interchanging $1_0$ and $1_1$. This implies that $A_{\{1_0,1_1\}}$ is transitive on the neighborhood of $\{1_0,1_1\}$ in $\G_\B$. So, $A$ is an arc-transitive automorphism group of $\G_\B$. Let $X=\Cay(P, R\cup L)$. It is easy to verify that the following map $$f: g\mapsto \{g_0,g_1\}, \forall g\in P$$ is an isomorphism from $X$ to $\G_\B$. So, $X\cong\G_\B$. Since $\G_\B$ is arc-transitive, $X$ is also arc-transitive. Since $P$ is a $p$-group with $p>2$, we may assume that $R=\{a,a^{-1}\}$ and $L=\{x,x^{-1}\}$. By Proposition~\ref{regular-p}, $X$ is a normal Cayley graph, and so $\Aut(\G_\B)=R(P)\rtimes\Aut(P, R\cup L)$. Clearly, $\Aut(P, R\cup L)$ acts faithfully on $R\cup L$. Since $p>2$, it is easy to see that $R,L$ are blocks of $\Aut(P, R\cup L)$ on $R\cup L$. It follows that $\Aut(P, R\cup L)\leq D_8$, and so $A\leq \Aut(\G_\B)\leq R(P)\rtimes D_8$. Also, as $R,L$ are blocks of $\Aut(P, R\cup L)$ on $R\cup L$, by Proposition~\ref{automorphism2}, each element in $\Aut(P, R\cup L)$ can also induce an automorphism of $\G$. This implies that $A=\Aut(\G_\B)$. Since $\G$ is arc-transitive, $\Aut(P, R\cup L)$ is isomorphic to $\mz_2\times\mz_2, \mz_4,$ or $D_8$. If $\Aut(P, R\cup L)\cong\mz_2\times\mz_2$ or $D_8$, then there exists an involution, say $\a$, in $\Aut(P, R\cup L)$ which interchanges $R$ and $L$. By Proposition~\ref{automorphism2}, $\a$ can induce an automorphism, say $\d_\a$, of $\G$ of order $2$ such that $R(P)\rtimes\lg \d_\a\rg$ is regular on $V(\G)$, and so $\G$ is Cayley, a contradiction. Thus, $\Aut(P, R\cup L)\cong\mz_4$. \end{proof} \section{Cubic non-Cayley vertex-transitive graphs of order $2p^3$} Let $p$ be an odd prime. We first introduce some cubic connected non-Cayley vertex-transitive graphs of order $2p^3$. It is well known that $\mz_{p^n}^*$ is cyclic and has order $p^{n-1}(p-1)$. So, if $4\ |\ (p-1)$ then $\mz_{p^n}^*$ has a unique subgroup of order $4$. Clearly, if $\ld$ is an element of order $4$ in $\mz_{p^n}^*$, then $\{1,-1,\ld,-\ld\}$ is the unique subgroup of order $4$ in the cyclic group $\mz_{p^n}^*$. \begin{example}\label{exam-0} Let $p$ be a prime such that $p-1$ is divisible by $4$ and let $\ld$ be an element of order $4$ in $\mz_{p^3}^*$. The graph $\mathcal{NC}_{2p^3}^0$ is defined to be the bi-Cayley graph ${\rm BiCay}(\mz_{p^3}, R, L,\{1\})$, where $\mz_{p^3}=\lg a\rg$, $R=\{a,a^{-1}\}$ and $L=\{a^\ld, a^{-\ld}\}$. \end{example} By the uniqueness of the subgroup of order $4$ in $\mz_{p^3}$, the graph $\mathcal{NC}_{2p^3}^0$ is independent of the choice of $\ld$. Let $\a$ be the automorphism of $\mz_{p^3}$ induced by the map $a\mapsto a^\ld$. Then $\a$ swaps $R$ and $L$, and by Proposition~\ref{automorphism2}, $\d_\a\in\Aut(\mathcal{NC}_{2p^3}^0)$ (see Equations (1)-(2) for the definition of $\d_\a$) and so $\mathcal{NC}_{2p^3}^0$ is vertex-transitive because $\d_\a$ swaps the two orbits of $\mz_{p^3}$ on $V(\mathcal{NC}_{2p^3}^0)$. In view of \cite[Theorem~1]{X}, we have $\Cay(\mz_{p^3}, R\cup L)$ is a tetravalent normal arc-transitive Cayley graph and $\Aut(\mz_{p^3}, R\cup L)\cong\mz_4$. If $p=5$, then by Magma~\cite{BCP}, $\mathcal{NC}_{2p^3}^0$ is non-Cayley vertex-transitive and $|\Aut(\mathcal{NC}_{2p^3}^0)|=4p^3$, and if $p>5$, then by Theorem~\ref{characterize}, again we have $\mathcal{NC}_{2p^3}^0$ is non-Cayley vertex-transitive. \begin{example}\label{exam-1} Let $p$ be a prime such that $p-1$ is divisible by $4$ and let $\ld$ be an element of order $4$ in $\mz_{p}^*$. The graph $\mathcal{NC}_{2p^3}^1$ is defined to be the bi-Cayley graph ${\rm BiCay}(\mz_{p^2}\times\mz_p, R, L,\{1\})$, where $\mz_{p^2}\times\mz_p=\lg a\rg\times\lg b\rg$, $R=\{a,a^{-1}\}$ and $L=\{(ab)^\ld, (ab)^{-\ld}\}$. \end{example} By the uniqueness of the subgroup of order $4$ in $\mz_{p}$, the graph $\mathcal{NC}_{2p^3}^1$ is independent of the choice of $\ld$. Let $\b$ be the automorphism of $\mz_{p^2}\times\mz_p$ induced by the map $a\mapsto (ab)^\ld, b\mapsto a^{\ld^3+\ld}b^{-\ld}$. Then $\b$ swaps $R$ and $L$, and by Proposition~\ref{automorphism2}, $\d_\b\in\Aut(\mathcal{NC}_{2p^3}^1)$ and so $\mathcal{NC}_{2p^3}^1$ is vertex-transitive because $\d_\b$ swaps the two orbits of $\mz_{p^2}\rtimes\mz_p$ on $V(\mathcal{NC}_{2p^3}^1)$. In view of \cite[Proposition~3.3]{xx}, we have $\Cay(\mz_{p^2}\times\mz_p, R\cup L)$ is a tetravalent normal arc-transitive Cayley graph and $\Aut(\mz_{p^2}\times\mz_p, R\cup L)\cong\mz_4$. If $p=5$, then by Magma~\cite{BCP}, $\mathcal{NC}_{2p^3}^1$ is non-Cayley vertex-transitive and $|\Aut(\mathcal{NC}_{2p^3}^1)|=4p^3$, and if $p>5$, then by Theorem~\ref{characterize}, again we have $\mathcal{NC}_{2p^3}^1$ is non-Cayley vertex-transitive. Also, note that $\Aut(\mathcal{NC}_{2p^3}^0)\cong\mz_{p^3}\rtimes\mz_4$ and $\Aut(\mathcal{NC}_{2p^3}^1)\cong(\mz_{p^2}\rtimes\mz_p)\rtimes\mz_4$. It follows that $\mathcal{NC}_{2p^3}^0$ and $\mathcal{NC}_{2p^3}^1$ are not isomorphic to each other. \begin{theorem}\label{classification} Let $p$ be a prime. Then a cubic vertex-transitive graph of order $2p^3$ is non-Cayley if and only if it is isomorphic to $\mathcal{NC}_{2p^3}^0$ or $\mathcal{NC}_{2p^3}^1$. \end{theorem} \begin{proof} By~\cite{McKay}, all connected cubic vertex-transitive graphs of order $16$ are Cayley. By~\cite{PSV}, if $p=3$, then all connected cubic vertex-transitive graphs of order $54$ are Cayley, and if $p=5$, then up to isomorphism, there are exactly two non-Cayley vertex-transitive graphs of order $2\cdot 5^3$, and so $\G\cong$ $\mathcal{NC}_{2\cdot 5^3}^0$ or $\mathcal{NC}_{2\cdot 5^3}^1$. In what follows, assume that $p>5$. By Lemma~\ref{isbicayley}, $\G$ is a bi-Cayley graph over a group $P$, where $P$ is a Sylow $p$-subgroup of $\Aut(\G)$. By Theorem~\ref{characterize}, $\G={\rm BiCay}(P,$ $ R,$ $ L,$ $ \{1\})$ and $\Cay(P,$ $ R\cup L)$ is a tetravalent normal arc-transitive Cayley graph such that $\Aut(P, R\cup L)\cong\mz_4$. Since $|\G|=2p^3$, one has $|P|=p^3$. Noting that $R=R^{-1}$ and $L=L^{-1}$, by Proposition~\ref{p3}, one of the following happens: $$ \begin{array}{ll} (1)&P=\mz_{p^3}=\lg a\rg, R=\{a, a^{-1}\}, L=\{a^\ld, a^{-\ld}\} (\ld^2\equiv-1\ (\mod p^3));\\ (2)&P=\mz_{p^2}\times\mz_p=\lg a\rg\times\lg b\rg, R=\{a, a^{-1}\}, L=\{(ab)^\ld, (ab)^{-\ld}\} (\ld^2\equiv-1\ (\mod p));\\ (3)&P=\mz_{p^2}\times\mz_p=\lg a\rg\times\lg b\rg, R=\{a, a^{-1}\}, L=\{ab, (ab)^{-1}\};\\ (4)&P=\lg a, b, c\ |\ a^p=b^p=c^p=1, c=[a, b], [a, c]=[b, c]=1\rg, \\ &R=\{a, a^{-1}\}, L=\{b, b^{-1}\}. \end{array} $$ If $(1)$ happens, then $\G\cong\mathcal{NC}_{2p^3}^0$, and if $(2)$ happens, then $\G\cong\mathcal{NC}_{2p^3}^1$. If $(3)$ happens, then in view of \cite[Proposition~3.3]{xx}, we have $\Aut(P, R\cup L)\cong\mz_2\times\mz_2$. This is impossible by Theorem~\ref{characterize}. If $(3)$ happens, then $P=\lg a, b, c\ |\ a^p=b^p=c^p=1, c=[a, b], [a, c]=[b, c]=1\rg$, and any two elements generating $P$ have the same relation as $a$ and $b$. It follows that $\Aut(P, R\cup L)\cong D_8$, and by Theorem~\ref{characterize}, $\G$ is not non-Cayley, a contradiction. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} This work was supported by the National Natural Science Foundation of China $(11271012,$ $ 11571035,$ $11231008),$ the Fundamental Research Funds for the Central Universities\\ $(2015$JBM$110)$ and the 111 Project of China (B16002). The author also would like to thank the anonymous referee for the valuable comments and suggestions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \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}{10} \bibitem{B} N. Biggs, Algebraic Graph Theory, Second ed, { Cambridge University Press}, Cambridge, 1993. \bibitem{BMBook} J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, New York: Elsevier North Holland, 1976. \bibitem{BCP} W. Bosma, C. Cannon, C. Playoust, The MAGMA algebra system I: The user language, J. Symbolic Comput. 24 (1997) 235--265. \bibitem{dJ} M.J. de Resmini, D. Jungnickel, Strongly regular semi-Cayley graphs, J. Algebraic Combin. 1 (1992) 171--195. \bibitem{FK3} Y.-Q. Feng, J.H. Kwak, Cubic symmetric graphs of order twice an odd prime power, J. Aust. Math. Soc. 81 (2006), 153--164. \bibitem{FXregular} Y.-Q. Feng, M.Y. Xu, Automorphism groups of tetravalent Cayley graphs on regular $p$-groups, Discrete Math. 305 (2005) 354--360. \bibitem{FXp3} Y.-Q. Feng, M.Y. Xu, Normality of tetravalent Cayley graphs of odd prime-cube order and its application, Acta Math. Sin., English Ser. 21 (2005) 903--912. \bibitem{Gao2011} X. Gao, W. Liu, Y. Luo, On the extendability of certain semi-Cayley graphs of finite abelian groups, Discrete Math. 311 (2011) 1978--1987. \bibitem{Gao2010} X. Gao, Y. Luo, The spectrum of semi-Cayley graphs over abelian groups, Linear Algebra Appl. 432 (2010) 2974--2983. \bibitem{H} B. Huppert, Eudliche Gruppen I, Springer-Verlag, Berlin, 1967. \bibitem{kovacs} I. Kov\'acs, A. Malni\v c, D. Maru\v si\v c, \v S. Miklavi\v c, One-matching bi-Cayley graphs over abelian groups, European J. Combin. 30 (2009) 602--616. \bibitem{KMZ} K. Kutnar, D. Maru\v si\v c, C. Zhang, On cubic non-Cayley vertex-transitive graphs, J. Graph Theory 69 (2012) 77--95. \bibitem{LM} K.H. Leung, S.L. Ma, Partial difference triples, J. Algebraic Combin. 2 (1993) 397--409. \bibitem{Marusic} D. Maru\v si\v c, On vertex symmetric digraphs, Discrete Math. 36 (1981) 69--81. \bibitem{McKay} B.D. McKay, Transitive graphs with fewer than $20$ vertices, Math. Comp. 33 (1979) 1101--1121. \bibitem{Pisanski} T. Pisanski, A classication of cubic bicirculants, Discrete Math. 307 (2007) 567--578. \bibitem{PSV} P. Poto\v cnik, P. Spiga, G. Verret, A census of small connected cubic vertex-transitive graphs, http://www.matapp.unimib.it/$\sim$spiga/. \bibitem{WI} H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964. \bibitem{X1} M.Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182 (1998) 309--319. \bibitem{X} M.Y. Xu, A note on one-regular graphs, Chinese Sci. Bull. 45 (2000) 2160--2162. \bibitem{xx} J. Xu, M.Y. Xu, Arc-transitive Cayley graphs of valency at most four on abelian groups, Southeast Asian Bull. Math. 25 (2001) 355--363. \bibitem{Zhouadv}J.-X. Zhou, Cubic vertex-transitive graphs of order $2p^2$, Advances in Math. (China) 37 (2008) 605--609. \bibitem{ZF} J.-X. Zhou, Yan-Quan Feng, Cubic bi-Cayley graphs over abelian groups, European J. Combin. 36 (2014) 679-693. \end{thebibliography} \end{document}