\documentclass{amcjoucc}
\usepackage{pgf,tikz,enumerate,amsmath,amsfonts,amssymb,color}
\newcommand\BIC[4]
{\begin{tikzpicture}[scale=0.6]
\foreach \i in {1,2,...,7}
{
\fill (\i*360/#1:#3) circle (3pt);
\fill (\i*360/#1:#4) circle (3pt);
\fill (8*360/#1:#4) circle (3pt);
\fill (8*360/#1:#3) circle (3pt);
\fill (1*360/#1:#4) circle (3pt);
\fill (1*360/#1:#3) circle (3pt);
\draw (\i*360/#1:#4) -- (\i*360/#1+360/#1:#4);
\draw (\i*360/#1:#3) -- (\i*360/#1:#4);
\draw (8*360/#1:#3) -- (8*360/#1:#4);
\draw (\i*360/#1:#3) -- (\i*360/#1+#2*360/#1:#3);
\draw (8*360/#1:#3) -- (8*360/#1+#2*360/#1:#4);
\draw (8*360/#1:#4) -- (8*360/#1+#2*360/#1:#3);
\draw (1*360/#1:#3) -- (1*360/#1+#2*360/#1:#3);
\draw (1*360/#1:#4) -- (1*360/#1+#2*360/#1:#4);
}
\end{tikzpicture}}
\newcommand\GPG[4]
{\begin{tikzpicture}[scale=0.6]
\foreach \i in {1,2,...,#1}
{
\fill (\i*360/#1:#3) circle (3pt);
\fill (\i*360/#1:#4) circle (3pt);
\draw (\i*360/#1:#4) -- (\i*360/#1+360/#1:#4);
\draw (\i*360/#1:#3) -- (\i*360/#1:#4);
\draw (\i*360/#1:#3) -- (\i*360/#1+#2*360/#1:#3);
}
\end{tikzpicture}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\Cay}{\hbox{Cay}}
\newcommand{\Aut}{\hbox{Aut}}
\begin{document}
\begin{frontmatter} %% Title, information about author, abstract, etc.
\titledata{Odd Automorphisms in Vertex-transitive Graphs} % title of the paper
{} % footnote on the title -- empty if not required
\authordata{Ademir Hujdurovi\'c} % First author name
{University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia\\
University of Primorska, UP FAMNIT, Glagolja\v ska 8, 6000 Koper, Slovenia} % Affiliation and address
{ademir.hujdurovic@upr.si} % E-mail address
{This work is supported in part by the Slovenian Research Agency (research program P1-0285 and research projects N1-0032, N1-0038, and J1-7051).} % Footnote on the first author (grant number, thanks,
% web page, etc.) -- empty in not required
\authordata{Klavdija Kutnar} % Second author
{University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia\\
University of Primorska, UP FAMNIT, Glagolja\v ska 8, 6000 Koper, Slovenia} % Affiliation and address
{klavdija.kutnar@upr.si}
{This work is supported in part by the Slovenian Research Agency
(research program P1-0285 and research projects N1-0032, N1-0038, J1-6720, J1-6743,
and J1-7051), in part by WoodWisdom-Net+, W$^3$B, and in part by NSFC project 11561021.} % No footnote!
\authordata{Dragan Maru\v si\v c} % Third author
{University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia\\
University of Primorska, UP FAMNIT, Glagolja\v ska 8, 6000 Koper, Slovenia\\
IMFM, Jadranska 19, 1000 Ljubljana, Slovenia}
{dragan.marusic@upr.si}
{This work is supported in part by the Slovenian Research Agency (I0-0035, research program P1-0285 and research projects N1-0032, N1-0038, J1-5433, J1-6720,
and J1-7051), and in part by H2020 Teaming InnoRenew CoE. }
\keywords{graph, vertex-transitive, automorphism group,
even permutation, odd permutation.} % Keywords
\msc{20B25, 05C25} % Math. Subj. Class. codes
\begin{abstract}
An automorphism of a graph is said to be {\em even/odd} if
it acts on the set of vertices as an even/odd permutation.
It this article the problem regarding existence of odd automorphisms
in vertex-transitive graphs is proposed. Partial results for certain
classes of vertex-transitive graphs, in particular for
Cayley graphs, are given. As a consequence, a characterization
of arc-transitive circulants without odd automorphisms is obtained.
\end{abstract}
\end{frontmatter} %% End of the front matter
%% Your article
%\item \texttt{thm} (Theorem)
%\item \texttt{prop} (Proposition)
%\item \texttt{lem} (Lemma)
%\item \texttt{cor} (Corollary)
%\item \texttt{claim} (Claim)
%\item \texttt{axiom} (Axiom)
%\item \texttt{conj} (Conjecture)
%\item \texttt{hypo} (Hypothesis)
%\item \texttt{assum} (Assumption)
%\item \texttt{prob} (Problem)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%% section 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:intro}
\indent
Apart from being a rich source of interesting mathematical objects in their own right,
vertex-transitive graphs
provide a perfect platform for investigating structural properties of transitive permutation groups
from a purely combinatorial viewpoint.
The recent outburst of research papers on this topic should therefore come as no surprise.
Most of these papers have arisen as direct attempts - by developing consistent theories and strategies --
to solve open problems in vertex-transitive graphs;
the hamiltonicity problem \cite{LL69}, for example,
being perhaps the most popular among them.
In this context knowing the full (or as near as possible) automorphism group
of a vertex-transitive graph is important because it provides the most complete
description of its structure. While some automorphisms are obvious,
often part of the defining properties, there are others, not so obvious
and hence more difficult to find.
Consider for example bicirculants, more precisely, $n$-bicirculants, that is, graphs admitting
an automorphism $\rho$ with two orbits of size $n \geq 2$ and no other orbits.
There are three essentially different possibilities for such a graph to be vertex-transitive
depending on whether its automorphism group contains a swap and/or a mixer, where
a {\em swap} is an automorphism interchanging the two orbits of $\rho$, and
a {\em mixer} is an automorphism which neither fixes nor interchanges the two orbits of $\rho$.
For example, the Petersen graph has swaps and mixers, prisms (except for the cube) have only swaps, while the dodecahedron has only mixers.
Clearly, swaps are the ``obvious'' automorphisms and mixers are ``not so obvious'' ones
(see Figure~\ref{fig:sm}).
\begin{figure}[h]
\begin{center}
\GPG{5}{2}{1.5cm}{3cm} \quad \quad
\GPG{5}{1}{1.5cm}{3cm} \quad \quad
\GPG{10}{2}{2.0cm}{3.5cm}
\caption{\label{fig:sm} \footnotesize The Petersen graph, the $5$-prism and the dodecahedron -- the first two admit a swap, while the third one does not.}
\end{center}
\end{figure}
In this paper we propose to approach the sometimes elusive separation line between the obvious and not so obvious automorphisms
via the even/odd permutations dichotomy.
Let us call an automorphism of a graph {\em even/odd} if
it acts on the vertex set as an even/odd permutation.
Further, a graph is said to be {\em even-closed} if all of its automorphisms
are even.
The Petersen graph and odd prisms have odd automorphisms, the swaps being
such automorphisms. On the other hand, the dodecahedron has only even automorphisms \cite{KM}.
Furthermore, consider the two cubic $2k$-bicirculants, $k>1$, shown in Figure~\ref{fig:8bic} for $k=4$. Both have swaps which are even automorphisms.
More precisely, all of the automorphisms of the $2k$-prism on the left-hand side
are even. As for the graph
on the right-hand side -- the Cayley graph
$\Cay(\ZZ_{4k},\{\pm 1, 2k\})$ on the
cyclic group $\ZZ_{4k}=\la 1\ra$ -- any generator of the
left regular representation of $\ZZ_{4k}$ is an odd automorphism.
\begin{figure}[h]
\begin{center}
\GPG{8}{1}{1.75cm}{3.5cm} \quad \quad
\BIC{8}{1}{1.75cm}{3.5cm}
\caption{\label{fig:8bic} \footnotesize Two examples of cubic $2k$-bicirculants for $k=4$,
one with and one without odd automorphisms.}
\end{center}
\end{figure}
This brings us to the following natural question:
Given a transitive group of even automorphisms $H$ of a graph $X$,
is there a group $G$ containing odd automorphisms of $X$ and $H$ as a subgroup?
In particular, we would like to focus on the following problem.
%ftp://www.combinatorialmath.ca/g&g/graphlib/transitive/
\begin{prob}
\label{prob:even/odd}
Which vertex-transitive graphs admit odd automorphisms?
\end{prob}
Of course, in some cases, the answer to the above problem will be purely arithmetic.
Such is for example the
case with cycles.
Clearly, all cycles of even length admit odd
automorphisms, while cycles of odd length $2k +1$ admit odd
automorphisms if and only if
$k$ is odd.
The answer for some of the well studied classes of graphs, however, suggest that the above even/odd question goes
beyond simple arithmetic conditions and is likely to uncover certain more complex structural properties.
For example, while the general distinguishing feature for cubic symmetric graphs
(with respect to the above question)
is their order $2n$, $n$ even/odd, there are exceptions on both sides. Namely, there exist cubic symmetric graphs
without odd automorphisms for $n$ odd, and with odd automorphisms for $n$ even,
see \cite{KM}.
In this paper a special emphasis is given to certain classes of
Cayley graphs (see Section~\ref{sec:cay}), such as circulants for example.
Theorem~\ref{thm:cir} gives a necessary and sufficient condition for a normal circulant
to be even-closed. This result combined together with certain other results
of this section then leads to a characterization of even-closed arc-transitive circulants,
see Theorem~\ref{pro:ATcir}.
%Corollary or Theorem__
In Section~\ref{sec:vt} the even/odd question is discussed in a more general context of vertex-transitive graphs.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%% section 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries}
\label{sec:pre}
\indent
Here we bring together definitions, notations and some results that will be needed in the remaining sections.
For a finite simple graph $X$ let $V(X)$, $E(X)$, $A(X)$ and $\Aut(X)$
be its vertex set, its edge set, its arc set and its automorphism group, respectively.
A graph is said to be {\it vertex-transitive}, {\it edge-transitive} and {\it arc-transitive}
(also {\em symmetric}) if its automorphism group acts transitively
on the set of vertices, the set of edges, and the set of arcs of the graph,
respectively. A non-identity automorphism is {\it semiregular},
in particular $(m,n)$-{\it semiregular} if it has $m$ cycles of equal length $n$ in its cycle decomposition, in short $m$ orbits of equal length $n$.
An {\it $n$-circulant} ({\em circulant}, in short) is a graph admitting a
$(1,n)$-semiregular automorphism, and an
{\it $n$-bicirculant} ({\em bicirculant}, in short) is a graph admitting a $(2,n)$-semiregular automorphism.
Given a group $G$ and a symmetric
subset $S=S^{-1}$ of $G\setminus\{1\}$, the {\em Cayley graph }
$X=Cay(G,S)$ has vertex set $G$ and
edges of the form $\{g,gs\}$ for all $g\in G$ and $s \in S$.
%
Every Cayley graph is vertex-transitive
but there exist vertex-transitive graphs that are not Cayley, the Petersen graph being the smallest such graph.
Cayley graphs are characterized in the following way.
A graph is a Cayley graph of a group $G$ if and only if
its automorphism group contains a regular subgroup $G_L$,
referred to as the {\em left regular representation} of $G$, isomorphic to
$G$, see \cite{Sab}.
Using the terminology and notation of Cayley graphs, note that
an $n$-circulant is a Cayley graph $\Cay(G,S)$ on a cyclic group
$G$ of order $n$ relative to some symmetric subset $S$ of $G\setminus\{1\}$,
usually denoted by $Cir(n,S)$.
The first of the two group-theoretic observations below reduces
the question of existence of odd automorphisms to
Sylow $2$-subgroups of the automorphism group.
\begin{prop}
\label{pro:permutation1}
A permutation group $G$ contains an odd permutation
if and only if its Sylow $2$-subgroup contains an odd permutation.
\end{prop}
\begin{prop}
\label{pro:permutation2}
A permutation group $G$ acting
semiregularly with an odd number of orbits
admits odd permutations if and only if its Sylow $2$-subgroup is cyclic.
\end{prop}
\begin{proof}
Clearly, if a Sylow $2$-subgroup is cyclic, the corresponding
generators are odd permutations.
On the other hand, if a Sylow $2$-subgroup $J$ is not cyclic
then the semiregularity of $G$ implies that all of the elements of $J$
must be even permutations. By Proposition~\ref{pro:permutation1}
$G$ itself consists solely of even permutations.
\end{proof}
As a consequence of Proposition~\ref{pro:permutation2},
for some classes of graphs the existence of odd automorphisms is easy to
establish. For instance, in Cayley graphs the corresponding regular subgroup contains odd automorphisms if and only if its Sylow $2$-subgroup is cyclic.
When a Sylow
$2$-subgroup is not cyclic, however, the search for odd automorphisms has to be done outside this
regular subgroup, raising the complexity of the problem.
%A graph $X$ is said to be {\em even-closed}
%if its automorphism group is contained in the alternating group $A_{|V(X)|}$,
%that is, if $X$ does not admit odd automorphisms.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%% section 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Cayley graphs}
\label{sec:cay}
\indent
In this section we give some general results about the existence of odd automorphisms
in Cayley graphs and discuss the problem in detail for circulants.
The first proposition, a corollary of Proposition~\ref{pro:permutation1}, gathers straightforward facts about the existence
of odd automorphisms in Cayley graphs.
(A graph is said to be a {\em graphical regular representation}, or a {\em GRR},
for a group $G$ if its automorphism group is isomorphic to $G$
and acts regularly on the vertex set of the graph.)
\begin{prop}
\label{pro:cay}
A Cayley graph on a group $G$ admits odd automorphisms
in $G_L$ if and only if Sylow $2$-subgroups of $G$ are cyclic.
In particular,
\begin{itemize}
\itemsep=0pt
\item a Cayley graph of order ${2\pmod 4}$ admits odd automorphisms,
\item a GRR graph admits odd automorphism if and only if Sylow $2$-subgroups of $G$ are cyclic.
\end{itemize}
\end{prop}
By Proposition~\ref{pro:cay}, Cayley graphs of order twice an odd number
admit odd automorphisms (they exist in a regular subgroup
of the automorphism group). As
for Cayley graphs whose order is odd or
divisible by $4$ the answer is not so simple.
The next proposition answers the question
of existence of odd automorphisms in particular
subgroups of automorphisms of Cayley graphs on abelian groups.
\begin{prop}
\label{pro:abelian}
Let $X=Cay(G,S)$ be a Cayley graph on an abelian group $G$ and let
$\tau\in \Aut(G)$ be such that $\tau(i)=-i$. Then $\la G_L,\tau\ra\le \Aut(X)$, and there
exists an odd automorphism in $\la G_L,\tau\ra$ if and only if one of the following holds:
\begin{enumerate}[(i)]
\itemsep=0pt
\item $|G|\equiv {3\pmod 4}$,
\item $|G|\equiv {2\pmod 4}$,
\item $|G|\equiv {0\pmod 4}$ and a Sylow $2$-subgroup of $G$ is cyclic.
\end{enumerate}
\end{prop}
\begin{proof}
First recall that
the mapping $\tau\colon G \to G$ defined by $\tau(i)=-i$ is an automorphism
of the group $G$ if and only if $G$ is abelian.
Moreover, since $S=-S$ it is easy to see that $\tau\in\Aut(X)$.
Clearly, when $|G|\equiv {1\pmod 4}$ there are no odd automorphisms in
$\la G_L,\tau\ra$. Suppose now that $|G|\not\equiv {1\pmod 4}$.
If $|G|\equiv {3\pmod 4}$ then
the involution $\tau$ has $2k+1$ cycles of length $2$
and one fixed vertex in its cyclic decomposition, and so
it is an odd automorphism.
If $|G|\equiv {2\pmod 4}$ then there exist
odd automorphisms in $G_L\le\la G_L,\tau\ra$ by Proposition~\ref{pro:cay}.
We are therefore left with the case $|G|\equiv {0\pmod 4}$.
Hence suppose that $G$ is of such order.
If a Sylow $2$-subgroup $J$ of $G_L$ is cyclic then
a generator of $J$ is a product of an odd number $|G|/|J|$
of cycles of length $|J|$, and thus an odd automorphism.
On the other hand, if $J$ is not cyclic then every element of $J$ has an
even number of cycles in its cyclic decomposition.
As for $\tau$, an element of $G$ is fixed by $\tau$ if and only if it is an involution. In other words, it fixes the largest elementary abelian $2$-group $T$ inside the
Sylow $2$-subgroup $J$, say of order $2^k$. Consequently, the number of
transpositions in the cyclic decomposition of $\tau$ equals $|G|/2-2^k$,
which is an even number if and only if $k\ge 1$. Consequently,
$\tau$ is an odd automorphism if and only if $T\cong \ZZ_2$ and hence $J$
is cyclic.
\end{proof}
\begin{cor}
\label{cor:cir}
Let $X=Cir(n,S)$, where $S$ is a symmetric subset of $\ZZ_{n}$, and either $n$ is
even or $n\equiv {3 \pmod 4}$. Then $X$ admits odd automorphisms.
\end{cor}
\begin{proof}
For $n$ even any generator of the left regular representation of
$\ZZ_n$ is an odd automorphism.
For $n=4k+3\equiv{3\pmod 4}$
the involution $\tau\colon i\mapsto -i$ is an odd automorphism of $X$
by Proposition~\ref{pro:abelian}.
\end{proof}
When $n\equiv {1 \pmod 4}$ the situation is more complex. For example,
cycles $C_{4k+1}=Cir(4k+1,\{\pm1\})$ admit only even automorphisms. On the other hand,
the circulant
$Cir(13,\{\pm 1,\pm 5\})$ is an example of a $(4k+1)$-circulant admitting odd automorphisms.
Namely, one can easily check that the permutation
$(0)(1,5,12,8)(2,10,11,3)(4,7,9,6)$ arising from the action of $5\in\ZZ_{13}^*$
is one of its odd automorphisms.
(For a positive integer $n$ we use
$\ZZ_n^*$ to denote the multiplicative group of units of $\ZZ_n$.)
We therefore propose the following problem.
\begin{prob}
Classify even-closed circulants of order $n\equiv {1 \pmod 4}$.
% which do not admit odd automorphisms.
\end{prob}
A partial answer to this problem is given at the end of this section,
see Corollary~\ref{cor:ATcirculants} and Theorem~\ref{pro:ATcir}.
We start with the class of connected arc-transitive circulants.
The classification of such circulants, obtained independently by Kov\'acs \cite{K03} and Li \cite{L03},
is essential to this end.
In order to state the classification let us recall the concept of normal Cayley graphs and
certain graph products.
The {\em wreath (lexicographic) product} $Y[X]$ of a graph $X$ by
a graph $Y$ is the graph with vertex set $V(Y)\times V(X)$ such that $\{(u_1,u_2),(v_1,v_2)\}$ is an edge
if and only if either $\{u_1,v_1\}\in E(Y)$, or $u_1=v_1$ and $\{u_2,v_2\}\in E(X).$ For a positive integer $b$ and
a graph $Y$, denote by $bY$ the graph consisting of $b$ vertex-disjoint copies of the graph $Y.$ The graph
$Y[\overline{K_b}]-bY $ is called the {\em deleted wreath (deleted lexicographic) product} of $Y$ and $\overline{K_b}$,
where $\overline{K_b}=bK_1$.
%By $\overline{\Gamma}$ we denote the complement of the graph $\Gamma,$ that is $V(\overline{\Gamma})=V(\Gamma)$ such
%that any two vertices $u$ and $v,$ are adjacent in $\overline{\Gamma}$, if and only if they are not adjacent in $\Gamma$. For two
%graphs $\Gamma $ and $X$ with $V(\Gamma)=V(X)=V$ denote by $\Gamma-X$ the graph with vertex set $V$
%and edge set $E(\Gamma)\backslash E(X).$
Let $X=Cay(G,S)$ be a Cayley graph on a group $G$.
Denote by $\Aut(G,S)$ the set of all
automorphisms of $G$ which fix $S$ setwise, that is,
$$
\Aut(G,S)=\{\sigma\in \Aut(G)|S^{\sigma}=S\}.
$$
It is easy to check that $\Aut(G,S)$ is a subgroup of $\Aut(X)$ and
that it is contained in the stabilizer of the identity element $1\in G.$
Following Xu \cite{Xu98}, $X=Cay(G,S)$ is called
a {\em normal Cayley graph} if $G_L$ is normal in $\Aut(X)$, that is, if $\Aut (G,S)$
coincides with the vertex stabilizer $1\in G$.
Moreover, if $X$ is a normal Cayley graph, then $\Aut(X)=G_L\rtimes \Aut(G,S)$.
\begin{prop}
\label{classificationATC}
{\rm\cite{K03,L03}}
Let $X$ be a connected arc-transitive circulant of order $n$. Then one of the following holds:
\begin{enumerate}
\itemsep=0pt
\item[(i)] $X \cong K_n;$
\item[(ii)] $X =Y[\overline{K_d}],$ where $n=md$, $m,d>1$ and $Y$ is a connected arc-transitive circulant of order $m$;
\item[(iii)] $X=Y[\overline{K_d}]-dY,$ where $n=md,$ $d>3,$ $gcd(d,m)=1$ and $Y$ is a
connected arc-transitive circulant of order $m$;
\item[(iv)] $X$ is a normal circulant.
\end{enumerate}
\end{prop}
The proof of the next proposition is straightforward.
\begin{prop}
\label{pro:Kn}
Complete graphs $K_n$, $n\ge 2$, admit odd automorphisms.
\end{prop}
Propositions~\ref{pro:lexi},~\ref{pro:dlexi},~\ref{pro:dlexi-1}, and~\ref{pro:dlexi-2} deal with
the existence of odd automorphisms
in the framework of (deleted) lexicographic products of graphs.
\begin{prop}
\label{pro:lexi}
Let $Z$ be a graph admitting an odd automorphism.
Then a lexicographic product $Y[Z]$ of the graph $Z$ by a graph $Y$
admits odd automorphisms. In particular, $Y[\overline{K_d}]$, $d>1$,
admits odd automorphisms.
\end{prop}
\begin{proof}
An odd automorphism is constructed in such a way
that it acts trivially on all blocks (that is, copies of the graph $Z$) but one
where it acts as an odd automorphism of the graph $Z$.
\end{proof}
\begin{prop}
\label{pro:dlexi}
Let $X$ be a deleted lexicographic product $X=Y[Z]-dY$, where $Z$ has odd automorphisms and $Y$ is of odd order $m$.
Then $X$ admits odd automorphisms.
\end{prop}
\begin{proof}
An odd automorphism is constructed in such a way
that it acts as the same odd automorphism
on every copy of the graph $Z$.
\end{proof}
\begin{prop}
\label{pro:dlexi-1}
Let $X$ be a deleted lexicographic product $X=Y[Z]-dY$, where $Z$ is of odd order $d$ and $Y$ has odd automorphisms.
Then $X$ admits odd automorphisms.
\end{prop}
\begin{proof}
An odd automorphism $\alpha$ is constructed
by extending an odd automorphism $\alpha'$ of $Y$ to an automorphism of $X$
by letting $\alpha$ acting as $\alpha'$ on each level of the deleted lexicographic product.
\end{proof}
Propositions~\ref{pro:dlexi} and~\ref{pro:dlexi-1} combined together
imply existence of odd automorphisms in arc-transitive circulants
belonging to the family given in Proposition~\ref{classificationATC}(iii).
\begin{prop}
\label{pro:dlexi-2}
Let $X$ be an arc-transitive circulant isomorphic to the deleted lexicographic product $Y[dK_1]-dY$, where $Y$ is an arc-transitive circulant of order coprime with $d>1$. Then $X$ has an odd automorphism.
\end{prop}
\begin{proof}
Suppose first that $Y$ is of odd order. Then,
since $dK_1$ admits odd automorphisms,
the existence of odd automorphisms in $Aut(X)$
follows from Proposition~\ref{pro:dlexi}.
%
Suppose now that $Y$ is of even order. Then the generic cycle of $Y$ is an odd
automorphism.
Since in this case $d$ is odd the existence of odd automorphisms in $Aut(X)$
follows from Proposition~\ref{pro:dlexi-1}.
\end{proof}
Corollary~\ref{cor:cir} and
Propositions~\ref{pro:Kn},~\ref{pro:lexi} and~\ref{pro:dlexi-2} combined together
imply that even-closed arc-transitive circulants may only exist amongst normal
arc-transitive circulants of order ${1\pmod 4}$. In all other cases an arc-transitive
circulant admits an odd automorphism.
\begin{cor}
\label{cor:ATcirculants}
An even-closed arc-transitive circulant is normal and of order ${1\pmod 4}$.
\end{cor}
For the rest of this section we may, in our search for odd automorphisms, therefore restrict ourselves to normal circulants.
Note that for a normal arc-transitive circulant $Cir(n,S)$ we may assume that $1\in S$.
This fact is used throughout this section.
The following lemma about the action of
the multiplicative group of units is needed in this
respect.
For a positive integer $n$ we use $n_p$ to denote the highest power of $p$ dividing $n$.
\begin{lemma}
\label{lem:pk}
Let $p$ be an odd prime, and let $k\geq 1$ be a positive integer. Then
$\ZZ_{p^k}^*$, in its natural action on $\ZZ_{p^k}$, admits an odd permutation
if and only if $k$ is odd.
\end{lemma}
\begin{proof}
By Proposition~\ref{pro:permutation1} it suffices to consider the Sylow $2$-subgroup $J$ of $\ZZ_{p^k}^*$. Since $\ZZ_{p^k}^*$ is a cyclic group, $J$ is cyclic too. Let $\alpha$ be a generator of $J$. We claim that $\langle \alpha \rangle$ acts semiregularly on $\ZZ_{p^k}\setminus\{0\}$.
Suppose on the contrary that this is not the case. Then there exist $m\in \mathbb{N}$ such that $\alpha^m\ne 1$ and $\alpha^m(x)=x$ for some $x\in \ZZ_{p^k}\setminus\{0\}$.
This is equivalent to
$$
(\alpha^m-1)x \equiv 0 \pmod {p^k}.
$$
The above equation admits a non-trivial solution if and only if $\alpha^m-1$ is divisible by $p$.
Suppose that $j1$ the number $\binom{2^s}{i}(Ap^j)^i$ is divisible by $p^{j+1}$.
Consequently, $2^sAp^j$ is divisible by $p^{j+1}$, and so
we conclude that $p$ divides $2^sA$, a contradiction.
As claimed above, this shows that $\alpha$ acts semiregularly on $\ZZ_{p^k}\setminus\{0\}$ with
$$
\frac{p-1}{(p^k-p^{k-1})_{2}}\cdot\frac{p^k-1}{p-1}=(1+p+\ldots+p^{k-1})\frac{p-1}{(p^k-p^{k-1})_{2}}
$$
cycles of even length $(p^k-p^{k-1})_{2}$ in its cycle decomposition.
Since the parity of $1+p+\ldots+p^{k-1}$ depends on whether $k$ is even or odd,
it follows that $\alpha$ is an odd permutation if and only if $k$ is odd.
The result follows.
\end{proof}
\begin{cor}
Let $p$ be an odd prime, and let $k\geq 1$ be a positive integer such that $p^k\equiv {1 \pmod 4}$. Then a normal arc-transitive circulant $X=Cay(\ZZ_{p^k},S)$ admits an odd automorphism if and only if $k$ is odd and $S$ contains the Sylow $2$-subgroup of $\ZZ_{p^k}^*$.
\end{cor}
\begin{proof}
Recall that $\Aut(X)\cong \ZZ_{p^k}\rtimes S$, and thus $X$ admits odd automorphisms if and only if $S$ contains an element
giving rise to an odd permutation on $\ZZ_{p^k}$. The result is thus obtained
by combining together Proposition~\ref{pro:permutation1} and Lemma~\ref{lem:pk}.
\end{proof}
\begin{lemma}
\label{lem:decom}
Let $n=p_1^{2k_1+1}\cdots p_a^{2k_a+1}q_1^{2l_1}\ldots q_b^{2l_b}$ be a prime decomposition of an odd integer $n$, and let $\ZZ_n\cong P_1\oplus\cdots\oplus P_a\oplus Q_1\oplus\cdots \oplus Q_b$, where
$P_i\cong \ZZ_{p_i^{2k_i+1}}$, $i\in\{1,\ldots,a\}$, and
$Q_i\cong \ZZ_{q_i^{2l_i}}$, $i\in\{1,\ldots,b\}$. Further,
let $\alpha_i$ and $\beta_i$, respectively, be generators of
the Sylow $2$-subgroup of $P_i^*$ and
the Sylow $2$-subgroup of $Q_i^*$.
Then, for each $i$, we have that $\alpha_i$ is an odd permutation on $\ZZ_n$,
and $\beta_i$ is an even permutation on $\ZZ_n$.
\end{lemma}
\begin{proof}
Observe that each cycle in the cycle decomposition of $\alpha_i\in P_i$
(considered as a permutation of $\ZZ_{p_i^{2k_i+1}}$) is lifted to $n/p_i^{2k_i+1}$ cycles of the same length in the cycle decomposition of $\alpha_i$ (when considered as a permutation of $\ZZ_n$).
By Lemma~\ref{lem:pk}, $\alpha_i$ is an odd permutation on $\ZZ_{p_i^{2k_i+1}}$ for each $i$. Similarly, $\beta_i$ is an even permutation on $\ZZ_{q_i^{2l_i}}$ for each $i$. The result follows.
\end{proof}
We introduce the following notation.
Let $n=p_1^{k_1}\cdots p_a^{k_a}$ be a prime decomposition of a positive integer $n$, let
\begin{eqnarray*}
\ZZ_n\cong \oplus_{i=1}^{a}P_i, \ \textrm{where} \ P_i\cong \ZZ_{p_i^{k_i}},
\end{eqnarray*}
and let $J(p_i)$ be the Sylow $2$-subgroup of $P_i^*$.
%
In the next theorem a necessary and sufficient condition for a normal circulant to be even-closed is given.
One of the immediate consequence is, for example, that a normal circulant of order $n^2$, $n$ odd, is even-closed.
\begin{thm}
\label{thm:cir}
Let $n=p_1^{k_1}\cdots p_a^{k_a}$ be a prime decomposition of a positive integer $n$, and let $X=Cir(n,S)$ be a normal arc-transitive circulant on
$\ZZ_n\cong \oplus_{i=1}^{a}P_i$.
Then $X$ is even-closed if and only if $n\equiv {1\pmod 4}$ and
for every $\alpha=\oplus_{i=1}^{a}\alpha_i\in S$ we have
$$
\sum_{i=1}^a\theta_i(\alpha) \equiv {0\pmod 2},
\textrm{ where }
\theta_i(\alpha)=\left\{\begin{array}{ll}
1; & \textrm{ if $J(p_i)\le\la\alpha_i\ra$ and $k_i$ is odd}\\
0; & \textrm{ otherwise}\\
\end{array}\right..
$$
\end{thm}
\begin{proof}
By Corollary~\ref{cor:cir} for $n\not\equiv {1\pmod 4}$ the graph $X$ admits odd automorphisms. We may therefore assume that
$n\equiv {1\pmod 4}$. By Lemma~\ref{lem:decom}, the existence of odd
automorphisms in $X$ depends solely on the parity of the exponents $k_i$
and the containment of the generators of the corresponding Sylow $2$-subgroups in $S$, and the result follows.
\end{proof}
%\begin{cor}
%A normal circulant of order $n^2$, $n$ odd, is even-closed.
%\end{cor}
Combined together
with Corollary~\ref{cor:ATcirculants} and
Theorem~\ref{thm:cir} we have the following
characterization of
even-closed arc-transitive circulants.
\begin{thm}
\label{pro:ATcir}
Let $X$ be an even-closed arc-transitive circulant of order $n$ and let
$n=p_1^{k_1}\cdots p_a^{k_a}$ be a prime decomposition of $n$.
Then $X$ is a normal circulant $X=Cir(n,S)$ on
$\ZZ_n\cong \oplus_{i=1}^{a}P_i$, $n\equiv {1\pmod 4}$ and
for every $\alpha=\oplus_{i=1}^{a}\alpha_i\in S$ we have
$$
\sum_{i=1}^a\theta_i(\alpha) \equiv {0\pmod 2},
\textrm{ where }
\theta_i(\alpha)=\left\{\begin{array}{ll}
1; & \textrm{ if $J(p_i)\le\la\alpha_i\ra$ and $k_i$ is odd}\\
0; & \textrm{ otherwise}\\
\end{array}\right..
$$
\end{thm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%% section 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Vertex-transitive graphs} %of particular orders}
\label{sec:vt}
\indent
It is known that every finite transitive permutation group
contains a fixed-point-free element of prime power order~(see \cite[Theorem 1]{FKS81}),
but not necessarily a fixed-point-free
element of prime order and, hence, a semiregular element (see for instance~\cite{seven,FKS81}).
In 1981 the third author asked if every vertex-transitive digraph with at least
two vertices admits a
semiregular automorphism (see \cite[Problem 2.4]{DM81}).
Despite considerable efforts by various mathematicians the problem remains open,
with the class of vertex-transitive graphs
having a solvable automorphism group being the main obstacle.
The most recent result on the subject is due to Verret \cite{V15}
who proved that every arc-transitive
graph of valency $8$ has a semiregular automorphism, which was the smallest
open valency for arc-transitive graphs
(see \cite{DMMN07, GV, MS98}
and \cite{KM08} for an overview of the status of this problem).
While the existence of such automorphisms in certain
vertex-transitive graphs has
proved to be an important building block in obtaining at least partial
solutions in many open problems in algebraic graph theory,
such as for example the hamiltonicity problem (see \cite{KM08a,KS09,LL69}),
the connection to the even/odd problem is straightforward.
\begin{prop}
\label{pro:semi}
An even-closed vertex-transitive graph does not have even order semiregular
automorphisms with an odd number of orbits.
\end{prop}
This suggest that in a search for odd automorphisms
a special attention should be given to semiregular
automoprhisms of even order.
Furthermore, for those classes of vertex-transitive graphs for which
a complete classification (together with the corresponding automorphism groups) exists,
the answer to Problem~\ref{prob:even/odd} is, at least implicitly, available right there -- in the classification.
Such is, for example, the case of vertex-transitive graphs
of order a product of two primes, see \cite{MS92,MS94,PX93},
and the case of vertex-transitive graphs which are graph truncations,
see \cite{AD15}.
%
The hard work needed to complete these classifications suggest that the even/odd
question is by no means an easy one.
Let us consider, for example, the class of all vertex-transitive graphs of order $2p$,
$p$ a prime.
In the completion of the classification of these graphs,
the classification of finite simple groups is an essential ingredient in handling
the case of primitive automorphism groups.
We know, by this classification, that
the Petersen graph and its complement are the only such graphs with a primitive
automorphism group. Of course, they both admit odd automorphisms.
As for imprimitive automorphism groups, it all depends on the arithmetic of $p$.
When $p \equiv {3\pmod 4}$,
the graphs are necessarily Cayley graphs (of dihedral groups) and hence
must admit odd automorphisms.
(Namely, reflections interchanging the two orbits of the rotation in the dihedral group
are odd automorphisms.)
When $p \equiv {1\pmod 4}$, then it follows by the classification
of these graphs \cite{DM81} that there is an automorphism of order $4$,
interchanging the two blocks of imprimitivity of size $p$,
having one orbit of size $2$ and $(p-1)/2$
orbits of size $4$, thus an odd number of orbits in total.
We have thus shown that every vertex-transitive graph of order twice a prime number
admits an odd automorphism.
However, no ``classification of finite simple groups free" proof of the above fact
is known to us.
In conclusion we would like to make the following comment with regards to
cubic vertex-transitive graphs. Recall that the class of cubic vertex-transitive graphs decomposes into three subclasses
depending on the number of orbits of
the vertex-stabilizer on the set of neighbors of a vertex.
These subclasses are
arc-transitive graphs (one orbit), graphs with vertex-stabilizers being $2$-groups (two orbits) and
GRR graphs (three orbits), see \cite{PSV13}. (Note that there are two types of cubic GRR graphs,
those with connecting set consisting of three involutions and those with connecting set consisting of
an involution, a non-involution and its inverse, see \cite{CPZ}.)
For the first and third subclass the answer to Problem~\ref{prob:even/odd}
is given in \cite{KM} and Proposition~\ref{pro:cay}, respectively, while the
problem is still open for the second subclass.
Examples given in Section~\ref{sec:intro}
(see also Figure~\ref{fig:8bic}) show, however, that this second subclass contains
infinitely many even-closed
graphs as well as infinitely many graphs admitting odd automorphisms.
\begin{prob}
Classify cubic vertex-transitive graphs with vertex-stabilizers being $2$-groups that admit odd
automorphisms.
\end{prob}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}
\begin{footnotesize}
\bibitem{AD15} B.~Alspach and E.~Dobson,
On automorphism gorups of graph truncations,
{\em Ars Math. Contemp.} {\bf 8} (2015), 215--223.
\bibitem{seven} P.~J.~Cameron, M.~Giudici, W.~M.~Kantor, G.~A.~Jones, M.~H.~Klin,
D.~Maru\v si\v c and L.~A.~Nowitz, Transitive permutation groups
without semiregular subgroups, {\em J. London Math. Soc.} {\bf 66 }
(2002), 325--333.
\bibitem{CPZ} M.~D.~E.~Conder, T.~Pisanski and A.~\v Zitnik,
Vertex-transitive graphs and their arc-types, arXiv:1505.02029.
\bibitem{DMMN07} E.~Dobson, A.~Malni\v c, D.~Maru\v si\v c and L.~A.~Nowitz,
Semiregular automorphisms of vertex- transitive graphs of certain valencies,
{\em J. Combin. Theory, Ser. B} {\bf 97} (2007), 371--380.
\bibitem{GV} M.~Giudici and G.~Verret,
Semiregular automorphisms in arc-transitive graphs of valency $2p$,
in preparation.
\bibitem{FKS81} B.~Fein, W.~M.~Kantor and M.~Schacher,
Relative Brauer groups II,
{\em J. Reine Angew. Mat.} {\bf 328} (1981), 39--57.
\bibitem{K03} I.~Kov\'acs,
Classifying arc-transitive circulants,
{\em J. Algebr. Combin.} {\bf 20} (2004), 353--358.
\bibitem{KM08a} K.~Kutnar and D.~Maru\v si\v c,
Hamiltonicity of vertex-transitive graphs of order $4p$,
{\em European J. Combin.} {\bf 29} (2008) 423--438.
\bibitem{KM08} K.~Kutnar and D.~Maru\v si\v c,
Recent trends and future directions in vertex-transitive graphs,
{\em Ars Math. Contemp.} {\bf 1} (2008), 112-–125.
\bibitem{KS09} K.~Kutnar and P.~\v Sparl,
Hamilton paths and cycles in vertex-transitive graphs of order $6p$,
{\em Discrete Math.} {\bf 309} (2009) 5444--5460.
\bibitem{KM} K.~Kutnar and D.~Maru\v si\v c,
Cubic symmetric graphs via odd automorphisms, manuscript.
\bibitem{L03} C.~H.~Li,
Permutation groups with a cyclic regular subgroup and arc-transitive circulants,
{\em J. Algebr. Combin.} {\bf 21} (2005), 131--136.
\bibitem {LL69} L.~Lov\'asz, Combinatorial structures and their applications,
(Proc. Calgary Internat. Conf., Calgary, Alberta, 1969),
pp. 243--246, Problem 11, Gordon and Breach, New York, 1970.
\bibitem{DM81} D.~Maru\v si\v c, On vertex symmetric digraphs,
{\em Discrete Math.} {\bf 36} (1981), 69--81.
\bibitem{MS92} D.~Maru\v si\v c and R.~Scapellato,
Characterizing vertex-transitive $pq$-graphs with
imprimitive automorphism subgroups,
{\em J.~Graph Theory} {\bf 16} (1992), 375--387.
\bibitem{MS94} D.~Maru\v si\v c and R.~Scapellato,
Classifying vertex-transitive graphs whose order is a product of two primes,
{\em Combinatorics} {\bf 14} (1994), 187--201.
\bibitem{MS98} D.~Maru\v si\v c and R.~Scapellato,
Permutation groups, vertex-transitive digraphs and semiregular
automorphisms,
{\em European J. Combin.} {\bf 19} (1998), 707-–712.
\bibitem{PSV13} P.~Poto\v cnik, P.~Spiga and G.~Verret,
Cubic vertex-transitive graphs on up to $1280$ vertices,
{\em J.~Symbolic Computation} {\bf 50} (2013), 465--477.
\bibitem{PX93} C.~E.~Praeger and M.~Y.~Xu,
Vertex-primitive graphs of order a product of two distinct primes,
{\em J.~Combin. Theory, Ser.~B} {\bf 59} (1993), 245--266.
\bibitem{Sab} G.~Sabidussi,
On a class of fixed-point-free graphs.
{\em Proc. Amer. Math. Soc.} {\bf 9} (1958), 800--804.
\bibitem{V15} G.~Verret,
Arc-transitive graphs of valency $8$ have a semiregular automorphism,
{\em Ars Math. Contemp.} {\bf 8} (2015), 29--34.
\bibitem{Xu98} M.~Y.~Xu,
Automorphism groups and isomorphisms of Cayley digraphs,
{\em Discrete Math.} {\bf 182} (1998), 309--320.
\end{footnotesize}
\end{thebibliography}
\end{document}