\documentclass[12pt]{amsart}

\topmargin=-0.4in \oddsidemargin=0.2in \evensidemargin=0.2in
\textwidth=6.2in \textheight=9.2in
%\documentclass[10pt, reqno]{amsart}%[11pt]{article}

%\usepackage{showkeys}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage[usenames]{color}
\usepackage{graphics}
%\include{PDF}

\renewcommand{\proof}{\par\noindent{\it Proof.\ \ }}
\def\qed{\ifmmode\square\else\nolinebreak\hfill
$\square$\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|\,}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}%
\newtheorem{corollary}[theorem]{Corollary}%
\newtheorem{proposition}[theorem]{Proposition}%
\newtheorem{definition}[theorem]{Definition}%
\newtheorem{problem}[theorem]{Problem}%
\newtheorem{example}[theorem]{Example}%
\newtheorem{construction}[theorem]{Construction}%
\newtheorem{conjecture}[theorem]{Conjecture}%
\newtheorem{question}[theorem]{Question}%
\newtheorem{notation}[theorem]{Notation}%

\newcommand{\ld}{,\ldots ,}
\newcommand{\nni}{\not\in }
\newcommand{\se}{ \subseteq }
\newcommand{\lan}{ \langle }
\newcommand{\ran}{ \rangle }

\newcommand{\CC}{\mathop{\bf C}\nolimits}
\newcommand{\FF}{\mathop{\bf F}\nolimits}
\newcommand{\GG}{\mathop{\bf G}\nolimits}
\newcommand{\Hom}{\mathop{\rm Hom}\nolimits}
\newcommand{\NN}{\mathop{\bf N}\nolimits}
\newcommand{\QQ}{\mathop{\bf Q}\nolimits}
\newcommand{\RR}{\mathop{\bf R}\nolimits}
%\newcommand{\ZZ}{\mathop{\bf Z}\nolimits}
\newcommand{\rank}{\mathop{\rm rank}\nolimits}

\def\ZZ{{\mathbb Z}}

\def\calB{{\mathcal B}}
\def\calC{{\mathcal C}}

\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\ga}{\gamma}
\newcommand{\de}{\delta}
\newcommand{\ep}{\varepsilon}
\newcommand{\eps}{{\varepsilon}}
\newcommand{\lam}{\lambda }

\newcommand{\dij}{_{ij}}
\newcommand{\dkl}{_{kl}}
\newcommand{\dst}{_{st}}
\newcommand{\dnn}{_{nn}}
\newcommand{\dmn}{_{mn}}
\newcommand{\dmm}{_{mm}}
\newcommand{\up}{^{-1}}

\newcommand{\iin}{$(i=1,\ldots ,n)$}

\newcommand{\sig}{\sigma }

\newcommand{\Om}{\Omega }

\def\l{\langle} \def\r{\rangle}

%%%% Roman Math %%%%%
\def\L{{\rm L}}
\def\U{{\rm U}}
\def\PSL{{\rm PSL}}%\nolimits}
\def\SL{{\rm SL}}%\nolimits}
\def\SO{{\rm SO}}%\nolimits}
\def\PSO{{\rm PSO}}%\nolimits}
\def\Spin{{\rm Spin}}%\nolimits}
\def\PSU{{\rm PSU}}%\nolimits}
\def\SU{{\rm SU}}%\nolimits}
\def\PSp{{\rm PSp}}%\nolimits}
\def\PGU{{\rm PGU}}%\nolimits}
\def\GU{{\rm GU}}%\nolimits}
\def\GL{{\rm GL}}%\nolimits}
\def\PGL{{\rm PGL}}%\nolimits}
\def\Cl{{\rm Cl}}%\nolimits}
\def\Sp{{\rm Sp}}%\nolimits}
\def\A{{\rm A}}%\nolimits}
\def\FGL{{\rm FGL}}%\nolimits}
\def\FSL{{\rm FSL}}%\nolimits}
\def\J{{\rm J}}
\def\M{{\rm M}}
\def\Suz{{\rm Suz}}
\def\E{{\rm E}}
\def\F{{\rm F}}
\def\G{{\rm G}}
\def\Sz{{\rm Sz}}
\def\AGL{{\rm AGL}}
\def\AGammaL{{\rm A\Gamma L}}

\def\Ru{{\rm Ru}}

\def\POmega{{\rm P\Omega}}
\def\PSigmaL{{\rm P\Sigma L}}

\def\PGammaL{{\rm P\Gamma L}}

\def\Sz{{\rm Sz}}
\def\Ree{{\rm Ree}}

\def\K{{\bf K}}
\def\Z{{\bf Z}}

%\def\A{{\rm A}}%\nolimits}
\def\B{{\rm B}}%\nolimits}

\def\C{{\rm C}}%\nolimits}

\def\D{{\rm D}}%\nolimits}
\def\E{{\rm E}}%\nolimits}
\def\F{{\rm F}}%\nolimits}
\def\G{{\rm G}}%\nolimits}
%\def\O{{\rm O}}%\nolimits}
\def\U{{\rm U}}%\nolimits}
\def\Sym{{\rm Sym}}
\def\Alt{{\rm Alt}}
\def\Aut{{\rm Aut}}
\def\Out{{\rm Out}}
\def\CSym{{\rm CSym}}
\def\Char{{\rm char}}
\def\Inn{{\rm Inn}}

\def\Cay{{\sf Cay}}
\def\BCay{{\sf BCay}}

\def\Aut{{\sf Aut}}
\def\Cos{{\sf Cos}}

\def\char{{\sf \,char\,}}
\def\soc{{\sf soc}}

\def\FIF{\mathrm{FIF}}

\def\KG{{\bf KG}}
%------------------------------------

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

\def\N{{\bf N}}
\def\C{{\bf C}}
\def\S{{\rm S}}
\def\A{{\rm A}}
\def\rmO{{\rm O}}
\def\rmQ{{\rm Q}}
\def\O{{\rm O}}

\def\J{{\bf J}}
\def\K{{\bf K}}

\def\a{\alpha}
\def\b{\beta}
\def\g{\gamma}
\def\s{\sigma}
\def\t{\tau}

\def\ov{\overline}
\def\mod{{\sf mod\ }}



\begin{document}

\title{A family of half-transitive graphs}
\thanks{This work was partially supported by an ARC Discovery Project Grant, NNSF of China(No. 11171292,
11271208) and  Hunan First Normal University(No. XYS12N12).}

\author[Chen]{Jing Chen}
\address{Department of Mathematics\\
Hunan First Normal University\\
Changsha, Hunan, 410205\\
P. R. China}
\curraddr{} \email{chenjing827@126.com}

\author[Li]{Cai Heng Li}
\address{School of Mathematics and Statistics\\
Yunnan University \\
Kunming, P. R. China}
\address{Center for the Mathematics of Symmetry and Computation\\
School of Mathematics and Statistics\\
The University of Western Australia\\
Crawley 6009 WA, Australia}
\email{cai.heng.li@uwa.edu.au}

\author[Seress]{\'Akos Seress}
\address{The Ohio State University \\
Columbus, OH 43210, USA}
\address{School of Mathematics and Statistics\\
The University of Western Australia\\
Crawley, WA 6009, Australia}
\email{akos@math.ohio-state.edu}


\maketitle

\begin{abstract}
We construct an infinite family of half-transitive graphs, which contains
infinitely many Cayley graphs, and infinitely many non-Cayley graphs.
\end{abstract}


\section{Introduction}

Let $\Ga=(V,E)$ be a graph with vertex set $V$ and edge set $E$. A
permutation of $V$ which preserves the adjacency of $\Ga$ is an
automorphism of the graph, and all automorphisms form the
automorphism group $\Aut\Ga$. If a subgroup $G\le\Aut\Ga$ is
transitive on $V$ or $E$, then $\Ga$ is called {\it
$G$-vertex-transitive} or {\it $G$-edge-transitive}, respectively.
An ordered pair of adjacent vertices is called an {\it arc}, and
$\Ga$ is called {\it arc-transitive} if $\Aut\Ga$ is transitive on
the set of arcs. An arc-transitive graph is vertex-transitive and
edge-transitive, but the converse statement is not true. A graph
which is vertex-transitive and edge-transitive but not
arc-transitive is called {\it half-transitive}.

The study of half-transitive graphs was initiated with a question of
Tutte \cite[p.\,60]{Tutte} regarding their existence, and he proved
that a vertex-transitive and edge-transitive graph with odd valency
must be arc-transitive. Bouwer \cite{Bouwer} in 1970 constructed the
first family of half-transitive graphs. Since then, constructing and
characterizing half-transitive graphs has been an active topic in
algebraic graph theory, refer to \cite{AMN,A-Xu,Li-Sim,MP,Sajna,Xu}
and a survey \cite{Marusic} for the work during 1990's, and
\cite{M-Sparl,Sajna,Song,Sparl-08,Sparl} for more recent work.

In this paper, we present an infinite family of half-transitive
graphs. These graphs were originated from {\it Johnson graphs}
$\J(n,i)$ where $i=1$, 2 or 3, the vertex set of which consists of
the $i$-element subsets of an $n$-element set such that two vertices
are adjacent when they meet in $(i-1)$-elements.
It is known that the automorphism group of $\J(n,i)$ is $\S_{n}$, see \cite{Jones} or  \cite[Theorem 1]{mark-Johnson}.

As usual, we denote by $[n]$ the set $\{1,2,3,\ldots,n\}$.
Let
\[V_n=\{\{\{i,j\},k\}\mid i,j,k\in [n]\}.\]
For convenience, we simply write the vertex $\{\{i,j\},k\}$ as $(ij,k)$.
Then $(ij,k)=(ji,k)$, and a 3-subset $\{i,j,k\}$ corresponds to exactly
three vertices $(ij,k)$, $(ik,j)$ and $(jk,i)$.
Thus, the cardinality is
\[|V_n|=3{n\choose3}=n(n-1)(n-2)/2.\]

\begin{definition}\label{def-Gamma}
{\rm
For an integer $n>3$, let $\Ga_n$ be the graph with vertex set $V_n$
such that two vertices $(ij,k)$ and $(i'j',k')\in V_n$ are adjacent
if and only if
\[\mbox{$\{i,j\}=\{i',k'\}$ or $\{j',k'\}$}\]
} and $\{i,j,k\}\neq\{i',j',k'\}$.
\end{definition}

The graph $\Ga_n$ is regular and has valency $4(n-3)$.
For example, the vertex $(12,3)$ has neighborhood
\[\{(1i,2),(2i,1),(13,i),(23,i) \mid i>3\},\]
which has size $4(n-3)$.

Let $\Ga=(V,E)$ be a graph, and let $\calB$ be a partition of the vertex set $V$.
Then the {\it quotient graph} $\Ga_\calB$ induced on $\calB$ is the graph
with vertex set $\calB$ such that $B,B'$ are adjacent if and only if
there is an edge which lies between $B$ and $B'$.
In this case, $\Ga$ is also said to be {\it homomorphic} to $\Ga_\calB$.

A graph $\Ga=(V,E)$ is called a {\it Cayley graph} if there is a
group $R$ and a self-inversed subset $S\subset R$ such that $V=R$
and $u,v\in S$ are adjacent if and only if $vu^{-1}\in S$. Cayley
graphs are vertex-transitive, but a vertex-transitive graph is not
necessarily a Cayley graph. For example, the Petersen graph is the
smallest vertex-transitive graph which is not a Cayley graph. The
family of graphs $\Ga_n$ contains infinitely many non-Cayley graphs.

\begin{theorem}\label{main-thm}
Let $\Ga_n$ be a graph defined above.
Then the following statements hold:
\begin{itemize}
\item[(i)] $\Ga_n$ is of order ${n(n-1)(n-2)\over2}$, valency $4(n-3)$, girth $3$,
and  diameter $3$;

\item[(ii)] $\Ga_n$ is homomorphic to $\K_n$, $\J(n,2)$ and $\J(n,3)$;

\item[(iii)] $\Ga_4$ and $\Ga_5$ are arc-transitive, and for $n\ge6$,  $\Aut\Ga_n=\Sym([n])$, and $\Ga_n$ is half-transitive;

\item[(iv)] $\Ga_n$ is a Cayley graph if and only if $n=8$, or $n=q+1$
with $q$ a prime-power, and $q\equiv 3$ $(\mod 4)$.
\end{itemize}
\end{theorem}


\section{Edge-transitivity}

Let $\s\in\Sym([n])$.
For convenience, we simply denote $V_n$ by $V$, and denote $\Ga_n$ by $\Ga$.
Then $\s$ induces a permutation on the vertex set $V$.
Since $G=\Sym([n])$ is 3-transitive on $[n]$, $G$ is transitive on $V$.

Take an edge $\{(i_1j_1,k_1), (i_2j_2,k_2)\}$ of $\Ga$.
Then $\{i_1,j_1\}=\{i_2,k_2\}$ or $\{j_2,k_2\}$, and hence
$\{i_1^\s,j_1^\s\}=\{i_2^\s,k_2^\s\}$ or $\{j_2^\s,k_2^\s\}$.
Thus, $(i_1^\s j_1^\s,k_1^\s)$ and $(i_2^\s j_2^\s,k_2^\s)$ are adjacent,
that is, $\s$ maps edges to edges.
Similarly, $\s$ maps non-edges to non-edges.
So $\s$ is an automorphism of $\Ga$, and $G=\Sym([n])$ is a vertex-transitive automorphism group of $\Ga$.

\begin{lemma}\label{vt}
The graph $\Ga=\Ga_n$ is $G$-vertex-transitive and $G$-edge-transitive,
but not $G$-arc-transitive.
\end{lemma}
\proof We consider the edges incident with the vertex $\a=(12,3)$.
The stabilizer
$G_\a=\Sym(\{1,2\})\times\Sym(\{4,5,\dots,n\})\cong\S_2\times\S_{n-3}$,
and $G_\a$ acting on the neighborhood $\Ga(\a)$ has two orbits
$\{(1i,2),(2i,1)\mid i>3\}$ and $\{(13,i),(23,i)\mid i>3\}$. Thus,
$G$ is not transitive on the arcs of $\Ga$. Further, the element
$g=(23i)$ maps $(1i,2)$ to $(12,3)$, and $(12,3)$ to $(13,i)$, so
$g$ maps the edge $\{(1i,2),(12,3)\}$ to the edge
$\{(12,3),(13,i)\}$. Since $\Ga$ is $G$-vertex-transitive, we
conclude that $\Ga$ is $G$-edge-transitive. \qed

Let $H$ be a  subgroup of $G$, and $S$ be a subset of $G$. Define
the {\it coset graph} of $G$ with respect to $H$ and $S$ to be the
directed graph with vertex set $[G:H]$ and such that, for any $Hx$,
$Hy\in V$, $Hx$ is connected to $Hy$ if and only if $yx^{-1}\in HSH$
and denote the digraph by $Cos(G,H,HSH)$.  With the vertex
$\a=(12,3)\in V_n$ and element $g=(234)\in G$, the graph $\Ga=\Ga_n$
can be described as a {\it coset graph}
$\Cos(G,G_\a,G_\a\{g,g^{-1}\}G_\a)$, which has vertex set
$[G:G_\a]=\{G_\a x\mid x\in G\}$ such that $G_\a x$ and $G_\a y$ are
adjacent if and only if $yx^{-1}\in G_\a\{g,g^{-1}\}G_\a$. The right
multiplication of each element $g\in G$
\[g:\ \ G_\a x\mapsto G_\a xg,\ \mbox{for all $x\in G$}\]
induces an automorphism of $\Ga$.

\begin{lemma}\label{arc-trans}
If an automorphism $\t\in\Aut(G)$ normalizes $G_\a$ and
$(G_\a\{g,g^{-1}\}G_\a)^\t=G_\a\{g,g^{-1}\}G_\a$, then $\t$ is an
automorphism of $\Ga$.
\end{lemma}
\proof
Since $\t$ normalizes $G_\a$, it induces a permutation on the vertex set $[G:G_\a]$.

For any two vertices $G_\a x$ and $G_\a y$, we have
\[\begin{array}{lll}
G_\a x\sim G_\a y &\Longleftrightarrow & yx^{-1}\in G_\a\{g,g^{-1}\}G_\a\\
 & \Longleftrightarrow & (yx^{-1})^\t\in(G_\a\{g,g^{-1}\}G_\a)^\t\\
 & \Longleftrightarrow & y^\t(x^\t)^{-1}\in G_\a\{g,g^{-1}\}G_\a\\
 & \Longleftrightarrow & (G_\a x)^\t=G_\a x^\t\sim G_\a y^\t=(G_\a y)^\t.
\end{array}\]
Thus, $\t$ is an automorphism of the graph $\Ga$. \qed

\begin{lemma}\label{n=4,5}
Both $\Ga_4$ and $\Ga_5$ are arc-transitive.
\end{lemma}
\proof
Let $\a=(12,3)$, and $g=(234)$.
Consider first the case $G=\S_4$.
Then $G_\a=\Sym(\{1,2\})$, and $\Ga=\Cos(G,G_\a,G_\a \{g,g^{-1}\}G_\a)$.
Let $\t$ be the inner-automorphism induced by the element $(34)\in G$.
Then $\t$ normalizes $G_\a$ and $g^\t=g^{-1}$.
By Lemma~\ref{arc-trans}, $\t$ is an automorphism of the graph.
Further, for the edge $\{G_\a,G_\a g\}$, we have
\[(G_\a,G_\a g)^{\t g}=(G_\a,G_\a g^{-1})^g=(G_\a g,G_\a),\]
and so $\Ga$ is arc-transitive.

Next, consider the case $G=\S_5$. Again let $\a=(12,3)$ and
$g=(234)$. Then $G_\a=\Sym(\{1,2\})\times\Sym(\{4,5\})$, and
$\Ga=\Cos(G,G_\a,G_\a \{g,g^{-1}\}G_\a)$. Let $\t$ be the
inner-automorphism of $G$ induced by the element $(15)(24)\in G$.
Then $\t$ normalizes $G_\a$ and reverses $g$. Arguing as above shows
that $\Ga$ is arc-transitive. \qed

However, we will show that $\Ga_n$ for $n\ge6$ are all half-transitive.



\section{The parameters}

Denote the graph $\Ga_n$ simply by $\Ga$ in the following.
For vertices $\a=(i_1j_1,k_1)$ and $\b=(i_2j_2,k_2)$, we denote
$\{i_1,j_1,k_1\}\cap\{i_2,j_2,k_2\}$ by $\a\cap\b$. Then
$|\a\cap\b|=2$ if $\a$ and $\b$ are adjacent.

\begin{lemma}\label{diam=3}
The graph $\Ga=\Ga_n$ is of order ${n(n-1)(n-2)\over2}$, valency $4(n-3)$,
girth $3$, and diameter $3$.
\end{lemma}
\proof As noticed above, each 3-subset $\{i,j,k\}$ corresponds to
exactly three vertices $(ij,k)$, $(jk,i)$ and $(ik,j)$. Thus, the
order $|V|$ of $\Ga$ equals $3{n\choose 3}={n(n-1)(n-2)\over2}$. By
the definition of the graph $\Ga$, the neighborhood   of the vertex
$\a=(ij,k)$ is $\Ga(\a)=\{(ik,m), (jk,m), (im,j), (jm,i)|m\neq
i,j,k\}$. Thus, $\Ga$ is of valency $4(n-3)$. Moreover, since
$(jk,m)$ and $(jm,i)$ are adjacent,  $\Ga$ is of girth 3.

We next compute the distance $d(\a,\b)$ between two vertices $\a$
and $\b$. As $\Ga$ is a vertex-transitive graph, we take
$\a=(12,3)$. We first consider a small case that $n=4$. Then
$|V|=12$, and the neighborhood $\Ga(\a)=\{(14,2), (24,1), (13,4),
(23,4)\}$. For other vertices except $(12,4)$, we have
\[\Ga(\a)\cap\Ga(\b)=\left\{
\begin{array}{ll}
\{(23,4)\}, & \mbox{if $\b=(13,2)$},\\

\{(13,4)\}, & \mbox{if $\b=(23,1)$},\\

\{(24,1)\}, & \mbox{if $\b=(14,3)$},\\

\{(14,2), (23,4)\},  & \mbox{if $\b=(34,1)$},\\

\{(14,2)\}, & \mbox{if $\b=(24,3)$},\\

\{(24,1),(13,4)\}, & \mbox{if $\b=(34,2)$},\\
\end{array}
\right.\] and so $d(\a,\b)=2$. For $\b=(12,4)$, $\Ga(\a)\cap\Ga(\b)=0$.
Furthermore, the sequence
\[\mbox{$\a=(12,3)$, $(14,2)$, $(24,3)$, $\b=(12,4)$}\]
is a path between $\a$ and $\b$ of length 3. Hence,  $d(\a,\b)=3$,
and thus, the graph $\Ga$ is of diameter 3.

Now we treat the cases where $n\geq5$. Take $\a=(12,3)$, and let
$\b=(ij,k)$.

\vskip0.08in \noindent{\bf Case 1.} Assume first that $i,j,k\geq 4$.
If a vertex $\g=(i'j',k')$ is adjacent to both $\a$ and $\b$, then
$|\g\cap \a|=2$ and $|\g\cap\b|=2$, which is not possible. Thus,
$d(\a,\b)$ is at least 3. On the other hand, the sequence
\[\mbox{$\a=(12,3)$, $(1i,2)$, $(ik,1)$, $\b=(ij,k)$}\]
is a path between $\a$ and $\b$ of length 3. Hence,  $d(\a,\b)=3$.

\vskip0.08in \noindent{\bf Case 2.} Next, consider the case where
$|\a\cap\b|=1$.

Suppose that $\b=(ij,3)$, where $i,j\ge4$.
Then the sequence $\a$, $(1i,2)$, $(i3,1)$, $\b$ is a path between $\a$ and $\b$,
and hence $d(\a,\b)\le 3$.
As mentioned above,
\[\Ga(\a)=\{(1i',2),(2i',1),(13,i'),(23,i') \mid i'>3\},\]
and similarly,
\[\Ga(\b)=\{(ij',j),(jj',i),(3i,j'),(3j,j')\mid j'\notin\{3,i,j\}\}.\]
Thus, $\Ga(\a)\cap\Ga(\b)=\emptyset$, and so $d(\a,\b)=3$.

Assume now that $k\neq 3$. Then $\b=(1i,k)$, $(2i,k)$, $(3i,k)$,
$(ij,1)$ or $(ij,2)$, where $i,j,k\geq 4$. In each of these cases,
$d(\a,\b)=2$ because
\[\Ga(\a)\cap\Ga(\b)=\left\{
\begin{array}{ll}
\{(1k,2),(13,i),(2i,1)\}, & \mbox{if $\b=(1i,k)$},\\

\{(2k,1),(23,i),(1i,2)\}, & \mbox{if $\b=(2i,k)$},\\

\{(31,i),(32,i)\}, & \mbox{if $\b=(3i,k)$},\\

\{(1i,2),(1j,2)\}, & \mbox{if $\b=(ij,1)$},\\

\{(2i,1),(2j,1)\}, & \mbox{if $\b=(ij,2)$}.\\
\end{array}
\right.\]

\vskip0.08in \noindent{\bf Case 3.} We then treat the case where
$|\a\cap\b|=2$.

Assume that $k=3$. Then $\b=(1i,3)$ or $(2i,3)$, where $i\geq 4$. If
$\b=(1i,3)$, then $\Ga(\a)\cap\Ga(\b)=\{(13,m), (2i,1)\mid 4\le m\le
n, m\not=i\}$, and thus $d(\a,\b)=2$. Similarly, if $\b=(2i,3)$,
there exists $n-3$ paths of length 2 between $\a$ and $\b$, and so
$d(\a,\b)=2$.

Suppose that $k\neq 3$.  Then $\b=(12,k)$, $(1i,2)$, $(2i,1)$,
$(13,k)$, $(23,k)$, $(3i,1)$, $(3i,2)$, where $i,k\ge4$. If
$\b=(12,k)$, then $\Ga(\a)\cap\Ga(\b)=\{(1m,2), (2m,1)\mid 4\le m\le
n, m\not=k\}$, and so $d(\a,\b)=2$. For these vertices $\b=(1i,2)$,
$(2i,1)$, $(13,k)$, or $(23,k)$, we have $\b\in\Ga(\a)$, and thus
$d(\a,\b)=1$. If $\b=(3i,1)$, $\Ga(\a)\cap\Ga(\b)=\{(13,m), (23,i),
(1i,2)|4\le m\le n,m\not=i\}$, and hence $d(\a,\b)=2$. Similarly, if
$\b=(3i,2)$, $\Ga(\a)\cap\Ga(\b)=\{(23,m), (13,i), (2i,1)|4\le m\le
n,m\not=i\}$, and so $d(\a,\b)=2$.

\vskip0.08in
\noindent{\bf Case 4.} Let $|\a\cap\b|=3$.
Then $\b=(23,1)$ or $(13,2)$.

For $\b=(23,1)$, we have $d(\a,\b)=2$ as $(13,m)$ is adjacent to
both $\a$ and  $\b$, and thus, there are exactly $n-3$ paths of
length 2 between $\a$ and $\b$, where $m\neq 1,2,3$. Similarly, if
$\b=(13,2)$, $d(\a,\b)=2$ because there exist exactly $n-3$ paths
$\a$, $(23,m)$, $\b$ of length 2 between $\a$ and $\b$, where $m\neq
1,2,3$.

Thus, $\Ga=\Ga_n$ is of diameter 3. \qed




\section{Quotients}

The action of $G=\Sym([n])$ on $V_n$ has three types of blocks as below
\[\begin{array}{l}
B_k=\{(ij,k)\mid i,j\in[n]\setminus\{k\}\},\ \mbox{size ${n-1\choose2}$},\\

B_{ij}=\{(ij,k)\mid k\in[n]\setminus\{i,j\}\},\ \mbox{size $n-2$},\\

B_{ijk}=\{(ij,k),(jk,i),(ki,j)\},\ \mbox{size 3}.
\end{array}\]
Let $\calB_1=B_k^G$, $\calB_2=B_{ij}^G$, and $\calB_3=B_{ijk}^G$.
Then $|\calB_1|=n$, $|\calB_2|={n\choose2}$, and $|\calB_3|={n\choose 3}$.

\begin{lemma}\label{partition}
If $n\ge7$, then $V=V_n$ has exactly three non-trivial $G$-invariant partitions:
$\calB_1$, $\calB_2$ and $\calB_3$.
\end{lemma}
\proof For the vertex $\b=(23,1)$, the stabilizer
$G_\b=\Sym(\{2,3\})\times\Sym([n]\setminus\{1,2,3\})$, and $G_\b$ is
contained in $G_{B_1}$, $G_{B_{23}}$ and $G_{B_{123}}$. Moreover,
these three subgroups are maximal in $G$ and are the only proper
subgroups of $G$ which properly contain $G_\b$. Thus, $\calB_1$,
$\calB_2$ and $\calB_3$ are the only block systems of $G$ acting on
$V_n$. \qed

By Lemma \ref{partition}, we have three block systems $\calB_i$ with $i=1$, 2 or 3,
and we have three quotient graph $\Ga_{\calB_i}$.
Clearly, the induced action of $G$ on $\calB_i$ is equivalent to the action of $G$
on $[n]^{\{i\}}$, where $i=1$, 2 or 3.
We thus identify $\calB_1$ with $[n]$, $\calB_2$ with $[n]^{\{2\}}$,
and $\calB_3$ with $[n]^{\{3\}}$.
The quotient graph $\Ga_{\calB_1}=\K_n=\J(n,1)$.
For $\Ga_{\calB_2}$, two vertices $B_{ij}$ and $B_{i'j'}$ are adjacent if and only if
$|\{i,j\}\cap\{i',j'\}|=1$, and so $\Ga_{\calB_1}=\J(n,2)$.
For $\Ga_{\calB_3}$, two vertices $B_{ijk}$ and $B_{i'j'k'}$ are adjacent
if and only if $|\{i,j,k\}\cap\{i',j',k'\}|=2$.
Thus, we have the following lemma.

\begin{lemma}\label{quotient}
The quotient graph $\Ga_{\calB_i}$ is the Johnson graph $\J(n,i)$,
where $i=1$, $2$ or $3$.
\end{lemma}

For a quotient graph $\Ga_\calB$, let $B,B'\in\calB$ be adjacent in
$\Ga_\calB$. The {\it induced subgraph} $[B\cup B']$ of $\Ga$ over
$B\cup B'$ is the graph with vertex set $B\cup B'$ and edge set
$E_0=\{\{u,v\}\in E\mid u,v\in B\cup B'\}$. Then $[B\cup B']$ is a
bipartite graph with biparts $B$ and $B'$; denoted by $[B,B']$. We
next determine the induced subgraph $[B,B']$ for the quotient graph
$\Ga_{\calB_i}$.

For a graph $\Sig=(V,E)$, the {\it vertex-edge incidence graph} is the bipartite graph
with biparts $V$ and $E$ such that two vertices $v\in V$ and $w\in E$ are adjacent
if and only if $v,w$ are incident in $\Sig$.
This incidence graph is also called the {\it subdivision} of $\Sig$.

\begin{lemma}\label{B-B'-1}
Let $B,B'\in\calB_1$ be adjacent in $\Ga_{\calB_1}$. Then the
induced subgraph $[B,B']$ consists of $2$ copies of the subdivision
of $\K_{n-2}$.
\end{lemma}
\proof
Since $(23,1)\in B_1$ is adjacent to $(34,2)\in B_2$, the vertices
$B_1$ and $B_2$ are adjacent in the quotient $\Ga_{\calB_1}$.
The edges of the induced subgraph $[B_1,B_2]$ are
\[\{\{(2i,1),(ij,2)\}\mid 3\le i\le n,\ j\not=i,1,2\}\cup
\{\{(1i,2),(ij,1)\}\mid 3\le i\le n,\ j\not=i,1,2\},\] which form
two copies of the subdivision of $\K_{n-2}$. \qed

A {\it star} $\K_{1,m}$ is a bipartite graph with $m+1$ vertices,
in which there is one vertex that is adjacent to all other $m$ vertices.
In particular, $\K_{1,2}$ is a path of length 2.

\begin{lemma}\label{B-B'-2}
Let $B,B'\in\calB_2$ be adjacent in $\Ga_{\calB_2}$.
Then the induced subgraph $[B,B']$ consists of $2$ copies of the star $\K_{1,n-3}$.
\end{lemma}
\proof Since $(12,3)\in B_{12}$ is adjacent to $(23,4)\in B_{23}$,
the vertices $B_{12}$ and $B_{23}$ are adjacent in the quotient
$\Ga_{\calB_2}$. The edges of the induced subgraph $[B_{12},B_{23}]$
are $\{\{(12,3),(23,i)\}\mid i\ge4\}\cup\{\{(23,1),(12,j)\}\mid
j\ge4\}$, which form two stars $\K_{1,n-3}$. \qed


\begin{lemma}\label{B-B'-3}
Let $B,B'\in\calB_3$ be adjacent in $\Ga_{\calB_3}$.
Then the induced subgraph $[B,B']$ consists of $2$ paths of length $2$.
\end{lemma}
\proof For the blocks $B=\{(12,3),(23,1),(31,2)\}$ and
$B'=\{(12,4),(24,1),(41,2)\}$, the induced subgraph $[B,B']$ has 4
edges
\[\mbox{$\{(12,3),(14,2)\}$, $\{(12,3),(24,1)\}$,
$\{(12,4),(13,2)\}$, $\{(12,4),(32,1)\}$.} \] These edges form two
paths of length 2:
\[(23,1),(12,4),(13,2),\ \ \mbox{and}\ (24,1),(12,3),(14,2).\]
Thus, $[B,B']=2\K_{1,2}$.
\qed



\section{The automorphism group}

In this section, we determine the automorphism group $\Aut\Ga$.

\begin{lemma}\label{al-simple}
Let $n\ge7$, and let $X$ be a subgroup such that $G\leq X\leq \Aut\Ga$.
Then $X$ is almost simple, and if $X\not=G$, then $X$ is primitive on $V$.
\end{lemma}
\proof
Let $M$ be a minimal normal subgroup of $X$.
Suppose that $M$ is intransitive on $V$.
Let $\calB$ be the set of $M$-orbits on $V$.
Then $\calB$ is $X$-invariant and $G$-invariant.
By Lemma~\ref{partition}, $\calB=\calB_i$ with $i=1$, 2 or 3.
For $B_i\in\calB_i$, we have that $G_{B_1}^{B_1}=\S_{n-1}$,
$G_{B_2}^{B_2}=\S_{n-2}$, and $G_{B_3}^{B_3}=\S_3$.
Thus, $G_{B_i}^{B_i}$ is primitive, and so is $X_{B_i}^{B_i}$.

Let $K=X_{(\calB)}$, the kernel of $X$ acting on $\calB$. Suppose
that $K\not=1$. Then $1\not=K^B\lhd X_B^B$, and so $K^B$ is
transitive as $X_B^B$ is primitive. Let $B'\in\calB$ be adjacent in
$\Ga_\calB$ to $B$. Then $K$ is transitive on $B'$, and since
$|B|=|B'|$, we conclude that the induced subgraph $[B,B']$ is
regular, which is a contradiction by
Lemmas~\ref{B-B'-1}-\ref{B-B'-3}. Thus, $K=1$, and so $M=1$, which
is a contradiction. So $M$ is transitive on $V$, and $X$ is
quasiprimitive on $V$. Further, $M$ is non-abelian since
$|V|=3{n\choose3}$.

Now let $M=T_1\times T_2\times\ldots\times T_l$, where $l\geq1$, and
$T_1\cong T_2\cong\ldots\cong T_l$ are non-abelian simple groups.
Then $M\cap G\lhd G$, and so $M\cap G=1$, $\A_n$ or $\S_n$.

Suppose that $M\cap G=1$.
Let $Z=MG=M{:}G$.
If $Z$ is imprimitive on $V$, then a block system $\calB=\calB_1$, $\calB_2$ or $\calB_3$.
Hence $Z\cong Z^\calB\le G^{\calB}\cong\S_n$, which is not possible.
Thus, $Z$ is primitive on $V$, and $G$ does not centralize $M$.
By O'Nan-Scott's theorem (see \cite{Dixon-book}), we have that
$l\ge n$, and ${n(n-1)(n-2)\over 2}=|V|=m^l$ or $m^{l-1}$
where $m\ge5$, which is not possible.

Therefore, $M\cap G=\A_n$ or $\S_n$, and letting $L=\soc(G)=\A_n$,
we have $L\leq M$. Since $L$ is non-abelian simple,  $L$ is
contained in a simple group $T_i$, say $T_1$. Hence, $T_1$ is
transitive on $V$. If $l\ge2$, then as $T_2$ centralizes $T_1$, we
have that $T_2$ is semiregular on $V$. Then $|V|$ divides $|T_1|$,
and $|T_2|=|T_1|$ divides $|V|$. So $T_1$ is regular on $V$, and
since $G$ is transitive on $V$, $L\leq T_1$ is semiregular with at
most 2 orbits. Since $T_1$ has no subgroup of index 2 and
$G/L\cong\ZZ_2$, we have that $L=T_1$ is regular on $V$, which is a
contradiction. Thus, $M=T_1$ is simple and $L\leq M$. Assume that
there exists another minimal normal subgroup $N$ of $X$ such that
$N\neq M$. Then $M\cap N=1$; however, the above argument with $N$ in
the place of $M$ shows that $L\leq N$. So $M\cap N\ge L$, which is a
contradiction. Therefore, $M$ is simple and the unique minimal
normal subgroup of $X$, and hence $X$ is almost simple.

Suppose that $X>G$ and $X$ is imprimitive on $V$.
Let $\calB$ be a block system for $X$ on $V$.
Then $\calB$ is a block system for $G$ on $V$.
By Lemma~\ref{partition}, $\calB=\calB_i$ where $i=1$, 2 or 3, and by Lemma~\ref{quotient}, $\Ga_\calB=\J(n,i)$.
As noticed in the Introduction, $\Aut\Ga_\calB=\S_n$, and so
$\S_n\cong G<X\cong X^{\calB}\leq\Aut\Ga_{\calB}\cong\S_n$, which is not possible.
Hence either $X=G$, or $X$ is primitive on $V$, as claimed.
\qed

A transitive permutation group $G$ on $\Ome$ is called {\it
$k$-homogeneous} if $G$ is transitive on the set of $k$-subsets of
$\Ome$, where $k$ is a positive integer.

\begin{lemma}\label{maximal}
If $n\ge8$, then $\Aut\Ga=G=\Sym([n])$.
\end{lemma}
\proof
Let $n\ge8$.
Suppose that $G<\Aut\Ga$.
Let $L\le\Aut\Ga$ be such that $G$ is a maximal subgroup of $L$.
Since $G$ is transitive on $V$, the almost simple group $L$ has
a factorization $L=GL_\a$.
Further, since $L$ is primitive on $V$, the factorization $L=GL_\a$ is
a maximal factorization.
Thus, the triple $(L,G,L_\a)$ is classified in \cite{LPS-book}, see the MAIN THEOREM on page 1.
An inspection of the candidates with one factor being $G=\S_n$,
we conclude that one of the following holds:
\begin{itemize}
\item[(i)] $n\leq 12$, or

\item[(ii)] $L=\S_{n+1}$, or

\item[(iii)] $L=\S_m$ or $\A_m$, and $G$ is $k$-homogenous of degree $m$,
where $1\le k\le 5$.
% and $L_\a=\S_k\times\S_{m-k}$.
\end{itemize}

Consider the small groups where $n\le12$.
We note that as $\Ga$ is not a complete group, $L<\Sym(V)$.

Let $n=12$ first.
Then $|V|={n(n-1)(n-2)\over2}=660$, and $L$ is a primitive group of degree 660.
Hence $L$ lies in Appendix B of \cite{Dixon-book}, which shows that
$\soc(L)=\PSL(2,659)$ or $\PSL(2,11)\times\PSL(2,11)$.
So $L$ does not contains $\S_{12}$, which is a contradiction.
Similarly, the cases where $n=8$, 9 and 10 are excluded.

%Now consider the case where $n=7$.
%Then $|V|={n(n-1)(n-2)\over2}=105$, and $\Ga$ is of valency $4(n-3)=16$.
%By Appendix B of \cite{Dixon-book}, we have that $(L,L_\a)=(\S_8,2^4{:}\S_4)$,
%or $(\S_{15},\S_2\times\S_{13})$.
%The second case is not possible since $L_\a$ has no transitive representation
%of degree 8 or 16.
%Thus, $L=\S_8$ and $L_\a=2^4{:}\S_4$.

Suppose that $n=11$.
Then $|V|=495$, and $\Ga$ is of valency 32.
By Appendix~B of \cite{Dixon-book}, as $\S_{11}<L$, we conclude that
$(L,L_\a)=(\S_{12},\S_8\times\S_4)$ or $(\O_{10}^-(2),2^8{:}\O_8^-(2))$.
The former is not possible since $\S_{12}\not=\S_{11}(\S_8\times\S_4)$,
 and the latter is not possible since $\O_8^-(2)$ does not have
a transitive representation of degree at most 32.

Next, let $L=\S_{n+1}$, with $n\ge13$. Since $L=GL_\a$, the
stabilizer $L_\a$ is a transitive permutation group of degree $n+1$
such that $|L:L_\a|=|V|={n(n-1)(n-2)\over2}$.
Assume that $L_\a$ is primitive of degree $n+1$.
By Bochert's theorem (see \cite[Theorem~14.2]{Wielandt}), $|L:L_\a|\ge[{n+2\over2}]!$.
Computation shows that $n\le10$, which is a contradiction.
Thus, $L_\a$ is imprimitive of degree $n+1$.
Then $L_\a=\S_b\wr\S_m$, where $bm=n+1$, and thus,
\[{n(n-1)(n-2)\over2}=|V|=|L:L_\a|={(n+1)!\over (b!)^lm!},\]
which is not possible.

Finally, assume that $G=\S_n$ is $k$-homogenous of degree $m$, and
$L=\S_m$ or $\A_m$, and $L_\a=\S_k\times\S_{m-k}$, where $k\le5$.
Since $L$ is not 2-transitive on $V$, we have $k\ge2$.
Thus, by the classification of 2-homogeneous groups, we conclude that $n\le8$,
which is a contradiction.

Therefore, $\Aut\Ga=G=\Sym([n])$, as claimed.
\qed



\section{Proof of Theorem~\ref{main-thm}}

In this section, we prove the main theorem.

By Lemma \ref{diam=3}, part~(i) of Theorem~\ref{main-thm} is true.
By Lemma~\ref{quotient}, Theorem~\ref{main-thm}\,(ii) holds.

For $n=4$ or 5, Theorem~\ref{main-thm} is proved by Lemma~\ref{n=4,5}.
Thus, we next assume $n\ge6$.

For $n=6$ or 7, a computation using Gap shows that $\Aut\Ga_n=\S_n$, and
for $n\ge8$, Lemma~\ref{maximal} shows that $\Aut\Ga=G$.
Then, by Lemma~\ref{vt}, $\Ga$ is half-transitive, as in part~(iii).

Finally, assume that $\Ga$ is a Cayley graph of a group $R$. Then
$R$ is regular on $V$ (see \cite[Proposition~16.3]{Biggs}), and
hence $R$ is 3-homogeneous but not 3-transitive on $[n]$. Further,
as $|R|=|V|=3{n\choose3}$, $R$ is not sharply 3-homogeneous on
$[n]$. Inspecting 3-homogeneous groups which are not 3-transitive,
refer to \cite[Theorem\,9.4B]{Dixon-book}, we conclude that
$R=\AGammaL(1,8)$ or $\PSL(2,q)$ where $q\equiv3$ $(\mod 4)$.
So $n=8$ or $q+1$, respectively.
This proves part~(iv) of Theorem~\ref{main-thm}.
\qed



\begin{thebibliography}{hhhh}

\bibitem{AMN}
B. Alspach, D. Maru\v si\v c, and L. Nowitz,
Constructing graphs which are 1/2-transitive,
{\it J. Austral. Math. Soc. Ser. A} {\bf 56} (1994), 391-402.

\bibitem{A-Xu}
B. Alspach and M. Y. Xu, 1/2-transitive graphs of order $3p$,
{\it J. Algebraic Combin.} {\bf 3} (1994), 347-355.

\bibitem{Biggs}
N. Biggs, {\it Algebraic Graph Theory}, Cambridge University Press,
New York, 1992.

\bibitem{Bouwer}
I. Z. Bouwer, Vertex and edge-transitive but not 1-transitive graphs,
{\it Canad. Math. Bull.} {\bf 13} (1970), 231-237.

\bibitem{BCN-book}
A. E. Brouwer and A. M. Cohen, A. Neumaier, {\it Distance-Regular
Graphs}, Ergeb. Math. Grenzgeb. (3) (Results in Mathematics and
Related Areas (3)), vol. 18, Springer-Verlag, Berlin, 1989.

\bibitem{atlas} J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker,
             and R. A. Wilson, {\it Atlas of Finite Groups},
             Oxford Univ. Press, London/New York, 1985.

\bibitem{Dixon-book}
J. D. Dixon, B. Mortimer, {\it Permutation Groups}, Springer, 1991.

\bibitem{FWZ}
Y. Q. Feng, K. S. Wang and C. X. Zhou,
Tetravalent half-transitive graphs of order $4p$,
{\it Europ. J. Combin.} {\bf 28} (2007), 726-733.

\bibitem{Jones}
G. A. Jones, Automorphisms and regular embeddings of merged Johnson graphs,
{\it European J. Combin.} {\bf 26} (2005), no. 3-4, 417�435.

\bibitem{Li-Sim}
C. H. Li and H. S. Sim, On half-transitive metacirculant graphs of
prime-power order, {\it J. Combin. Theory Ser. B} {\bf 81} (2001),
45-57.

\bibitem{LPS-book}
M. Liebeck, C. E. Praeger and J. Saxl, The maximal factorizations of
the finite simple groups and their automorphism groups, {\it Mem.
Amer. Math. Soc.} {\bf 86} (1990), no. 432.

\bibitem{Marusic}
D. Maru\v si\v c, Recent developments in half-transitive graphs,
{\it Discrete Math}. {\bf 182} (1998), 219-231.

\bibitem{MP}
D. Maru\v si\v c and C. E. Praeger,
Tetravalent graphs admitting half-transitive groups actions: alternating cycles,
{\it J. Combin. Theory Ser. B} {\bf 75} (1999), 185-205.

\bibitem{M-Sparl}
D. Maru\v si\v c and P. \v Sparl, On quartic half-arc-transitive
metacirculants, {\it J. Algebraic Combin.} {\bf 28} (2008), 365-395.

\bibitem{mark-Johnson} Mark Ramras, Elizabeth Donovan,  The Automorphism Group of a Johnson Graph,
{\it Siam J. Discrete Math.} {\bf 25} (2011), 267-270.

\bibitem{Sajna}
M. \v Sajna, Half-transitivity of some metacirculants,
{\it Discrete Math.} {\bf 185} (1998), 117-136.

\bibitem{Song}
Shu-Jiao Song, C. H. Li, and Dian-Jun Wang,
Classifying a family of edge-transitive metacirculant graphs,
{\it J. Algebraic Combin.} {\bf 35} (2012), 497-513.

\bibitem{Sparl-08}
Primoz Sparl, A classification of tightly attached
half-arc-transitive graphs of valency 4 {\it J. Combin. Theory Ser.
B} {\bf 98} (2008).

\bibitem{Sparl}
Primoz Sparl, Almost all quartic half-arc-transitive weak
metacirculants of Class II are of Class IV. {\it Discrete Math.}
{\bf 310} (2010), 1737-1742.

\bibitem{Tutte}
W. T. Tutte, {\it Connectivity in Graphs},
University of Toronto Press, Toronto, 1966.

\bibitem{Wielandt}
H. Wielandt, {\it Finite Permutations Groups}, Academic Press Inc. 1964.

\bibitem{Xu}
M. Y. Xu, Half-transitive graphs of prime-cube order,
{\it J. Algebraic Combin.} {\bf 1} (1992), 275-282.

\end{thebibliography}

\end{document}

thebibliography
