# Tetravalent vertex-transitive graphs of order $6p$

Majid Arezoomand, Mohsen Ghasemi* and Mohammad A. Iranmanesh

###### Abstract.

A graph is vertex-transitive if its automorphism group acts transitively on
vertices of the graph. A vertex-transitive graph is a Cayley graph if its
automorphism group contains a subgroup acting regularly on its vertices. In
this paper, the tetravalent vertex-transitive non-Cayley graphs of order $6p$
are classified for each prime $p$.

MSC(2010): Primary: 20B20, Secondary: 05C25.
Keywords: Tetravalent graph, vertex transitive graph, non-Cayley graph.
$*$Corresponding author

##  1\. Introduction

In this paper we consider undirected finite connected graphs without loops or
multiple edges. For a graph $X$ we use $V(X)$, $E(X)$, $A(X)$ and ${\rm
Aut}(X)$ to denote its vertex set, edge set, arc set and its full automorphism
group, respectively. For $u,v\in V(X)$, $u\thicksim v$ represents that $u$ is
adjacent to $v$, and is denoted by $\\{u,v\\}$ the edge incident to $u$ and
$v$ in $X$, and $N_{X}(u)$ is the neighborhood of $u$ in $X$, that is, the set
of vertices adjacent to $u$ in $X$. A graph $X$ is said to be $G$-vertex-
transitive, $G$-edge-transitive and $G$-arc-transitive (or $G$-symmetric) if
$G\leq{\rm Aut}(X)$ acts transitively on $V(X)$, $E(X)$ and $A(X)$,
respectively. In the special case, if $G={\rm Aut}(X)$ then $X$ is said to be
vertex-transitive, edge-transitive and arc-transitive (or symmetric). An s-arc
in a graph $X$ is an ordered $(s+1)$-tuple $(v_{0},v_{1},\cdots,v_{s})$ of
vertices of $X$ such that $v_{i-1}$ is adjacent to $v_{i}$ for $1\leq i\leq
s$, and $v_{i-1}\neq v_{i+1}$ for $1\leq i\leq s$; in other words, a directed
walk of length $s$ which never includes a backtracking. A graph $X$ is said to
be $s$-arc-transitive if ${\rm Aut}(X)$ is transitive on the set of $s$-arcs
in $X$. A subgroup of the automorphism group of a graph $X$ is said to be
$s$-regular if it acts regularly on the set of $s$-arcs of $X$. Recall that a
permutation group $G$ acting on a set $\Omega$ is called semiregular if the
stabilizer of $\alpha\in G$, $G_{\alpha}=1$ for all $\alpha\in G$ and is
called regular if it is semiregular and transitive.

Let $G$ be a finite group and $S$ be a subset of $G$ such that $1\notin S$ and
$S=S^{-1}$ where $S^{-1}=\\{s^{-1}\mid s\in S\\}$. The Cayley graph $X={\rm
Cay}(G,S)$ on $G$ with respect to $S$ is defined as the graph with vertex set
$V(X)=G$ and edge set $E(X)=\\{\\{g,sg\\}\mid g\in G,s\in S\\}$. The
automorphism group ${\rm Aut}(X)$ of $X$ contains the right regular
representation $R(G)$ of $G$, the acting group of $G$ by right multiplication,
as a subgroup, and $R(G)$ is regular on $V(X)$. A Cayley graph, ${\rm
Cay}(G,S)$ is said to be normal if $R(G)$ is normal in ${\rm Aut}({\rm
Cay}(G,S))$. By [36, Proposition 3.1], $N_{{\rm Aut}({\rm
Cay}(G,S))}(R(G))=R(G){\rm Aut}(G,S)$, where ${\rm Aut}(G,S)=\\{\alpha\in{\rm
Aut}(G)\mid S^{\alpha}=S\\}$. Note that ${\rm Aut}(X)$ is normal if and only
if ${\rm Aut}(G,S)={\rm Aut}(X)_{v}$ for some $v\in V(X)$.

It is well known that a vertex-transitive graph is a Cayley graph if and only
if its automorphism group contains a subgroup acting regularly on its vertex
set (see, for example, [32, Lemma 4]). There are vertex-transitive graphs
which are not Cayley graphs and the smallest one is the well-known Petersen
graph. Such a graph will be called a vertex-transitive non-Cayley graph, or a
$\mathcal{VNC}$-graph for short.

Many publications have been put into service of investigation the
$\mathcal{VNC}$-graphs from different perspectives. For example, in [19],
Marušič asked for a determination of the set $\mathcal{NC}$ of non-Cayley
numbers, that is, those numbers $n$ for which there exists a
$\mathcal{VNC}$-graph of order $n$, and to settle this question, a lot of
$\mathcal{VNC}$-graphs were constructed in [12, 14, 15, 20, 21, 22, 23, 24,
25, 27, 30]. In [8], Feng considered the question to determine the smallest
valency for $\mathcal{VNC}$-graphs of a given order and it was solved for the
graphs of odd prime power order. From [6, 18] all cubic or tetravalent
$\mathcal{VNC}$-graphs of order $2p$ are known for each prime $p$. In [38, 39,
40], all cubic $\mathcal{VNC}$-graphs of order $2pq$ were classified for any
primes $p$ and $q$. Also tetravalent $\mathcal{VNC}$-graphs of order $2p^{2}$
and $4p$ were classified for any prime $p$ (see [5, 37]). We know that all
components of vertex-transitive graphs are isomorphic. So without loss of
generality we may assume that $X$ is connected.

A graph $X$ is said to be a bi-Cayley graph over a group $G\leq{\rm Aut}(X)$
if it admits $G$ as a semiregular automorphism group with two orbits of equal
size. Note that every bi-Cayley graph admits the following concrete
realization. Let $R,L$ and $S$ be subsets of a group $G$ such that $R=R^{-1}$,
$L=L^{-1}$ and $R\cup L$ does not contain the identity element of $G$. Let
$g_{0}=(g,0)$ and $g_{1}=(g,1)$ where $g\in G$. Define the graph ${\rm
BiCay}(G,R,L,S)$ to have vertex set the union of the right part
$G_{0}=\\{g_{0}\mid g\in G\\}$ and the left part $G_{1}=\\{g_{1}\mid g\in
G\\}$ and edge set the union of the right edges $\\{\\{h_{0},g_{0}\\}\mid
gh^{-1}\in R\\}$, the left edges $\\{\\{h_{1},g_{1}\\}\mid gh^{-1}\in L\\}$
and the spokes $\\{\\{h_{0},g_{1}\\}\mid gh^{-1}\in S\\}$. Now we introduce
the coset graph constructed from a finite group $G$ relative to a subgroup $H$
of $G$ and a union $D$ of some double cosets of $H$ in $G$ such that
$D^{-1}=D$. The coset graph ${\rm Cos}(G,H,D)$ of $G$ with respect to $H$ and
$D$ is defined to have vertex set $[G:H]$, the set of right cosets of $H$ in
$G$, and edge set $\\{\\{Hg,Hdg\\}\mid g\in G,d\in D\\}$. The graph ${\rm
Cos}(G,H,D)$ has valency $|D|/|H|$ and is connected if and only if $D$
generates the group $G$. The action of $G$ on $V({\rm Cos}(G,H,D))$ by right
multiplication induces a vertex-transitive automorphism group, which is arc-
transitive if and only if $D$ is a single double coset. Clearly, ${\rm
Cos}(G,H,D)\cong{\rm Cos}(G,H^{\alpha},D^{\alpha})$ for every $\alpha\in{\rm
Aut}(G)$. Conversely, let $X$ be a graph and let $A$ be a vertex-transitive
subgroup of ${\rm Aut}(X)$. By [31], the graph $X$ is isomorphic to a coset
graph ${\rm Cos}(A,H,D)$, where $H=A_{u}$ is the stabilizer of $u\in V(X)$ in
$A$ and $D$ consists of all elements of $A$ which map $u$ to one of its
neighbors. It is easy to show that ${\rm Core}_{A}(H)=1$ and that $D$ is a
union of some double cosets of $H$ in $A$ satisfying $D=D^{-1}$. Recall that a
graph $\Gamma=(V,E)$ is called an $(m,n)$-metacirculant, where $m,n$ are
positive integers, if $\Gamma$ is of order $|V|=mn$ and has two automorphisms
$\rho,\sigma$ such that

  * $(a)$

$\langle\rho\rangle$ is semiregular and has $m$ orbits on $V$,

  * $(b)$

$\sigma$ cyclically permutes the $m$ orbits of $\langle\rho\rangle$ and
normalizes $\langle\rho\rangle$, and

  * $(c)$

$\sigma^{m}$ fixes at least one vertex of $\Gamma$.

A graph $\widetilde{X}$ is called a covering of a graph $X$ with projection
$\wp:\widetilde{X}\rightarrow X$ if there is a surjection
$\wp:V{(\widetilde{X})}\rightarrow V(X)$ such that
$\wp|_{N_{\widetilde{X}}({\tilde{v}})}:{N_{\widetilde{X}}({\tilde{v}})}\rightarrow{N_{X}(v)}$
is a bijection for any vertex $v\in V(X)$ and $\tilde{v}\in\wp^{-1}(v)$. A
covering $\widetilde{X}$ of $X$ with a projection $\wp$ is said to be regular
(or $K$-covering) if there is a semiregular subgroup $K$ of the automorphism
group ${\rm Aut}(\widetilde{X})$ such that the graph $X$ is isomorphic to the
quotient graph $\widetilde{X}/K$, say by $\Im$, and the quotient map
$\widetilde{X}\rightarrow\widetilde{X}/K$ is the composition $\wp\Im$ of $\wp$
and $\Im$ (for the purpose of this paper, all functions are composed from left
to right). If $K$ is cyclic or elementary abelian then $\widetilde{X}$ is
called a cyclic or an elementary abelian covering of $X$, and if
$\widetilde{X}$ is connected $K$ becomes the covering transformation group.
The fibre of an edge or a vertex is its preimage under $\wp$. An automorphism
of $\widetilde{X}$ is said to be fibre-preserving if it maps a fibre to a
fibre, while every covering transformation maps a fibre on to itself. All of
fibre-preserving automorphisms form a group called the fibre-preserving group.

Let $\widetilde{X}$ be a $K$-covering of $X$ with a projection $\wp$. If
$\alpha\in{\rm Aut}(X)$ and $\widetilde{\alpha}\in{\rm Aut}(\widetilde{X})$
satisfy $\widetilde{\alpha}\wp=\wp\alpha$, we call $\widetilde{\alpha}$ a lift
of $\alpha$, and $\alpha$ the projection of $\widetilde{\alpha}$. Concepts
such as a lift of a subgroup of ${\rm Aut}(X)$ and the projection of a
subgroup of ${\rm Aut}(\widetilde{X})$ are self-explanatory. The lifts and the
projections of such subgroups are of course subgroups in ${\rm
Aut}(\widetilde{X})$ and ${\rm Aut}(X)$, respectively.

Let $m_{1},m_{2}>1$ be two odd integers such that $(m_{1},m_{2})=1$. Let
$1\leq t\leq m_{2}$, $(t,m_{2})=1$ be such that $t^{2}\equiv-1\pmod{m_{2}}$.
Let $H=\langle r\rangle\times\langle
s\rangle\cong\mathbb{Z}_{m_{1}}\times\mathbb{Z}_{m_{2}}=\mathbb{Z}_{m_{1}m_{2}}$.
Set $R=\\{r,r^{-1}\\}$, $L=\\{r^{t},r^{-t}\\}$ and $S=\\{1,s\\}$ and
$X_{m_{1},m_{2},t}={\rm BiCay}(H,R,L,S)$. Then we have the following result.

######  Proposition 1.

[29, Theorem 4.3] Let $X$ be a connected tetravalent vertex-transitive bi-
Cayley graph over a cyclic group of odd order $n$. Then $X$ is a
$\mathcal{VNC}$-graph if and only if $X\cong X_{m_{1},m_{2},t}$ for some
integers $m_{1},m_{2}$ and $t$.

The following theorem is the main result of this paper.

######  Theorem 2.

Let $X$ be a connected tetravalent vertex-transitive graph of order $6p$,
where $p$ is a prime. Then $X$ is a $\mathcal{VNC}$-graph if and only if
$X\cong X_{3,p,t}$, where $1\leq t\leq p-1$ and $t^{2}\equiv-1$ (mod $p$) or
$X$ is one of the nine specified graphs.

##  2\. Preliminaries

In this section, we introduce some notation and definitions as well as some
preliminary results which will be used later in the paper.

For a regular graph $X$, use $d(X)$ to represent the valency of $X$, and for
any subset $B$ of $V(X)$, the subgraph of $X$ induced by $B$ will be denoted
by $X[B]$. Let $X$ be a connected vertex-transitive graph, and let $G\leq{\rm
Aut}(X)$ be vertex-transitive on $X$. For a $G$-invariant partition $\Omega$
of $V(X)$, the quotient graph $X_{\Omega}$ is defined as the graph with vertex
set $\Omega$ such that, for any two vertices $B,C\in\Omega$, $B$ is adjacent
to $C$ if and only if there exist $u\in B$ and $v\in C$ which are adjacent in
$X$. Let $N$ be a normal subgroup of $G$. Then the set $\Omega$ of orbits of
$N$ in $V(X)$ is a $G$-invariant partition of $V(X)$. In this case, the symbol
$X_{\Omega}$ will be replaced by $X_{N}$.

For two groups $M$ and $N$, by $N\rtimes M$ we denote the semidirect product
of $N$ by $M$. For a group $G$, the largest solvable normal subgroup of $G$ is
called the solvable radical of $G$ and is denoted by ${\rm Sol}(G)$. The outer
automorphism group of the group $G$, is the quotient, ${\rm Aut}(G)/{\rm
Inn}(G)$, where ${\rm Aut}(G)$ is the automorphism group of $G$ and ${\rm
Inn}(G)$ is the subgroup consisting of inner automorphisms. The outer
automorphism group is usually denoted by ${\rm Out}(G)$. Also a lexicographic
product of two graphs $X$ and $Y$ which is denoted by $X[Y]$ is defined as the
graph with vertex set $V(X)\times V(Y)$ such that for any two vertices
$u=(x_{1},y_{1})$ and $v=(x_{2},y_{2})$ in $X[Y]$, $u$ is adjacent to $v$ in
$X[Y]$, whenever either $\\{x_{1},x_{2}\\}\in E(X)$ or $x_{1}=x_{2}$ and
$\\{y_{1},y_{2}\\}\in E(Y)$. Note that the lexicographic product of two Cayley
graphs is a Cayley graph. For group and graph-theoretic terms not defined here
we refer the reader to [4] and [35], respectively. Now we state the following
well known result.

######  Proposition 3.

Let $X$ be a $G$-vertex-transitive graph. Then $X$ is symmetric if and only if
each vertex stabilizer $G_{v}$ acts transitively on the set of vertices
adjacent to $v$, where $v\in V(X)$.

A finite simple group $G$ is said to be a $K_{3}$-group if its order has
exactly three distinct prime divisors. By [11, Pages 12-14 ], $G$ is
isomorphic to one of the following groups:

$A_{5},A_{6},{\rm PSL}_{2}(7),{\rm PSL}_{2}(8),{\rm PSL}_{2}(17),{\rm
PSL}_{3}(3),{\rm U}_{3}(3),{\rm U}_{4}(2).$

The socle of a group $G$ is the subgroup generated by the set of all minimal
normal subgroups of $G$, it is denoted by ${\rm soc}(G)$. Also a group $G$ is
said to be almost simple if $T\leq G\leq{\rm Aut}(T)$, where $T$ is a non-
abelian simple group. It is well known that $G$ is an almost simple group if
and only if ${\rm soc}(G)=T$ for some non-abelian simple group $T$.

Now we prove the following lemma.

######  Lemma 4.

Let $G$ be an almost simple group and ${\rm soc}(G)=A$, where $A$ is a non-
abelian simple $K_{3}$-group. Then

  * $(i)$

If $A\cong A_{5}$ then $G\cong A_{5}$ or $S_{5}$.

  * $(ii)$

If $A\cong A_{6}$ then $G\cong A_{6}$ or $S_{6}$ or
$S_{6}\rtimes\mathbb{Z}_{2}$.

  * $(iii)$

If $A\cong{\rm PSL}_{2}(p)$, where $p\in\\{7,17\\}$, then $G\cong{\rm
PSL}_{2}(p)$ or ${\rm PGL}_{2}(p)$.

  * $(iv)$

If $A\cong{\rm PSL}_{2}(8)$ then $G\cong{\rm PSL}_{2}(8)$ or $G/{\rm
PSL}_{2}(8)\cong\mathbb{Z}_{3}$.

  * $(v)$

If $A\cong{\rm PSL}_{3}(3)$ then $G\cong{\rm PSL}_{3}(3)$ or $G/{\rm
PSL}_{3}(3)\cong\mathbb{Z}_{2}$.

  * $(vi)$

If $A\cong{\rm U}_{3}(3)$ then $G\cong{\rm U}_{3}(3)$ or $G/{\rm
U}_{3}(3)\cong\mathbb{Z}_{2}$.

  * $(vii)$

If $A\cong{\rm U}_{4}(2)$ then $G\cong{\rm U}_{4}(2)$ or $G/{\rm
U}_{4}(2)\cong\mathbb{Z}_{2}$.

###### Proof.

Since $G$ is an almost simple group and ${\rm soc}(G)=A$, it implies that
$A\leq G\leq{\rm Aut}(A)$. If $A\cong A_{5}$, then $A_{5}\leq G\leq{\rm
Aut}(A_{5})$. Now since $|{\rm Out}(A_{5})|=2$, it follows that $G\cong A_{5}$
or $S_{5}$ and $(i)$ holds. Also if $A$ is isomorphic to one of ${\rm
PSL}_{2}(7)$, ${\rm PSL}_{2}(17)$, ${\rm PSL}_{3}(3)$, ${\rm U}_{3}(3)$ or
${\rm U}_{4}(2)$ then $|{\rm Out}(A)|=2$ and the assertions in
$(iii),(v),(vi)$ and $(vii)$ hold. If $A\cong A_{6}$ then $|{\rm
Out}(A_{6})|=4$ and ${\rm Aut}(A_{6})\cong S_{6}\rtimes\mathbb{Z}_{2}$. Thus
$G\cong A_{6}$ or $S_{6}$ or $S_{6}\rtimes\mathbb{Z}_{2}$ and $(ii)$ holds.
Finally if $A\cong{\rm PSL}_{2}(8)$ then $|{\rm Out}({\rm PSL}_{2}(8))|=3$.
Hence $G\cong{\rm PSL}_{2}(8)$ or $G/{\rm PSL}_{2}(8)\cong\mathbb{Z}_{3}$ and
$(iv)$ holds. ∎

##  3\. Main Results

In this section we classify all connected tetravalent $\mathcal{VNC}$-graphs
of order $6p$ where $p$ is a prime. To do this we prove the following
propositions.

######  Proposition 5.

Let $X$ be a graph, $A={\rm Aut}(X)$ and $N$ be the normal subgroup of $A$.
Also let $\Omega$ be the set of orbits of $N$ on $V(X)$ and $X_{N}$ be a
Cayley graph on subgroup of $A/K$, where $K$ is the kernel of action $N$ on
$\Omega$. Then $X$ is a Cayley graph on some subgroup of $A$.

###### Proof.

Suppose that $X_{N}={\rm Cay}(H,S)$, where $H\leq A/K$. Thus we may suppose
that $H=T/K$, where $T\leq A$. Let $x,y$ be two arbitrary elements of $V(X)$.
Set $X=x^{N}$ and $Y=y^{N}$. If $X=Y$ then there is $\alpha\in N$ so that
$x^{\alpha}=y$. Thus we may suppose that $X\neq Y$. By our assumption there is
an element $K\beta\in T/K$ such that $(x^{N})^{K\beta}=(y^{N})$ and so
$(x^{N})^{\beta}=(y^{N})$. Now $x^{\beta}=y^{n}$ for some $n\in N$. Now
$x^{({\beta}n^{-1})}=y$, where ${\beta}n^{-1}\in T$. Thus $T$ acts
transitively on $V(X)$. Suppose that $x^{t}=x$, where $t\in T$. Now
$(x^{N})^{Kt}=(x^{N})$, a contradiction. Thus $T$ acts regularly on $V(X)$ and
$X$ is a Cayley graph on $T$. ∎

######  Proposition 6.

Let $X$ be a connected tetravalent vertex-transitive graph of order $3p$,
where $p$ is a prime. Then $X$ is a $\mathcal{VNC}$-graph if and only if $X$
is isomorphic to $L(O_{3})$, the line graph of the Petersen graph.

###### Proof.

Suppose that $X$ is a connected tetravalent $\mathcal{VNC}$-graph of order
$3p$. By [26], all tetravalent vertex-transitive graphs of order $6,9$ and
$21$ are Cayley graphs. Also a tetravalent vertex-transitive graph of order
$15$ is not a Cayley graph and is isomorphic to $L(O_{3})$. Thus we may assume
that $p\geq 11$. If $X$ is symmetric then by [34, Page 215], is isomorphic to
one of $L_{3}(2)^{4}_{21}$ or $G(3p,2)$, which are Cayley graphs. Thus in the
following we may assume that $X$ is not symmetric. Let $A={\rm Aut}(X)$ and
$v\in V(X)$. Since $A_{v}$ is a $\\{2,3\\}$-group we have $|A|=2^{s}3^{t}p$,
for some non-negative integers $s,t$. We claim that $A$ is not solvable.

Suppose by contrary that $A$ is solvable and let $N$ be a minimal normal
subgroup of $A$. Then $N$ ia an elementary abelian $r$-group, where
$r\in\\{2,3,p\\}$, $N=T^{k}$, and $T$ is a simple group. Let $\Omega$ be the
set of orbits of $N$ on $V(X)$ and $K$ be the kernel of the action $A$ on the
set of orbits of $N$. By considering the order of graph, we see that either
$r=3$ or $r=p$. Assume first that $N$ is an elementary abelian $3$-group. Then
$X_{N}$ has order $p$ and has valency $2$ or $4$. It is easy to see that $K$
acts faithfully on each orbits and therefore $K\leq S_{3}$, which implies that
$|N|=3$. Let $P$ be a Sylow $p$-subgroup of $A$. Then $|P|=p$ and since $N$ is
a normal subgroup of $A$, it follows that the orbits of $N$ form a complete
block system of $A$. Moreover $P\times N$ acts regularly on $V(X)$ which
implies that $X$ is a Cayley graph, a contradiction. Next assume that $N$ is
an elementary abelian $p$-group. Then $X_{N}$ has order $3$ and its valency is
$2$. Hence ${\rm Aut}(X_{N})\cong D_{6}$. Suppose that
$\Omega=\\{\Delta_{0},\Delta_{1},\Delta_{2}\\}$ and
$\Delta_{i}\thicksim\Delta_{i+1}$ where the subscripts are taken modulo 3. If
$\Delta_{i}$ has an edge, then $X[\Delta_{i}]\cong C_{p}$ and it is easy to
see that $|K_{v}|\leq 2$ where $v\in V(X)$. Thus we have $|K|\leq 2p$. In case
$\Delta_{i}$ has no edge, then since $|V(X_{N})|=3$ and $p\geq 11$ we conclude
that $X[\Delta_{i}\cup\Delta_{i+1}]\cong C_{2p}$. Let $K^{*}$ be the kernel of
the action of $K$ on $X[\Delta_{i}\cup\Delta_{i+1}]$. Now the connectivity of
$X$ and transitivity of $A/K$ on $V(X_{N})$ imply that $K^{*}=1$ and
consequently, $K\leq{\rm Aut}(X[\Delta_{i}\cup\Delta_{i+1}])\cong D_{4p}$.
Since $K$ fixes $\Delta_{i}$ it follows that $|K|\leq 2p$. Since $A/K$ is
transitive on $V(X_{N})$ it follows that 3 divides $|A/K|$ and $A/K$ has an
element of order $3$, say $K\alpha$, where $\alpha\in A$. Therefore
$\alpha^{3}\in K$ and hence $o(\alpha^{3})=1$, 2, $p$ or $2p$. If
$\alpha^{3}=1$ then $\langle\alpha\rangle.P$ acts transitively and so
regularly on $V(X)$, a contradiction. Also if $o(\alpha^{3})=2$, $p$ or $2p$
then $\alpha^{2}$, $\alpha^{p}$ and $\alpha^{2p}$ have order $3$. In each case
there is an element of order 3, say $\beta$, in $A$ such that
$\langle\beta\rangle.P$ acts regularly on $V(X)$, another contradiction. Hence
$A$ is not solvable.

Let $L={\rm Sol}(A)$, $\Sigma$ be the set of orbits of $L$ on $V(X)$ and $K$
be the kernel of the action of $A$ on the set of orbits of $L$. Assume first
that $L$ is not trivial. Since $K_{v}$ is a $\\{2,3\\}$-group, it implies that
$K_{v}$ is solvable and by considering $K=LK_{v}$ we see that $K$ is solvable.
By the definition of solvable radical we conclude that $K=L$ and $A/L\leq{\rm
Aut}(X_{L})$. If ${\rm deg}(X_{L})=0$ then $A/L$ is solvable which implies
that $A$ is solvable, a contradiction. Since $|X|=3p$, this implies that ${\rm
deg}(X_{L})\neq 1,3$. In case ${\rm deg}(X_{L})=2$ we have ${\rm
Aut}(X_{L})\cong D_{2n}$, where $|V(X_{L})|=n$ and $n\in\\{3,p\\}$. Now $A/L$
is solvable and so $A$ is solvable, which is impossible. Thus we may assume
that ${\rm deg}(X_{L})=4$ and $L\leq S_{3}$. Thus $X_{L}$ is a circulant graph
and $X_{L}={\rm Cay}(G,S)$, where $G\cong\mathbb{Z}_{p}=\langle a\rangle$,
$S=\\{a^{r},a^{-r},a^{s},a^{-s}\\}$ where $(r,p)=(s,p)=1$. By [3, Theorem
1.2], $X_{L}$ is normal. Hence ${\rm Aut}(G,S)={\rm Aut}(X_{L})$. Since
$\sigma:a\mapsto a^{r}$ is an automorphism of $G$ we have
$S=\\{a,a^{-1},a^{i},a^{-i}\\}$ where $(i,p)=1$.

Set $B={\rm Aut}(X_{L})$ and $Y=X_{L}$. Let $B_{1}^{*}$ be the subgroup of
$B_{1}$ which fixes $\\{1\\}\cup S$ and $Y_{2}(1)$ be the subgraph of $Y$ with
vertex set

$\\{1\\}\cup
S\cup\\{a^{2},a^{-2},a^{i+1},a^{-i+1},a^{2i},a^{-2i},a^{-i-1},a^{i-1}\\}.$

Also

$N_{Y}(a)=\\{1,a^{2},a^{i+1},a^{-i+1}\\},N_{Y}(a^{-1})=\\{1,a^{-2},a^{-i-1},a^{i-1}\\},N_{Y}(a^{i})=\\{1,a^{i+1},a^{2i},a^{i-1}\\}$

and $N_{Y}(a^{-i})=\\{1,a^{-i+1},a^{-2i},a^{-i-1}\\}$. By a tedious
computation we find that $B_{1}^{*}=1$ and $B_{1}$ have no any element of
order $4$. Thus $B_{1}$ acts faithfully on $S$ and so $B_{1}\leq S_{4}$. Since
$B_{1}$ has no any element of order 4, by considering the subgroups of $S_{4}$
we see that either $B_{1}\cong\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ or
$|B_{1}|\in\\{1,2,6\\}$. Since $|B|=|B_{1}||G|$ we see that
$|B|\in\\{p,2p,4p,6p\\}$. Moreover $\alpha:a\rightarrow a^{-1}$ is an element
of ${\rm Aut}(G,S)$ and $o(\alpha)=2$. Hence $|B_{1}|=2$ or $4$ or $6$. From
the fact that $A/L$ acts transitively on $V(Y)$ we have $p\mid|A/L|$ and
$|A/L|\in\\{p,2p,4p,6p\\}$. By considering the order of $B$ we see that $G\leq
A/L$. So $G=T/L$ where $T\leq A$ and by Proposition 5, $X$ is a Cayley graph,
a contradiction.

Assume now that $L$ is trivial. Then $N$ is not solvable, where $N$ is the
minimal normal subgroup of $A$. If $N$ is semiregular then $|N|$ divides $3p$
and $N$ is solvable, a contradiction. Therefore $N$ is not semiregular and the
valency of quotient graph $X_{N}$ is not $4$. By considering the order of
graph we see that $X_{N}$ is not cubic. Thus ${\rm deg}(X_{N})=0$ or $2$ and
since $A/K\leq{\rm Aut}(X_{N})$ we conclude that $A/K$ is solvable. Moreover,
since $K=K_{v}N$ and $K_{v}$ is a $\\{2,3\\}$-group we conclude that $K/N$ is
solvable. From the fact that $A/K\cong(A/N)/(K/N)$ we conclude that $A/N$ is
solvable. We claim that $N$ is the unique minimal normal subgroup of $A$.
Suppose by contrary that $M\neq N$ is another minimal normal subgroup of $A$.
Since $MN/N\cong M/(M\cap N)\leq A/N$ we see that $M/(M\cap N)$ is solvable.
But $M\cap N=1$ and so $M$ is solvable, a contradiction. Hence $N$ is the only
minimal normal subgroup of $A$. Also since $|A|$ is not divided by $p^{2}$ we
conclude that $N$ is a simple group. Therefore $A$ is an almost simple group
and ${\rm soc}(A)=N$. From the fact that $A$ is a $\\{2,3,p\\}$-group, we
conclude that $N$ is a $K_{3}$-group. Also since $p\geq 11$ it follows that
$N$ is isomorphic to either ${\rm PSL}_{2}(17)$ or ${\rm PSL}_{3}(3)$.

First assume that $N\cong{\rm PSL}_{2}(17)$. Then by part $(iii)$ of Lemma 4,
$A\cong{\rm PSL}_{2}(17)$ or ${\rm PGL}_{2}(17)$. If $A\cong{\rm PSL}_{2}(17)$
then $|A:A_{v}|=51$. By [7], we see that $A$ has not any subgroup of index
$51$, a contradiction. Also if $A\cong{\rm PGL}_{2}(17)$, then by using GAP
[10], $A$ has no any subgroup of index $51$, another contradiction.

Assume now that $N\cong{\rm PSL}_{3}(3)$. In this case, by part $(v)$ of Lemma
4, $A\cong{\rm PSL}_{3}(3)$ or $A={\rm Aut}({\rm PSL}_{3}(3))$. In the first
case, by using GAP [10], and the fact that $A$ is a transitive permutation
group of degree $39$, we see that $A$ has a regular subgroup which means that
$X$ is a Cayley graph, a contradiction. However the later case is impossible,
because there is no transitive permutation representation of ${\rm Aut}({\rm
PSL}_{3}(3))$ of degree $39$. ∎

Let $X$ be a connected tetravalent vertex-transitive graph of order $6p$. If
$p=2$ or 3, then by [26], we see that $X$ is a Cayley graph. Also if $p=5$ or
$p=7$ then by [13] and using [28] we see that $X$ is isomorphic to one of the
graphs in the following lemma.

######  Lemma 7.

A connected tetravalent vertex-transitive non-Cayley graph of order at most 42
are listed below:

  * $(i)$

The Coxeter graph;

  * $(ii)$

the Desargues graph;

  * $(iii)$

the dodecahedron graph;

  * $(iv)$

one of the six graphs in Figure 1.

Figure 1. Six graphs illustrated in Lemma 7

Proof of the Theorem 2. Let $X$ be a connected tetravalent vertex-transitive
graph of order $6p$. If $p\leq 7$, then $X$ is one of the nine specified
graphs in Lemma 7. So we may assume that $p\geq 11$. Suppose that $X\cong
X_{3,p,t}$, then by Proposition 1, $X$ is a $\mathcal{VNC}$-graph. Assume that
$X$ is a $\mathcal{VNC}$-graph. Let $A={\rm Aut}(X)$ and $v\in V(X)$. Since
$X$ is connected and tetravalent, $A_{v}$ is a $\\{2,3\\}$-group and so
$|A|=2^{s}3^{t}p$ for some integers $s,t\geq 1$. Assume that $N$ is a minimal
normal subgroup of $A$. We know that $N=T^{k}$, where $T$ is a finite simple
group. Let $\Omega$ be the set of orbits of $N$ on $V(X)$ and $K$ be the
kernel of the action of $A$ on $\Omega$. Now we consider two cases:

Case I. $A$ is solvable.

In this case $N$ ia an elementary abelian $r$-group, where $r\in\\{2,3,p\\}$.
First suppose that $N$ is an elementary abelian $2$-group. In this case
$X_{N}$ has order $3p$ and valency $2$ or $4$. If $X_{N}$ has valency $2$ then
$X_{N}\cong C_{3p}$ and ${\rm Aut}(X_{N})\cong D_{6p}$. Suppose that
$\Omega=\\{\Delta_{0},\Delta_{1},\Delta_{2},\cdots,\Delta_{3p-1}\\}$, where
the subscripts are taken modulo $3p$. Also suppose that
$\Delta_{i}\thicksim\Delta_{i+1}$ in $X_{N}$. If for some $i$, the induced
graph $X[\Delta_{i}]$ has an edge then by considering the valency of $X$, we
see that $X[\Delta_{i-1}\cup\Delta_{i}]\cong C_{4}$ and
$X[\Delta_{i}\cup\Delta_{i+1}]\cong K_{4}$ where $1\leq i\leq 3p-1$. Now by
considering the induced graph $X[\Delta_{0}\cup\Delta_{3p-1}]$, we have a
contradiction. Thus we may assume that each $X[\Delta_{i}]$ has no any edge.
Thus for each $i$, $X[\Delta_{i}\cup\Delta_{i+1}]\cong C_{4}$. It is easy to
see that in this case $X\cong C_{3p}[2K_{1}]$, which is a Cayley graph, a
contradiction.

Assume now that $X_{N}$ has valency $4$. Then $K_{v}=1$ for each vertex $v$.
By Proposition 6, $X_{N}$ is a Cayley graph, unless the case where $X_{N}$ is
isomorphic to the line graph of the Petersen graph. Since $p\geq 11$, $X_{N}$
is not isomorphic to the line graph of the Petersen graph. Hence $X_{N}$ is a
Cayley graph and by [21, Proposition 1.2], is a $(3,p)$-metacirculant graph.
Thus $X_{N}$ has an automorphism $\sigma$ of order $p$ such that
$\langle\sigma\rangle$ is semiregular on the vertex set of $X_{N}$. Moreover
$X_{N}$ has an automorphism say $\tau$ such that $\tau$ normalizing
$\langle\sigma\rangle$ and cyclically permutes the $3$ orbits of
$\langle\sigma\rangle$ and has a cycle of size $3$ in its cycle decomposition.
Thus, for some positive integer $i$, the group
$\langle\sigma,\tau^{i}\rangle$, has order $3p$ and acts regularly on
$V(X_{N})$. Therefore we may suppose that $X_{N}={\rm Cay}(H,S)$ where
$H=\langle\sigma,\tau^{i}\rangle$. First suppose that $H\cong F_{3p}$. If
$X_{N}$ is normal then ${\rm Aut}(X_{N})_{1}={\rm Aut}(H,S)$. Since $X_{N}$ is
connected and ${\rm Aut}(H,S)$ acts faithfully on $S$ we conclude that ${\rm
Aut}(X_{N})_{1}\leq S_{4}$. Moreover $S=\\{x,x^{-1},y,y^{-1}\\}$ where $x$ and
$y$ have not the same order. It is easy to see that ${\rm Aut}(H,S)$ has no
any element of order $3$ or $4$. Thus by considering the subgroups of $S_{4}$
we see that ${\rm Aut}(X_{N})_{1}=1$ or $\mathbb{Z}_{2}$ or
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. Therefore $|{\rm Aut}(X_{N})|\leq 12p$
and so $|A/K|$ divides $12p$. By considering the order of ${\rm Aut}(X_{N})$
we see that $H\leq A/K$ and so $H=T/K$ for some $T\leq A$. Now $|T|=6p$ and
$T$ acts regularly on $V(X)$, a contradiction. Thus we may suppose that
$X_{N}$ is not normal. If $X_{N}$ is not primitive then by [17, Theorem 3.1]
we see that the valency of $X_{N}$ is not equal to $4$. Also if $X_{N}$ is
primitive then again by [34, Lemma 2.1] we have a contradiction. Therefore
$X_{N}$ is a Cayley graph on $\mathbb{Z}_{3p}$.

Thus $X_{N}$ is a circulant graph and $X_{N}={\rm Cay}(H,S)$, where
$S=\\{a^{i},a^{-i},a^{j},a^{-j}\\}$ and either $(i,3p)=1$ or $(j,3p)=1$ or
$(i-j,3p)=1$. Set $B={\rm Aut}(X_{N})$ and $Y=X_{N}$. Let $B_{1}^{*}$ be the
subgroup of $B_{1}$ which fixes $\\{1\\}\cup S$ and $Y_{2}(1)$ be the subgraph
of $Y$ with vertex set $\\{1\\}\cup S\cup(S^{2}-(1\cup S))$. We see that

$S^{2}-(1\cup
S)=\\{a^{2i},a^{i+j},a^{i-j},a^{-2i},a^{-i+j},a^{-i-j},a^{2j},a^{-2j}\\}.$

Also

$N_{Y}(a^{i})=\\{1,a^{2i},a^{i+j},a^{i-j}\\},N_{Y}(a^{-i})=\\{1,a^{-2i},a^{-i+j},a^{-i-j}\\},N_{Y}(a^{j})=\\{1,a^{i+j},a^{-i+j},a^{2j}\\}$

and $N_{Y}(a^{-j})=\\{1,a^{i-j},a^{-i-j},a^{-2j}\\}$. By a tedious computation
we have $B_{1}^{*}=1$ and $B_{1}$ has no any element of order $4$. Thus
$B_{1}$ acts faithfully on $S$ and so $B_{1}\leq S_{4}$. Since $B_{1}$ has no
any element of order $3$, and the fact that $\alpha:a\rightarrow a^{-1}$ is an
element of ${\rm Aut}(H,S)$ and $o(\alpha)=2$, it implies that
$B_{1}\cong\mathbb{Z}_{2}$ or $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ and so
$|{\rm Aut}(X_{N})|\in\\{6p,12p\\}$. Since $A/N$ acts transitively on $V(Y)$
we have that $3p$ divides $|A/N|$. Thus $|A/N|\in\\{3p,6p,12p\\}$. By
considering the order of $B$, we see that $H\leq A/N$ and so $H=T/N$ where
$T\leq A$. Now by Proposition 5, $X$ is a Cayley graph, a contradiction.

Now suppose that $N$ is an elementary abelian $3$-group and
$\Omega=\\{\Delta_{0},\Delta_{1},\Delta_{2},\cdots,\Delta_{2p-1}\\}$, where
the subscripts are taken modulo $2p$. Then $X_{N}$ has order $2p$ and so
$X_{N}$ has valency $2$, $3$ or $4$. First suppose that $X_{N}$ has valency
$2$. Then $X_{N}\cong C_{2p}$ and ${{\rm Aut}(X_{N})}\cong D_{4p}$. Suppose
that $\Delta_{i}\thicksim\Delta_{i+1}$ in $X_{N}$. If $\Delta_{i}$ has an edge
then by considering the valency of $X$ we see that $N$ acts faithfully on
$X[\Delta_{i}]$. Hence $|N|=3$ and by considering the valency of $X$ we see
that $X[\Delta_{i-1}\cup\Delta_{i}]\cong 3K_{2}$, $|K_{v}|\leq 2$ and $|K|\leq
6$. Since $A/K$ is transitive on $V(X_{N})$ it follows that $2p$ divides
$|A/K|$. Hence $A/K\cong\mathbb{Z}_{2p}$ or $A/K\cong D_{2p}$ or $A/K\cong
D_{4p}$. If $A/K\cong\mathbb{Z}_{2p}$ or $A/K\cong D_{4p}$, then $A/K$ has an
element of order $2p$, say $K\alpha$, where $\alpha\in A$. Therefore
$\alpha^{2p}\in K$ and hence $o(\alpha^{2p})=1$, $2$, $3$ or $6$. If
$\alpha^{2p}=1$ then $\langle\alpha\rangle\times\langle\gamma\rangle$, where
$\gamma$ is an element of order $3$ in $K$, acts transitively and so regularly
on $V(X)$, a contradiction. Also if $o(\alpha^{2p})=2$, $3$ or $6$ then
$\alpha^{2}$, $\alpha^{3}$ and $\alpha^{6}$ have order $2p$. Thus in each case
there is an element of order $2p$, say $\beta$, in $A$ such that
$\langle\beta\rangle\times\langle\gamma\rangle$ acts transitively and so
regularly on $V(X)$, a contradiction. Thus we may suppose that $A/K\cong
D_{2p}$. Thus $A/K$ has an element of order $p$, say $K\alpha$. Clearly,
$K\alpha$ does not fix any element of $V(X_{N})$ and so $\alpha$ does not.
Clearly, $\alpha^{p}\in K$ and so $o(\alpha^{p})=1$ or $2$ or $3$ or $6$. In
each case we can find an element of order $p$, say $\beta$ such that
$\langle\beta\rangle$ acts semiregularly on $V(X)$. Set
$H=\langle\beta\rangle\times\langle\gamma\rangle$, where $\gamma$ is an
element of order $3$ in $K$, acts semiregularly on $V(X)$ and has two orbits
on $V(X)$, which means that $X$ is a bi-Cayley graph over
$H\cong\mathbb{Z}_{3p}$. Then, by Proposition 1, $X\cong X_{3,p,t}$, where
$1\leq t\leq p-1$, and $t^{2}\equiv-1$ (mod $p$).

Suppose that $\Delta_{i}$ has no edge. Then it is easy to see that either
$X[\Delta_{0}\cup\Delta_{2p-1}]=X[\Delta_{i-1}\cup\Delta_{i}]\cong C_{6}$
$(1\leq i\leq 2p-1)$ or $X[\Delta_{i}\cup\Delta_{i+1}]\cong 3K_{2}$ $(1\leq
i\leq 2p-1,i\hskip 2.84544pt{\rm is}\hskip 2.84544pt{\rm odd})$ and
$X[\Delta_{i}\cup\Delta_{i+1}]\cong K_{3,3}$ $(0\leq i\leq 2p-1,i\hskip
2.84544pt{\rm is}\hskip 2.84544pt{\rm even})$.

First suppose that
$X[\Delta_{0}\cup\Delta_{2p-1}]=X[\Delta_{i-1}\cup\Delta_{i}]\cong C_{6}$
$(1\leq i\leq 2p-1)$. Then we consider the action of $K$ in $X[\Delta_{i}]$
$(0\leq i\leq 2p-1)$. Now it is easy to see that $K$ acts faithfully on
$X[\Delta_{i}]$ and so $K\leq S_{3}$. Since $2p$ divides $|A/K|$ and $|A/K|$
divides $4p$ with a similar arguments as above we get a contradiction. Now
suppose that $X[\Delta_{i}\cup\Delta_{i+1}]\cong 3K_{2}$ $(1\leq i\leq
2p-1,i\hskip 2.84544pt{\rm is}\hskip 2.84544pt{\rm odd})$ and
$X[\Delta_{i}\cup\Delta_{i+1}]\cong K_{3,3}$ $(0\leq i\leq 2p-2,i\hskip
2.84544pt{\rm is}\hskip 2.84544pt{\rm even})$.

Let $V(\Delta_{i})=\\{a_{i},b_{i},c_{i}\\}$ $(0\leq i\leq 2p-1)$. Without loss
of generality we may assume that $a_{i}\thicksim a_{i+1},b_{i}\thicksim
b_{i+1}$ and $c_{i}\thicksim c_{i+1}.$ Now it is easy to see that
$\alpha:a_{i}\mapsto b_{i},b_{i}\mapsto c_{i},c_{i}\mapsto a_{i}$ and
$\beta:a_{i}\mapsto a_{i+2},b_{i}\mapsto b_{i+2},c_{i}\mapsto c_{i+2}$ are
automorphisms of $X$ of orders $3$ and $p$, respectively, where $(0\leq i\leq
2p-1)$ . Clearly
$\langle\alpha\rangle\times\langle\beta\rangle\cong\mathbb{Z}_{3p}$ acts
semiregularly and has two orbits on $V(X)$. Therefore $X$ is a bi-Cayley graph
over the group $\mathbb{Z}_{3p}$ and again, by Proposition 1, $X=X_{3,p,t}$,
where $1\leq t\leq p-1$ and $t^{2}\equiv-1$ (mod $p$).

Suppose that $X_{N}$ has valency either $3$ or $4$. If ${\rm Aut}(X_{N})$ is
primitive then by [18, Corollary 6.6], $p\geq 313$, $2p=m^{2}+1$ for some
composite integer $m$. Also $\Gamma$ has valency either $\frac{m(m-1)}{2}$ or
$\frac{m(m+1)}{2}$, a contradiction. Thus we may suppose that ${\rm
Aut}(X_{N})$ is imprimitive. Now by [21, Theorem], $X_{N}$ is metacirculant.
If $X_{N}$ has valency 3 then by [33, Main Theorem], $X_{N}$ is isomorphic to
generalized Petersen graph $GP(p,k)$. By [9, Theorems 1, 2], we see that
$|{\rm Aut}(X_{N})|=4p$. If $\Delta_{i}$ has an edge then $X[\Delta_{i}]\cong
C_{3}$ $(0\leq i\leq 2p-1)$. We see that $X_{N}$ can not have valency $3$, a
contradiction. Thus we may suppose that $\Delta_{i}$ $(0\leq i\leq 2p-1)$ has
no edges. Let $V(\Delta_{i})=\\{a_{i},b_{i},c_{i}\\}$ $(0\leq i\leq 2p-1)$.
Let $\Delta_{i+1}$, $\Delta_{i+2}$ and $\Delta_{i+3}$ are the vertices
adjacent to $\Delta_{i}$. Since $X_{N}$ has valency 3, we may suppose that
$X[\Delta_{i}\cup\Delta_{i+1}]\cong C_{6}$,
$X[\Delta_{i}\cup\Delta_{i+2}]\cong 3K_{2}$ and
$X[\Delta_{i}\cup\Delta_{i+3}]\cong 3K_{2}$. Now it is easy to see that
$\alpha:a_{i}\mapsto b_{i},b_{i}\mapsto c_{i},c_{i}\mapsto a_{i}$ is an
automorphisms of $X$ of order $3$. Also $K$ acts faithfully on $X[\Delta_{i}]$
and so $K=N\cong\mathbb{Z}_{3}$. By [1, Theorem 1.1], we see that the
generalized Petersen graph is a normal bi-Cayley graph on $H=\mathbb{Z}_{p}$.
Clearly, $H$ acts semiregularly on $V(X_{N})$. If $H$ is not a subgroup of
$A/K$ then $p^{2}\mid|{\rm Aut}(X_{N})|$, a contradiction. Thus $H\leq A/K$
and $A/K$ has a semiregular element of order $p$, say $K\alpha$. Now
$\alpha^{p}\in K$ and so $o(\alpha^{p})=1,2$ or 3. In each case it is easy to
find an element of order $p$, say $\beta$, which is a power of $\alpha$. If
$\beta$ fixes an element then it is easy to see that $K\alpha$ or
$K\alpha^{2}$ or $K\alpha^{3}$ fixes at least one $\Delta_{i}$, a
contradiction. Now
$\langle\beta\rangle\times\langle\gamma\rangle\cong\mathbb{Z}_{3p}$ acts
semiregularly and has two orbits on $V(X)$ where $\gamma\in K$ and
$O(\gamma)=3$. Therefore $X$ is a bi-Cayley graph over group $\mathbb{Z}_{3p}$
and by Proposition 1, $X=X_{3,p,t}$, where $1\leq t\leq p-1$ and
$t^{2}\equiv-1\pmod{p}$. Also if $X_{N}$ has valency 4 then $N=K$. Since
$A_{v}$ is $\\{2,3\\}$-group we conclude that $A$ has a semiregular element of
order $p$, say $\delta$. Since $N_{A}(N)/C_{A}(N)$ is a subgroup of ${\rm
Aut}(N)\cong\mathbb{Z}_{2}$ we conclude that $\delta$ or ${\delta}^{2}\in
C_{A}(N)$. Also if $N=\langle\gamma\rangle$ then $\langle\delta,\gamma\rangle$
or $\langle\delta^{2},\gamma\rangle$ is a semiregular subgroup of ${\rm
Aut}(X)$ which is isomorphic to $\mathbb{Z}_{3p}$. Thus $X$ is a bi-Cayley
graph over $H\cong\mathbb{Z}_{3p}=\langle a\rangle$ and by Proposition 1,
$X=X_{3,p,t}$, where $1\leq t\leq p-1$ and $t^{2}\equiv-1\pmod{p}$.

Finally, suppose that $N$ is an elementary abelian $p$-group. By considering
the order of $A$ we see that $|N|=p$. Suppose that $N_{v}\neq 1$ for some
$v\in V(X)$ and $w$ is an another arbitrary vertex of $X$. Since $X$ is
transitive, there exists $\alpha\in{\rm Aut}(X)$ such that $w^{\alpha}=v$ and
so $N_{v}=N_{w^{\alpha}}=\alpha^{-1}N_{w}\alpha=N_{w}$. Thus $N$ is trivial, a
contradiction. Therefore $N$ acts semiregularly on $V(X)$ and so $X$ is an
$N$-regular cover of $X_{N}$. By [26, Page 173] we know that $X_{N}$ is a
Cayley graph. Thus ${\rm Aut}(X_{N})$ has a subgroup which acts regularly on
$V(X)$, say $G$. Suppose that $\tilde{G}$ is a lift of $G$. Now it is easy to
see that $\tilde{G}$ acts regularly on $V(X)$ and so $X$ is a Cayley graph, a
contradiction.

Case II. $A$ is not solvable.

Let $L={\rm Sol}(A)$ be the solvable radical of $A$ and $\Omega$ be the set of
orbits of $L$ on $V(X)$. First suppose that $L$ is not trivial. Let $K$ be the
kernel of $A$ on $\Omega$. Since $K_{v}$ is a $\\{2,3\\}$-group it implies
that $K_{v}$ is solvable and so by considering $K=LK_{v}$ we see that $K$ is
solvable. Now by the definition of $L$ we conclude that $K=L$ and $A/L\leq{\rm
Aut}(X_{L})$. If ${\rm deg}(X_{L})=0$ then $A/L$ is solvable and so $A$ is
solvable, a contradiction. Also if ${\rm deg}(X_{L})=2$ then ${\rm
Aut}(X_{L})\cong D_{2n}$, where $|V(X_{L})|=n$ and $n\in\\{3,6,p,2p,3p\\}$.
Now $A/L$ is solvable and so $A$ is solvable, a contradiction. Thus we may
suppose that ${\rm deg}(X_{L})=3$ or $4$. If ${\rm deg}(X_{L})=3$ then
$n\in\\{6,2p,3p\\}$. By [16, Theorem 1.1], we see that ${\rm Aut}(X_{L})$ is
solvable and so $A/L$ is solvable. Now $A$ is solvable, a contradiction. Also
if ${\rm deg}(X_{L})=4$ then $L=K$ and $K$ acts faithfully on each orbits of
$K$. Moreover, in this case $n\in\\{6,p,2p,3p\\}$. If $n=6$, then $X_{L}$ is
isomorphic to the octahedral graph and so $|{\rm Aut}(X_{L})|=48$. Thus ${\rm
Aut}(X_{L})$ is solvable which implies that $A$ is solvable, a contradiction.
If $n=p$ then by $|V(X)|=|L|n$ we see that $|L|=6$ and $L\cong S_{3}$ or
$\mathbb{Z}_{6}$. Also since $A_{v}$ is a $\\{2,3\\}$-group, it implies that
$A$ has a semiregular element of order $p$, say $\alpha$. If $L$ as subgroup
of $S_{6}$ is isomorphic to $S_{3}$ then since $L$ is semiregular we conclude
that $S_{3}\times\langle\alpha\rangle$ acts regularly on $V(X)$, a
contradiction. Similarly if $L$ as subgroup of $S_{6}$ is isomorphic to
$\mathbb{Z}_{6}=\langle\beta\rangle$ then
$\langle\alpha\rangle\times\langle\beta\rangle$ acts regularly on $V(X)$, a
contradiction. Also if $|V(X_{L})|=2p$ then $|L|=3$. Since $A_{v}$ is
$\\{2,3\\}$-group we conclude that $A$ has a semiregular element, say
$\alpha$, of order $p$, . Since $N_{A}(L)/C_{A}(L)$ is a subgroup of ${\rm
Aut}(L)$ we conclude that $\alpha\in C_{A}(L)$. Also if $\beta\in L$ and
$\beta$ has order $3$ then $\langle\alpha,\beta\rangle$ is a semiregular
subgroup of ${\rm Aut}(X)$ which is isomorphic to $\mathbb{Z}_{3p}$. Thus $X$
is a bi-Cayley graph over $H$, where $H\cong\mathbb{Z}_{3p}$. By Proposition
1, $X=X_{3,p,t}$, where $1\leq t\leq p-1$ and $t^{2}\equiv-1\pmod{p}$. Finally
if $|V(X_{L})|=3p$ then $|L|=2$. By Proposition 6, $X_{N}$ is a Cayley graph,
unless the case where $X_{N}$ is isomorphic to the line graph of the Petersen
graph. Since $p\geq 11$, it follows that $X_{N}$ is not isomorphic to the line
graph of the Petersen graph. Also if $X_{N}$ is a Cayley graph then ${\rm
Aut}(X_{N})$ has a subgroup say $H$ which acts regularly on $V(X_{N})$. Thus
$|H|=3p$ and by [21, Proposition 1.2], $X_{N}$ is a $(3,p)$-metacirculant
graph. Thus $X_{N}$ has an automorphism $\sigma$ of order $p$ such that
$\langle\sigma\rangle$ is semiregular on the vertex set of $X_{N}$, and an
automorphism $\tau$ normalizing $\langle\sigma\rangle$ and cyclically
permuting the $3$ orbits of $\langle\sigma\rangle$ such that $\tau$ has a
cycle of size $3$ in its cycle decomposition. Thus
$\langle\sigma,\tau^{i}\rangle$ for some positive integer $i$, has order $3p$
and acts regularly on $V(X_{N})$. Therefore we may suppose that $X_{N}={\rm
Cay}(H,S)$. First suppose that $H=\langle\sigma,\tau^{i}\rangle\cong F_{3p}$.
If $X_{N}$ is normal then ${\rm Aut}(X_{N})_{1}={\rm Aut}(H,S)$. Since ${\rm
Aut}(H,S)$ acts faithfully on $S$ we conclude that ${\rm Aut}(X_{N})_{1}\leq
S_{4}$. Also since $X_{N}$ is connected we conclude that
$S=\\{x,x^{-1},y,y^{-1}\\}$ and $x$ and $y$ have not the same orders. Now it
is easy to see that ${\rm Aut}(H,S)$ has no any element of order $3$ or $4$.
Thus by considering the subgroups of $S_{4}$ we see that ${\rm
Aut}(X_{N})_{1}=1$ or $\mathbb{Z}_{2}$ or
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. Therefore $|{\rm Aut}(X_{N})|\leq 12p$
and so $|A/K|$ divides $12p$. Now by considering the order of ${\rm
Aut}(X_{N})$ we see that $H\leq A/K$ and so $H=T/K$ for some $T\leq A$. Now
$|T|=6p$ and $T$ acts regularly on $V(X)$, a contradiction. Thus we may
suppose that $X_{N}$ is not normal. If $X_{N}$ is not primitive then by [17,
Theorem 3.1] we see that the valency of $X_{N}$ is not equal to $4$. Also if
$X_{N}$ is primitive then again by [34, Lemma 2.1] we have a contradiction.
Therefore $X_{N}$ is a Cayley graph on $\mathbb{Z}_{3p}$. Now similar to the
case where $A$ is solvable, we conclude that $X$ is a Cayley graph, a
contradiction.

Suppose that $L$ is trivial. By considering the order of $A$, we see that $N$
is a $K_{3}$-group. Since $p\geq 11$, it follows that $N\cong{\rm
PSL}_{2}(17)$ or ${\rm PSL}_{3}(3)$. If $N$ has more than two orbits then
$n\in\\{3,6,2p,3p\\}$. First assume that $n=2p$ or $3p$. We know that $A/K$
acts transitively on $V(X_{N})$ and $K=K_{\alpha}N$, where $v\in V(X)$. Thus
$p^{2}$ divides $|A|$, a contradiction. Thus we may suppose that $n=3$ or $6$.
By using GAP [10], it is easy to see that ${\rm PSL}_{2}(17)$ and ${\rm
PSL}_{3}(3)$ does not have any orbit of order $p$ or $2p$, where
$p\in\\{13,17\\}$. Therefore $N$ has at most two orbits. Now ${\rm
Aut}(X_{N})$ is solvable and so $A/K$ is solvable. Also since $K_{v}$ is
$\\{2,3\\}$-group and $K=K_{v}N$, it follows that $K/N$ is solvable. Since
$A/K\cong(A/N)/(K/N)$ we conclude that $A/N$ is also solvable. Suppose that
$M$ is another minimal normal subgroup of $A$. Thus by the fact that
$MN/N\cong M/(M\cap N)\leq A/N$ we see that $M/(M\cap N)$ is solvable. But
$M\cap N=1$ and so $M$ is solvable, a contradiction. Hence $N$ is the only
minimal normal subgroup of $A$. Since $|A|$ is not divisible by $p^{2}$ we
conclude that $N$ is a simple group. Therefore $A$ is an almost simple group
and ${\rm soc}(A)=N$. Since $A$ is $\\{2,3,p\\}$-group, it follows that $N$ is
a $K_{3}$-group. Also since $p\geq 11$ we conclude that $N\cong{\rm
PSL}_{2}(17)$ or $N\cong{\rm PSL}_{3}(3)$.

First assume that $N\cong{\rm PSL}_{2}(17)$. Then $A\cong{\rm PSL}_{2}(17)$ or
${\rm PGL}_{2}(17)$. If $A\cong{\rm PSL}_{2}(17)$ then $|A:A_{v}|=102$. By
[7], we see that $A$ has two subgroups of index $102$ and both of them have an
element of order $4$. Also we see that $A_{v}$ acts transitively on the set of
vertices adjacent to $v$. By Proposition 3, $X$ is a symmetric graph. If $X$
is one-regular then $|A|=2^{3}.3.17$, a contradiction. By [2, Theorem 1], we
see that $X\cong C_{3p}[2K_{1}]$ and so $X$ is a Cayley graph, a
contradiction. Also if $A\cong{\rm PGL}_{2}(17)$ then by using GAP [10], $A$
has no any subgroup of index $102$, a contradiction.

Assume that $N\cong{\rm PSL}_{3}(3)$. Then $A\cong{\rm PSL}_{3}(3)$ or $A={\rm
Aut}({\rm PSL}_{3}(3))$. Let $A={\rm Aut}({\rm PSL}_{3}(3))$. Since $A\leq
S_{78}$ is a transitive permutation group of degree $78$, there exists a core-
free subgroup $H$ of $A$ of index $78$ such that $A$ is isomorphic to the
permutation representation of the action of $A$ on the right cosets of $H$ in
$G$ by right multiplication. One can check, by using GAP [10], that in this
case $A$ has a regular subgroup of order $78$ which means that $X$ is a Cayley
graph, a contradiction. Hence $A={\rm PSL}_{3}(3)$ and $X={\rm Cos}({\rm
PSL}_{3}(3),H,D)$, is a coset graph, where
$H\cong(\mathbb{Z}_{3}\times\mathbb{Z}_{3})\rtimes Q_{8}$ and $D$ is a union
of double cosets of $H$ in $G$. Since $X$ is $4$-valent, we have $|D|/|H|=4$.
By using GAP [10], there are $15$ possibilities for $D$ and in each case
$\langle D\rangle$ is a proper subgroup of ${\rm PSL}_{3}(3)$ which means that
$X$ is disconnected, a contradiction. This complete the proof.

## References

  * [1] M. Arezoomand, M. Ghasemi, Normality of one-matching semi-Cayley graphs over finite abelian groups with maximum degree three, _Contrib. Discrete. Math._ 15(3) (2020) 75–87.
  * [2] K. Berčič, M. Ghasemi, Tetravalent arc-transitive graphs of order twice a product of two primes, _Discrete Math._ 312 (2012) 3643–3648.
  * [3] Y.G. Baik, Y.-Q. Feng, H.S. Sim, M.Y. Xu, On the normality of Cayley graphs of abelian groups, _Algebra Colloq._ 5 (1998) 297–304.
  * [4] N.L. Biggs, Algebraic Graph Theory, 2nd edn., Cambridge Mathematica Library, Cambridge University Press, Camberidge, 1986.
  * [5] H.W. Cheng, M. Ghasemi, S. Qiao, Tetravalent vertex-transitive graphs of order twice a prime square, _Graph. Combin._ 32 (2016) 1763–1771.
  * [6] Y. Cheng, J. Oxley, On weakly symmetric graphs of order twice a prime, _J. Combin. Theory B_ 42 (1987) 196–211.
  * [7] J.H. Conway, R.T. Curties, S.P. Norton, R.A. Parker, R.A. Wilson, _Atlas of Finite Groups_ , Clarendon Press, Oxford, 1985.
  * [8] Y.-Q. Feng, On vertex-transitive graphs of odd prime-power order, _Discrete Math._ 248 (2002) 265–269.
  * [9] R. Frucht, J. E. Graver, M.E. Watkins, The groups of the generalized Petersen graphs, _Math. Proc. Camb. Phil. Soc._ 70 (1971) 211–218.
  * [10] GAP Team, Group, GAP-Groups, Algorithms, and Programming, Version 4.5.5, 2012, http://www.gapsystem.org.
  * [11] D. Gorenstein, _Finite simple groups_ Plenum Press, New York, 1982.
  * [12] A. Hassani, M. A. Iranmanesh, C. E. Praeger, On vertex-imprimitive graphs of order a product of three distinct odd primes, _J. Combin. Math. Combin. Comput._ 28 (1998) 187–213.
  * [13] D. Holt, G. Royle, G. Tracey, The transitive groups of degree 48 and some applications, _accepted to J. Algebra_
  * [14] M.A. Iranmanesh, C.E. Praeger, On non-Cayley vertex-transitive graphs of order a product of three primes, _J. Combin. Theory B_ 81 (2001) 1–19.
  * [15] C.H. Li, A. Seress, On vertex-transitive non-Cayley graphs of square-free order, _Designs, Codes and Cryptography._ 34 (2005) 265–281.
  * [16] C.H. Li, Z.P. Lu, G.X. Wang, Vertex-transitive cubic graphs of square-free order, _J. Graph Theory._ 75 (2014) 1–19.
  * [17] Z.P. Lu, M.Y. Xu, On the normality of Cayley graphs of order $pq$, _Austral. J. Combin._ 27 (2003) 81–93.
  * [18] D. Marušič, On vertex symmetric digraphs, _Discrete Math._ 36 (1981) 69–81.
  * [19] D. Marušič, Cayley properties of vertex symmetric graphs, _Ars Combin._ 16B (1983) 297–302.
  * [20] D. Marušič, Vertex transitive graphs and digraphs of order $p^{k}$, _Ann. Discrete Math._ 27 (1985) 115–128.
  * [21] D. Marušič, R. Scapellato, Characterizing vertex-transitive $pq$-graphs with an imprimitive automorphism subgroup, _J. Graph Theory._ 16 (1992) 375–387.
  * [22] D. Marušič, R. Scapellato, Classifying vertex-transitive graphs whose order is a product of two primes, _Combinatorica._ 14 (1994) 187–201.
  * [23] D. Marušič, R. Scapellato, B. Zgrablič, On quasiprimitive $pqr$-graphs, _Algebra Colloq._ 2 (1995) 295–314.
  * [24] B.D. McKay, C.E. Praeger, Vertex-transitive graphs which are not Cayley graphs I, _J. Austral. Math. Soc._ 56 (1994) 53–63.
  * [25] B.D. McKay, C.E. Praeger, Vertex-transitive graphs which are not Cayley graphs II, _J. Graph Theory_ 22 (1996) 321–334.
  * [26] B.D. McKay, G. F. Royle, The Transitive Graphs with at Most 26 Vertices. _Ars Combin._ 30 (1990) 161–176.
  * [27] A.A. Miller, C.E. Praeger, Non-Cayley vertex-transitive graphs of order twice the product of two odd primes, _J. Algebraic Combin._ 3 (1994) 77–111.
  * [28] Private communication with Holt and Royle.
  * [29] S. Qiao, J. X. Zhou, On tetravalent vertex-transitive bicirculants, Indian J. Pure Appl. Math. 51(1) (2020) 277-288.
  * [30] A. Seress, On vertex-transitive non-Cayley graphs of order $pqr$, _Discrete Math._ 182 (1998) 279–292.
  * [31] B.O. Sabidussi, Vertex-transitive graphs, Monash Math. 68 (1964) 426–438.
  * [32] G. Sabidussi, On a class of fix-point-free graphs, _Proc. Amer. Math. Soc._ 9 (1958) 800–804.
  * [33] N.D. Tan, Cubic $(m,n)$-metacirculant graphs Cayley graphs which are not Cayley graphs, _Discrete Math._ 154 (1996) 237–244.
  * [34] R.J. Wang, M.Y. Xu, A classification of symmetric graphs of order $3p$, _J. Combin. Theory B_ 58 (1993) 197–216.
  * [35] H. Wielandt, Finite Permutation Groups, Acadamic Press, New York 1964.
  * [36] M.Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, _Discrete Math._ 82 (1998) 309–319.
  * [37] J.-X. Zhou, Tetravalent vertex-transitive graphs of order $4p$, _J. Graph Theory_ 71 (2012) 402–415.
  * [38] J.-X. Zhou, Cubic vertex-transitive graphs of order $4p$ (Chinese), _J. Sys. Sci. Math. Sci._ 28 (2008) 1245–1249.
  * [39] J.-X. Zhou, Cubic vertex-transitive graphs of order $2p^{2}$ (Chinese), _Advance in Math._ 37 (2008) 605–609.
  * [40] J.-X. Zhou, Y.-Q. Feng, Cubic vertex-transitive graphs of order $2pq$, _J. Graph Theory_ 65 (2010) 285–302.

M. Arezoomand
University of Larestan, 74317-16137, Larestan, I. R. Iran
Email<EMAIL_ADDRESS>

M. Ghasemi
Department of Mathematics,
Urmia University, 57135, Urmia, I. R. Iran
Email<EMAIL_ADDRESS>

Mohammad A. Iranmanesh
Department of Mathematics,
Yazd University, 89195-741, Yazd, I. R. Iran
Email<EMAIL_ADDRESS>