%*********************************************************************************
%       Manuscript       Vertex-transitive direct products       March 2017
%
%	  Revised April 2018
%
%*********************************************************************************

\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.10}{25(2)}{2018}

\usepackage{amsmath, amssymb}
%\usepackage{latexsym}
\usepackage{mathrsfs}
\usepackage{float}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\usepackage{MnSymbol}
\usepackage{tikz} % Tikz package is needed for the graphics.

\begin{document}

\title{Vertex-transitive direct products of graphs}

\author{Richard H.~Hammack\thanks{Supported by Simons Foundation Collaboration Grant for Mathematicians 523748.}\\
\small Department of Mathematics\\[-0.8ex]
\small Virginia Commonwealth University\\[-0.8ex] 
\small Richmond, Virginia U.S.A.\\
\small\tt rhammack@vcu.edu\\
\and
Wilfried Imrich\\
\small Dept.~of Mathematics and Information Technology\\[-0.8ex]
\small Montanuniversit\"at Leoben\\[-0.8ex]
\small  Leoben, Austria\\
\small\tt wilfried.imrich@unileoben.ac.at}

\dateline{May 3, 2017}{Apr 4, 2018}{Apr 27, 2018}
\MSC{05C76, 05C75}
\Copyright{The authors. Released under the CC BY-ND license (International 4.0).}


\maketitle

\begin{abstract}
It is known that for graphs $A$ and $B$ with odd cycles, the
direct product $A\times B$ is vertex-transitive if and only if both
$A$ and $B$ are vertex-transitive. But this is not
necessarily true if one of $A$ or $B$ is bipartite,
and until now there has been no characterization
of such vertex-transitive direct products.
We prove that if $A$ and $B$ are both bipartite, or both
non-bipartite, then $A\times B$ is vertex-transitive if and
only if both $A$ and $B$ are vertex-transitive.
Also, if $A$ has an odd cycle and $B$ is
bipartite, then $A\times B$ is
vertex-transitive if and only if both $A\times K_2$ and $B$ are
vertex-transitive.
\end{abstract}


%\begin{keyword}
%graph direct product \sep bipartite graphs \sep vertex-transitive graph
%\end{keyword}

%\end{frontmatter}


\section{Introduction}
\label{Section:Intro}

Our graphs are finite, without multiple edges, but may
have loops. The set of isomorphism classes of graphs
that may have loops is denoted $\Gamma_0$, while
$\Gamma$ denotes those without loops. Thus
$\Gamma\subset \Gamma_0$. We denote the complete graph
on $n$ vertices as $K_n$, whereas $K_n^*$ is
$K_n$ with a loop added to each vertex.
The automorphism group of a graph $G$ is denoted as ${\rm Aut}(G)$.
We say~$G$ is {\bf vertex-transitive} if for any two vertices $x,y\in V(G)$,
there is a $\varphi \in \mbox{Aut}(G)$ for which $\varphi(x)=y$.

Recall that the {\bf direct product} of two graphs $A,B$
in $\Gamma_0$ or $\Gamma$ is the graph $A\times B$ with
vertices $V(A)\times V(B)$ and edges
\[E(A\times B)=\big\{(a,b)(a',b') \mid
aa'\in E(A) \mbox{ and } bb'\in E(B)\big\}.\]
Figure~\ref{Fig:Direct} shows an example.

%%%%%%%%%%%%  BEGIN FIGURE 1 %%%%%%%%%%%
\begin{figure}[t]
\centering
\begin{tikzpicture}[scale=0.9, style=thick]
\foreach \x in {12} \draw (\x,-0.5)--+(0,1) node [left] {$K_2\;$};
\draw (16,0.5) node {$A\times K_2$};
\draw (13,-0.5)--+(0,1)--+(1,0)--+(2,1)--+(2,0)--+(1,1)--+(0,0);
\draw (13,-1.3)..controls +(-0.7,0.7) and +(-0.7,-0.7)..(13,-1.3);
\draw (15,-1.3)..controls +(0.7,0.7) and +(0.7,-0.7)..(15,-1.3);
\draw (13,-1.3)--+(2,0);
\draw (15.5,-1.3) node [right]  {$A$};
\foreach \x in {12,13,14,15} \foreach \y in {-0.5,0.5} \draw (\x,\y) [fill=white] circle (0.08);
\foreach \x in {13,14,15}  \draw (\x,-1.3) [fill=white] circle (0.08);
\end{tikzpicture}
\caption{The direct product of graphs.}
\label{Fig:Direct}
\end{figure}
%%%%%%%%%%%% END FIGURE 1 %%%%%%%%%%%%%


This product is commutative and associative in the sense that
the maps $(x,y)\mapsto (y,x)$ and $(x,(y,z))\mapsto ((x,y),z)$ are
isomorphisms
$A\times B\to B\times A$ and $A\times(B\times C)\to (A\times B)\times C$.
If $+$ represents disjoint union, then the
distributive law $A\times(B+C)=A\times B +A\times C$ holds,
which is equality of graphs, rather than
just isomorphism.
Recall also Weichsel's theorem~\cite[Theorem~5.9]{HIK}.

\begin{theorem}
\label{Theo:Weichsel}
A direct product $A\times B$ of connected graphs is
connected if and only if at least one factor has an
odd cycle; if both factors are bipartite, then
the product has exactly two components.
In general, if both $A$ and $B$ have odd cycles, then
so does $A\times B$. Moreover, if $B$ is bipartite,
with bipartition $X\cup Y$, then $A\times B$ is
bipartite, with bipartition $V(A)\times X \,\cup\, V(A)\times Y$.
\end{theorem}

It is easy to verify that if $B$ is bipartite,
then $K_2\times B=B+B$.

Note that $G\times K_1^*\cong G$ for any
$G$, so $K_1^*$ is the unit for the direct product. A graph
$G$ is called {\bf prime} over the direct product if it has
more than one vertex, and whenever $G\cong A\times B$,
one of $A$ or $B$ is isomorphic to $G$, and the other is
$K_1^*$. A result of McKenzie~\cite{FACTOR}
implies that any finite, connected non-bipartite graph factors
uniquely into prime graphs over the direct product, up to
order and isomorphism of the factors. See also Chapter 8
of~\cite{HIK}.

A consequence of unique prime factorization of
connected non-bipartite graphs over
the direct product, Theorem 8.19 of~\cite{HIK} states that
any [non-bipartite] direct product is vertex-transitive
if an only if each factor is vertex-transitive.
Unfortunately, the condition of non-bipartiteness was
inadvertently omitted in the statement of Theorem~8.19~\cite{HIK}.
Indeed, the theorem is false for non-bipartite graphs, as
is seen in Figure~\ref{Fig:Direct}, where
$A\times K_2$ is the (vertex-transitive) 6-cycle,
but $A$ is not vertex-transitive.

Until now, no characterization of bipartite vertex-transitive direct
products had been known. In Section~\ref{Section:Main} we give the following
complete characterization.

\medskip
\noindent
{\bf Theorem~\ref{Theo:Main}.} {\em If $A$ and $B$ are both bipartite or both non-bipartite, then
$A\times B$ is vertex-transitive
if and only if both $A$ and $B$ are vertex-transitive.
If $A$ has an odd cycle and $B$ is bipartite, then $A\times B$ is
vertex-transitive if and only if both $A\times K_2$ and $B$ are
vertex-transitive.}
\medskip

One direction of this theorem is elementary,
and follows from our next proposition.
\begin{proposition}
\label{Prop:EasyDirection}
If both $A$ and $B$ are vertex-transitive graphs,
then $A\times B$ is vertex-transitive.
If both $A\times K_2$ and $B$ are vertex-transitive,
and $B$ is bipartite, then $A\times B$ is vertex-transitive.
\end{proposition}

\begin{proof}
For the first statement, suppose both $A$ and $B$ are
vertex-transitive.
Given two vertices $(a,b)$ and $(a',b')$ of
$A\times B$, select automorphisms $\alpha$ of $A$ and
$\beta$ of $B$ for which $\alpha(a)=a'$ and $\beta(b)=b'$.
%{\sk (In case $a=a'$ (resp.\ $b=b'$), $\alpha$ (resp.\ $\beta$)  can be selected as the identity.)}
By the definition of the direct product,
$(x,y)\mapsto(\alpha(x),\beta(y))$
is an automorphism of $A\times B$ sending $(a,b)$ to $(a',b')$,
so $A\times B$ is vertex-transitive.

For the second statement, suppose both $A\times K_2$ and $B$ are vertex-transitive
and $B$ is bipartite. Then the above paragraph implies that
$(A\times K_2)\times B$ is vertex-transitive. But
\[(A\times K_2)\times B\cong A\times (K_2\times B)\cong
A\times (B+B)= A\times B+A\times B,\]
which is to say that the graph consisting of two copies of $A\times B$ is
vertex-transitive. Then certainly each copy of $A\times B$
is vertex-transitive.
\end{proof}

The converse of our main theorem is
more subtle, and some machinery is needed
to attack it. To this end,
Section~\ref{Section:Cartesian} reviews
the Cartesian product of graphs, and their unique prime
factorizations.
This
is followed by sections on $R$-thinness and Cartesian skeletons.
Section~\ref{Section:Main} proves our main theorem.
There we will need the Lov\'{a}sz
cancellation laws:

\begin{theorem}[Lov\'{a}sz~\cite{LOVASZ}]
\label{Theorem:Lovasz}
Suppose $A, B$ and $C$ are graphs, and $C$ has at least one edge.
Then $A\times C\cong B\times C$ implies $A\cong B$ provided that
\vspace{-0.1in}
\begin{itemize}
\setlength\itemsep{-5pt}
\item $C$ has an odd cycle, or
%\item there are homomorphisms $A\to C$ and $B\to C$, or
\item $A$ and  $B$ are both bipartite.
\end{itemize}
\end{theorem}

But before reviewing further preliminaries, some examples
will put our results in context. Example 1 involves a factor with loops, Example 2 a disconnected
factor without loops, and Example 3 involves a connected factor without loops.

\begin{example}
The graph $A$ in Figure~\ref{Fig:Direct} is not vertex-transitive.
However, the figure shows that $A\times K_2$ is vertex-transitive.
If $B$ is a bipartite vertex-transitive graph
(such as the 4-cycle), then $A\times B$ is vertex-transitive
by Proposition~\ref{Prop:EasyDirection}.
So here we have a vertex-transitive product $A\times B$, where $A$ is not vertex-transitive,
but both $A\times K_2$ and $B$ are.
\end{example}

\begin{example}
The graph $A=C_3+C_6$ is not vertex-transitive because one component is a triangle
and the other is a hexagon. But Figure~\ref{Fig:ExDisconn} shows that
$A\times K_2$ is three copies of a hexagon, which {\it is} vertex-transitive.
If $B$ is a bipartite vertex-transitive graph, then
Proposition~\ref{Prop:EasyDirection} says
$A\times B$ is vertex-transitive.
So $A\times B$ is vertex-transitive, where $A$ is not vertex-transitive,
but both $A\times K_2$ and $B$ are.

%%%%%%%%%%%% BEGIN FIGURE 2 %%%%%%%%%%%%%%%
\begin{figure}[h]
\centering
\begin{tikzpicture}[style=thick, scale=1]
\def\vr{2pt}
\draw (0.3,0)--(0.3,1) node [left] {$K_2\;$};
\draw (1,0)--(2,1)--(3,0)--(1,1)--(2,0)--(3,1)--(1,0);
\draw (4,0)--(5,1)--(6,0)--(7,1)--(8,0)--(9,1)--(4,0);
\draw [densely dashed] (4,1)--(5,0)--(6,1)--(7,0)--(8,1)--(9,0)--(4,1);
\draw (1,-0.7)--(3,-0.7)..controls +(0,-0.7) and +(0,-0.7)..(1,-0.7);
\draw (4,-0.7)--(9,-0.7)..controls +(0,-0.7) and +(0,-0.7)..(4,-0.7);
\foreach \x in {0.3,1,2,3,4,5,6,7,8,9} \foreach \y in {0,1} \draw [fill=white] (\x,\y) circle (\vr);
\foreach \x in {1,2,3,4,5,6,7,8,9} \foreach \y in {-0.7} \draw [fill=white] (\x,\y) circle (\vr);
\draw (9.5,-0.7) node {$A$};
\draw (9.25,1) node [right] {$A\times K_2$};
\end{tikzpicture}
\caption{The disconnected graph $A$ is not vertex-transitive, but its product with $K_2$ is.}
\label{Fig:ExDisconn}
\end{figure}
\end{example}
%%%%%%%%%%%%% END FIGURE 2 %%%%%%%%%%%%%%%%

\begin{example}
Figure~\ref{Fig:ExConn} shows a graph $A$ and the product $A\times K_2$.
For brevity, vertices $(x,\varepsilon)$ of $A\times K_2$ are written as $x\varepsilon$, and,
for clarity, edges are encoded dashed, dotted, solid black and solid gray. The dashed outer
hexagon~$H$ in~$A$ corresponds to a subgraph  $H\times K_2=H+H$ in the product,
 which is shown as two dashed copies of~$H$.
Similarly each solid (black or gray) triangle $T$ in~$A$ corresponds to a solid (black or gray) hexagon
$T\times K_2$ in the product.

%%%%%%%%%%%%% BEGIN FIGURE 3 %%%%%%%%%%%%%%%%
\begin{figure}[h]
\centering
\begin{tikzpicture}[style=thick, scale=1]
\def\vr{2pt}
\def\rr{2.5}
\def\rrr{1.75}
\def\rrrr{0.75}
\def\off{-8}
\def\offf{-4.75}

% Radial lines
\foreach \x in{ 30, 90,150,210,270,330} \draw [dotted] (\off,0) +(\x:\rrr)--+(\x:\rrrr);
% Triangle
\foreach \x in{ 90,210,330} \draw [line width=2.2pt, lightgray] (\off,0) +(\x:\rrrr)--+(\x+120:\rrrr);
% Other triangle
\foreach \x in{ 30,150,270} \draw [very thick] (\off,0) +(\x:\rrrr)--+(\x+120:\rrrr);
% Outer Hexagon
\foreach \x in {30, 90,150,210,270,330} \draw [densely dashed] (\off,0) +(\x:\rrr)--+(\x+60:\rrr);
\foreach \x in {30, 90,150,210,270,330} \foreach \y in {\rrr, \rrrr} \draw (\off,0) +(\x:\y) [fill=white] circle (\vr);

\draw (\off,0) node {$A$};
\draw (0,0) node {$A\times K_2$};
{\small
\draw (\off,0) +(90:\rrr+0.3) node {$a$};
\draw (\off,0) +(30:\rrr+0.3) node {$b$};
\draw (\off,0) +(-30:\rrr+0.3) node {$c$};
\draw (\off,0) +(-90:\rrr+0.3) node {$d$};
\draw (\off,0) +(-150:\rrr+0.3) node {$e$};
\draw (\off,0) +(150:\rrr+0.3) node {$f$};

\draw (\off,0) +(75:1.2*\rrrr) node {$0$};
\draw (\off,0) +(15:1.2*\rrrr) node {$1$};
\draw (\off,0) +(-45:1.2*\rrrr) node {$2$};
\draw (\off,0) +(-105:1.2*\rrrr) node {$3$};
\draw (\off,0) +(-165:1.2*\rrrr) node {$4$};
\draw (\off,0) +(132:1.2*\rrrr) node {$5$};
}

\draw (-5.75,0) node {\Large $\times$};

% Draw K_2
\draw (\offf,-0.75)--(\offf,0.75);
\foreach \y in {0.75} \draw (\offf,\y) [fill=black] circle (\vr);
\foreach \y in {-0.75} \draw (\offf,\y) [fill=white] circle (\vr);
\draw (\offf, 0.9) node [above] {\small $1$};
\draw (\offf, -0.9) node [below] {\small $0$};
\draw (-3.75,0) node {\Large $=$};

% Draw non-hexagon edges
\foreach \x in {7.5, 37.5, ...,352.5} \draw [dotted] (\x:\rr)--(\x+15:\rr);
% Draw hexagon
\draw [densely dashed] (7.5:\rr)--(7.5+105:\rr)--(7.5+120:\rr)--(7.5+225:\rr)--(7.5+240:\rr)--(7.5+345:\rr)--(7.5+360:\rr);
% Draw hexagon
\draw  [line width=2.2pt, lightgray] (37.5:\rr)--(37.5+105:\rr)--(37.5+120:\rr)--(37.5+225:\rr)--(37.5+240:\rr)--(37.5+345:\rr)--(37.5+360:\rr);
% Draw hexagon
\draw [densely dashed] (67.5:\rr)--(67.5+105:\rr)--(67.5+120:\rr)--(67.5+225:\rr)--(67.5+240:\rr)--(67.5+345:\rr)--(67.5+360:\rr);
%\draw twisted hexagon
\draw [very thick] (82.5:\rr)--(82.5+135:\rr)--(82.5+120:\rr)--(82.5+255:\rr)--(82.5+240:\rr)--(82.5+375:\rr)--(82.5:\rr);
\foreach \x in {7.5, 37.5, ...,352.5} \draw [fill=white](\x:\rr) circle (\vr);
\foreach \x in {-7.5, -37.5,...,-352.5} \draw (\x:\rr) [fill=black] circle (\vr);

{\small
\draw (7.5:\rr+0.4) node {$c0$};
\draw (7.5+15:\rr+0.4) node {$21$};
\draw (7.5+30:\rr+0.4) node {$40$};
\draw (7.5+45:\rr+0.4) node {$e1$};
\draw (7.5+60:\rr+0.4) node {$d0$};
\draw (7.5+75:\rr+0.4) node {$31$};
\draw (7.5+90:\rr+0.4) node {$10$};
\draw (7.5+105:\rr+0.4) node {$b1$};
\draw (7.5+120:\rr+0.4) node {$a0$};
\draw (7.5+135:\rr+0.4) node {$01$};
\draw (7.5+150:\rr+0.4) node {$20$};
\draw (7.5+165:\rr+0.4) node {$c1$};
\draw (7.5+180:\rr+0.4) node {$b0$};
\draw (7.5+195:\rr+0.4) node {$11$};
\draw (7.5+210:\rr+0.4) node {$50$};
\draw (7.5+225:\rr+0.4) node {$f1$};

\draw (7.5+240:\rr+0.4) node {$e0$};
\draw (7.5+255:\rr+0.4) node {$41$};
\draw (7.5+270:\rr+0.4) node {$00$};
\draw (7.5+285:\rr+0.4) node {$a1$};
\draw (7.5+300:\rr+0.4) node {$f0$};
\draw (7.5+315:\rr+0.4) node {$51$};
\draw (7.5+330:\rr+0.4) node {$30$};
\draw (7.5+345:\rr+0.4) node {$d1$};
}
\end{tikzpicture}
\caption{The graph $A$ is not vertex-transitive, but its product with $K_2$ is.}
\label{Fig:ExConn}
\end{figure}
%%%%%%%%%%%%% END FIGURE 3 %%%%%%%%%%%%%%%%

The graph $A$ is not vertex-transitive because some of its
vertices are on triangles and others are not.  But the product $A\times K_2$
{\it is} vertex-transitive, though seeing this may take a moment of reflection.
Note that the permutation $\pi=(a\, b\, c\, d\, e\, f)(0 \,1\, 2 \,3 \,4\, 5)$ that rotates $A$ by
$60^\circ$ induces
an automorphism $x\varepsilon\mapsto \pi(x)\varepsilon$ of $A\times K_2$ that sends the
``twisted'' solid black hexagon to the ``untwisted'' solid gray hexagon.

Also the following automorphism of order 2 exchanges the two dashed
hexagons in the product with the two solid hexagons.
\[\begin{array}{cccccc c cccccc}
a0 & b1 & c0 & d1 & e0 & f1& \mbox{\rule{0.2in}{0in}} & a1 & b0 & c1 & d0 & e1 & f0\\
\updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & 
&
\updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow \\
01 & 40 & 21 & 00 & 41 & 20 & & 30 & 11 & 50 & 31 & 10 & 51 
\end{array}\]
 The other symmetries are more transparent, arising from
rotations and reflections of the product's drawing.

Now, if $B$ is a bipartite vertex-transitive graph,
then $A\times B$ is vertex-transitive
by Proposition~\ref{Prop:EasyDirection}.
So we have a vertex-transitive product $A\times B$, where $A$ is not vertex-transitive,
but both $A\times K_2$ and $B$ are.
\end{example}

Now we cover the preliminary material needed to prove
our main theorem, Theorem~\ref{Theo:Main}. We begin with the Cartesian product.

\section{The Cartesian Product}
\label{Section:Cartesian}
%Our proof of Conjecture~\ref{Conj:Main} uses the Cartesian product of graphs.
The {\it Cartesian product} of two graphs $A,B\in\Gamma$ is the graph $A\Box B\in\Gamma$ with
vertices $V(A)\times V(B)$ and edges
\[E(A\Box B)=\big\{(a,b)(a',b') \mid
aa'\in E(A) \mbox{ and } b=b', \mbox { or }  a=a' \mbox{ and } bb'\in E(B)\big\}.\]
(See Figure~\ref {Fig:Cartesian}.)
The Cartesian product is commutative and associative in the sense that
$A\Box B\cong B\Box A$ and $A\Box(B\Box C)\cong (A\Box B)\Box C$.
Letting $B+C$ denote the disjoint union of graphs $B$ and $C$, we
also get the distributive law
\begin{equation}
\label{EqnDist}
A\Box(B+C)=A\Box B+A\Box C,
\end{equation}
which is true equality, rather than mere isomorphism.

%%%%%%%%%%%% BEGIN FIGURE 4 %%%%%%%%%%%%%%%
\begin{figure}[H]
\centering
\begin{tikzpicture}[style=thick, scale=1.2]
\def\vr{2pt}
\foreach \y in {0,1,2,3} \draw (1,\y)--(4,\y);
\foreach \x in {0,1,2,3,4} \draw (\x,1)--(\x,3);
\foreach \x in {0,1,2,3,4} \draw (\x,1)..controls +(-0.4,1)..+(0,2);
\foreach \y in {0,1,2,3} \draw (2,\y)..controls +(1,0.4)..+(2,0);
\foreach \x in {1,2,3,4} \draw (\x,0) [fill=white] circle (\vr);
\foreach \y in {1,2,3} \draw (0,\y) [fill=white] circle (\vr);
\foreach \x in {1,2,3,4} \foreach \y in {1,2,3} \draw (\x,\y) [fill=white] circle (\vr);
\draw (4.1,0) node [right] {$A$};
\draw (0,3.1) node [above] {$B$};
\draw (4,3) node [above right] {$A\Box B$};
\end{tikzpicture}
\caption{Cartesian product of graphs.}
\label{Fig:Cartesian}
\end{figure}
%%%%%%%%%%%%% END FIGURE 4 %%%%%%%%%%%%%%%%


Clearly $K_1\Box A\cong A$ for any graph $A$, so $K_1$ is the unit
for the Cartesian product.
A nontrivial graph $G$ is {\it prime over $\Box$} if for any factoring $G\cong A\Box B$,
one of $A$ or $B$ is $K_1$ and the other is $G$. Certainly every finite graph can be
factored into prime factors in $\Gamma$. Sabidussi and Vizing
\cite{SAB,VIZ} proved that this prime factorization is unique for connected graphs.
 % has a unique prime factoring.
%up to order and isomorphism
%of the factors.
More precisely, we have the following.

\begin{theorem}[Theorem 6.8 of \cite{HIK}]
\label{Prop:Cartesian:Iso}
Let $G, H\in\Gamma$ be isomorphic connected graphs with
$G=G_1\Box \cdots\Box G_k$ and $H=H_1\Box\cdots\Box H_\ell$, where
the factors $G_i$ and $H_i$ are prime.
Then $k=\ell$, and for any isomorphism $\varphi:G\to H$, there is a permutation
$\pi$ of $\{1,2,\ldots,\ell\}$ and isomorphisms $\varphi_i:G_{\pi(i)}\to H_i$
for which
\[\varphi(x_1,x_2,\ldots,x_\ell)=
\big(\varphi_1(x_{\pi(1)}),  \varphi_2(x_{\pi(2)}), \ldots,
\varphi_\ell(x_{\pi(\ell)})\big).\]
\end{theorem}

Notice that cancellation is a consequence of unique prime factorization:
For connected graphs, $A\Box C\cong B\Box C$ implies $A\cong B$.
(Cancellation holds also for disconnected graphs, but we shall not need
this stronger result.)

\pagebreak

%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\section{$R$-Thin Graphs}
\label{Section:Thin}
The notion of so-called $R$-thinness is an important issue in
factorings over the direct product. McKenzie~\cite{FACTOR} uses this idea
(in a somewhat more general form), citing an earlier
use by Chang~\cite{CHANG}. In other contexts, $R$-thin graphs have been
called {\it worthy} graphs~\cite{WILSON}.
See Chapter 8 of~\cite{HIK} for proofs of the assertions made in this section.

A graph $G$ is $R$-{\it thin} if no two vertices have the same open neighborhood,
that is, if $N_G(x)=N_G(y)$ implies $x=y$. Said differently, any vertex is uniquely
determined by its open neighborhood.

More generally, we form a relation $R$ on the vertices of an arbitrary graph.
Two vertices $x$ and $y$ of $G$ are
in {\em relation $R$}, written $xRy$, precisely if their open neighborhoods are
identical, that is, if $N_G(x)=N_G(y)$. It is easy
to check that $R$ is an equivalence relation on
$V(G)$.

%(For example,  the equivalence classes for $A\times B$
%in Figure~\ref{Fig:Layers}
%are $\{b1\}$, $\{b2\}$, $\{a1, c1\}$ and $\{a2, c2\}$; those of $A$ are $\{a,c\}$ and $\{b\}$,
%and those of $B$ are $\{1\}$ and $\{2\}$.)
%A graph is then $R$-thin if and only if each equivalence class contains exactly one vertex.

%+++++++++++++++++++++++++
%\begin{figure}[t]
%\centering
%\begin{tikzpicture}[scale=0.7,style=thick]
%\def\vr{2.8pt} % \vr = vertex radius;  Set \vr = 2/scale for uniform sizing of vertices
%\def\sr{2.5pt}
%\foreach \x in {0,8} \draw  (\x,1)--+(0,2);
%\foreach \x in {1,3} \draw   (\x,-0.1)--+(2,0);
%\foreach \x in {1,3} \draw (\x,1)--+(2,2);
%\foreach \x in {1,3} \draw  (\x,3)--+(2,0);
%\foreach \x in {1,3} \draw  (\x,3)--+(2,-2);
%\draw (0,3)..controls +(-1,1) and +(1,1)..+(0,0);
%\draw (8,3)..controls +(-1,1) and +(1,1)..+(0,0);
%\draw (9.8,-0.1)--+(2,0) (9.8,1)--+(2,2)--+(0,2)--+(2,0);
%\foreach \x in {0,1,3,5, 8, 9.8,11.8} \foreach \y in {1,3} \draw (\x,\y) [fill=white] circle (\vr);
%\foreach \x in {1,3,5, 9.8,11.8}   \draw (\x,-0.1) [fill=white] circle (\vr);
%{\footnotesize
%\draw (1,3.5) node {$a2$}  (3,3.5) node {$b2$} (5,3.5) node {$c2$};
%\draw (1,0.6) node {$a1$}  (3,0.6) node {$b1$} (5,0.6) node {$c1$};
%\draw (1,-0.5) node {$a$}  (3,-0.5) node {$b$} (5,-0.5) node {$c$};
%\draw (-0.4,3) node {$2$} (8,3)  node [left] {$\{2\}$};
%\draw (-0.4,1) node {$1$} (8,1)  node [left] {$\{1\}$};
%\draw (9.8,-0.1) node [left] {$\{b\}$} (11.8,-0.1) node [right] {$\{a,c\}$};
%\draw (9.8,1) node [left] {$\{b1\}$} (11.8,1) node [right] {$\{a1,c1\}$};
%\draw (9.8,3) node [left] {$\{b2\}$} (11.8,3) node [right] {$\{a2,c2\}$};
%}
%{\small
%\draw (0,4.2) node {$B$} (8,4.2) node {$B/R$};
%\draw (5.1,-0.1) node [right] {$A$} (13.1,-0.1) node [right] {$A/R$};
%\draw  (10.6,4.2) node [right] {$(A\times B)/R$};
%\draw  (3.8,4.2) node [right] {$A\times B$};
%}
%\end{tikzpicture}
%\caption{Graphs $A,B$ and $A\times B$ (left), and quotients $A/R, B/R$ and
%$(A\times B)/R$ (right).}
%\label{Fig:Layers}
%\end{figure}
%+++++++++++++++++++++++++

%This transposition is possible because
%$a2$ and $c2$ have the same neighborhood.
%Evidently, then, vertices with identical neighborhoods complicate the
%discussion of prime factorizations over the direct product. To overcome this difficulty,

An $R$-equivalence class of a graph is called an
{\bf R-class}.
Given two $R$-classes $X$ and $Y$ (not necessarily distinct), it
is easy to check that either every vertex in $X$ is adjacent to every vertex in $Y$,
or no vertex in $X$ is adjacent to any in $Y$. In particular, this means that
an $R$-class $X$ of $G$ induces either a complete subgraph
$K_n^*$ or a totally disconnected subgraph
$\overline{K_n^*}$.

As the relation $R$ is defined entirely in terms of adjacencies, it is clear that given
an isomorphism $\varphi:G\to H$ we have $xRy$ in $G$ if and only if
$\varphi(x)R\,\varphi(y)$ in $H$.
Thus $\varphi$ maps $R$-classes of~$G$ bijectively to $R$-classes of $H$.

Take any vertex $x$ of a vertex-transitive graph $G$, and say $x$
belongs to the $R$-class $X$. Because an automorphism
$\varphi$ of $G$ carries $R$-classes to $R$-classes, the $R$-class containing
$\alpha(x)$ has $|X|$ vertices. Thus, by vertex-transitivity, all $R$-classes of $G$ have size $|X|$.

Given a graph $G$, we define a quotient graph $G/R$ (in $\Gamma_0$)
whose vertex set is the
set of  $R$-classes of $G$,
and for which two classes are adjacent if they are joined by an edge of $G$.
(And a single class carries a loop provided that an edge of $G$ has both
endpoints in that class.)
%Figure~\ref{Fig:Layers} shows quotients $A/R$, $B/R$ and $(A\times B)/R$.
If $G$ is $R$-thin, then $G/R\cong G$.
An easy check confirms that $G/R$ is $R$-thin for any $G\in\Gamma_0$.

Any automorphism $\varphi:G\to G$ induces an automorphism $G/R\to G/R$
defined as $X\mapsto \varphi(X)$. Conversely, if all $R$-classes have the same
size, then we can lift any automorphism $\varphi:G/R\to G/R$ to an automorphism
of $G$ by simply declaring that each $R$-class $X$ maps to $\alpha(X)$ by an
arbitrary bijection. Moreover, if $x$ and $y$ are two
vertices in the same $R$-class, then
transposition of $x$ with $y$ is an
automorphism of $G$. This implies a lemma.

\begin{lemma}
\label{Lemma:Thin}
If a graph $G$ is vertex-transitive, then $G/R$ is vertex-transitive. If
$G/R$ is vertex-transitive, and all $R$-classes of $G$ have the same size, then $G$
is vertex-transitive.
\end{lemma}

Because $N_{A\times B}(a,b)=N_A(a)\times N_B(b)$, it follows that the $R$-classes
of $A\times B$ are precisely the sets $X\times Y$, where $X$ is an $R$-class of $A$,
and $Y$ is an $R$-class of $B$.  In fact, the map $(A\times B)/R\to A/R\times B/R$
given by $X\times Y\mapsto (X,Y)$ is an isomorphism,
as is proved in Section~8.2 of~\cite{HIK}. Thus
$A\times B$ is $R$-thin if and only if both $A$ and $B$ are.

Note also that $G$ is bipartite if and only if $G/R$ is
bipartite. 

We will use these ideas frequently, sometimes without comment.

%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\section{The Cartesian Skeleton}
\label{Section:Skeleton}
We now recall the definition of the Cartesian skeleton $S(G)$ of an arbitrary graph $G$ in
$\Gamma_0$. The Cartesian skeleton $S(G)$ is a graph on the vertex set of $G$ that has the property $S(A\times B)=S(A)\Box S(B)$ in the class of $R$-thin graphs,
thereby linking the direct and Cartesian products.

We construct $S(G)$ as a certain subgraph of the Boolean square of $G$.
The {\bf Boolean square}  of  $G$ is the graph $G^s$ with $V(G^s)=V(G)$
and $E(G^s)=\{xy \mid  N_G(x)\cap N_G(y)\neq \emptyset\}$. Thus, $xy$ is an edge of $G^s$
whenever $G$ has an $x,y$-walk of length two.
%For instance, if $p\geq 3$, then
%$K_p^s=K_p^*$ (i.e., $K_p$ with a loop added to each vertex). Also, $K_2^s=K_1^*+K_1^*$
%and $K_1^s=K_1$.
The left side of Figure~\ref{Fig:Skel} shows graphs $A,B$ and $A\times B$ (bold)
together with their Boolean squares $A^s,B^s$ and $(A\times B)^s$ (dotted).


If $G$ has an $x,y$-walk $W$ of even length, then $G^s$ has an $x,y$-walk
of length $|W|/2$ on alternate vertices of $W$. Thus $G^s$ is connected if
$G$ is connected and has an odd cycle. (An odd cycle guarantees an even
walk between any two vertices.) On the other hand, if $G$ is connected and bipartite, then
$G^s$ has exactly two components, whose vertex sets are the two partite sets of $G$.

We now show how to form $S(G)$ as a certain spanning subgraph of $G^s$.
Consider an arbitrary factorization $G\cong A\times B$, by which we
identify each vertex of $G$ with an ordered pair $(a,b)$.
We say that an edge $(a,b)(a',b')$ of $G^s$ is
{\bf Cartesian}
relative to the factorization $A\times B$ if either $a=a'$ and $b\ne b'$, or
$a\ne a'$ and $b=b'$. For example, in Figure~\ref{Fig:Skel} edges $xz$ and $zy$ of $G^s$
are Cartesian (relative to the factorization $A\times B$), but edges $xy$ and $yy$ of
$G^s$ are not Cartesian.
We make $S(G)$ from $G^s$ by removing the edges of $G^s$ that are not
Cartesian, but we do this in a way that does not reference the factoring $A\times B$ of $G$.
We next identify two intrinsic criteria for a non-loop edge of
$G^s$ that tell us if
it may fail to be Cartesian relative to some factoring of~$G$.


%%%%%%%%%%%%% BEGIN FIGURE 5 %%%%%%%%%%%%%%%%
\begin{figure}[bh]
\centering
\begin{tikzpicture}[scale=1.5, style=thick]
\def\vr{1.4pt} % \vr = vertex radius;  Set \vr = 2/scale for uniform sizing of vertices
\draw [line width=1pt] (4,1)--(2,3)--(1,2)--(2,1)--(4,3) (1,3)--(3,1)--(4,2)--(3,3)--(1,1);
\draw  [line width=1pt] (1,3)--(2,4)--(3,3)--(4,4);
\draw  [line width=1pt] (1,4)--(2,3)--(3,4)--(4,3);
\draw  [line width=1pt] (0,1)--(0,4) node [above] {$B$}  (1,0)--(4,0) node [right] {$A$};
\foreach \y in {0,1,2,3,4}
\draw [densely dotted] (1,\y) .. controls +(1,-.3) .. (3,\y) (2,\y) .. controls +(1,-.3) .. (4,\y);
\foreach \x in {0,1,2,3,4} \foreach \y in {1,2}
\draw [densely dotted] (\x,\y) .. controls +(-0.4,1) .. (\x,\y+2);
\foreach \x in {1,2} \foreach \y in {1,2} \draw [densely dotted] (\x,\y).. controls +(0.7,1.3)..(\x+2,\y+2);
\foreach \x in {1,2} \foreach \y in {3,4} \draw [densely dotted] (\x,\y).. controls +(0.7,-1.3)..(\x+2,\y-2);
{\footnotesize
\draw (1.05,1.1) node [right] {$x'$} (2.05,1.05) node [right] {$x$}
(1.25,3.1) node {$z'$}  (2.2,3.05) node {$z$} (3.25,3.05) node {$y'$}  (4.2,3.05) node {$y$};
\foreach \x in {1,2,3,4} \foreach \y in {0,3,4} \draw [densely dotted] (\x,\y)..controls +(-.3,.5) and +(.3,.5)..(\x,\y);
\foreach \x in {1,2,3,4} \foreach \y in {1,2} \draw [densely dotted] (\x,\y)..controls +(-.3,-.5) and +(.3,-.5)..(\x,\y);
}
\foreach \y in {1,2,3,4} \draw [densely dotted] (0,\y)..controls +(.5,-.4) and +(.5,.4)..(0,\y);
\foreach \x in {0,1,2,3,4} \foreach \y in {1,2,3,4} \draw (\x, \y) [line width=1pt, fill=white] circle (\vr);
\foreach \x in {1,2,3,4}  \draw (\x, 0) [line width=1pt, fill=white] circle (\vr);
\end{tikzpicture}
\hspace{0.25cm}
\begin{tikzpicture}[style=thick, scale=1.5]
\def\vr{1.4pt} % \vr = vertex radius;  Set \vr = 2/scale for uniform sizing of vertices
\draw [line width=1pt] (4,1)--(2,3)--(1,2)--(2,1)--(4,3) (1,3)--(3,1)--(4,2)--(3,3)--(1,1);
\draw  [line width=1pt] (1,3)--(2,4)--(3,3)--(4,4);
\draw  [line width=1pt] (1,4)--(2,3)--(3,4)--(4,3);
\draw  [line width=1pt] (0.3,1)--(0.3,4) node [above] {$B$}  (1,0)--(4,0) node [right] {$A$};
\foreach \y in {0,1,2,3,4}
\draw [densely dotted] (1,\y) .. controls +(1,-.3) .. (3,\y) (2,\y) .. controls +(1,-.3) .. (4,\y);
\foreach \x in {0.3,1,2,3,4} \foreach \y in {1,2}
\draw [densely dotted] (\x,\y) .. controls +(-0.4,1) .. (\x,\y+2);
\foreach \x in {0.3,1,2,3,4} \foreach \y in {1,2,3,4} \draw (\x, \y) [line width=1pt, fill=white] circle (\vr);
\foreach \x in {1,2,3,4}  \draw (\x, 0) [line width=1pt, fill=white] circle (\vr);
\end{tikzpicture}
\caption{Left: graphs $A, B, A\!\times\! B$ and their Boolean squares $A^s, B^s$ and
$(\!A\!\times\!B)^s$ (dotted).
Right: graphs $A, B, A\times B$ and their Cartesian skeletons $S(A), S(B)$ and
$S(A\times B)$ (dotted).}
\label{Fig:Skel}
\end{figure}
%%%%%%%%%%%%% END FIGURE 5 %%%%%%%%%%%%%%%%

\pagebreak
%(Thus the adjacency matrix of $G^s$
%is the Boolean second power of the adjacency matrix of $G$, that is,
%if $G$ has adjacency matrix $A$
%then the matrix of $G^s$ is obtained from $A^2$ by replacing each nonzero entry by 1.)

The criteria are as follows.
(Note that the symbol $\subset$ means {\it proper} inclusion, and the neighborhoods
are neighborhoods of $G$, not $G^s$.)
\begin{itemize}
%\item[(i)] If $xy$ is a loop (i.e. if $x=y$) then $xy$ cannot be Cartesian.
\item[(i)] In Figure \ref{Fig:Skel}, the edge $xy$ of $G^s$ is not Cartesian, and
there is a $z\in V(G)$ with $N_G(x)\cap N_G(y)\subset N_G(x)\cap N_G(z)$ and
$N_G(x)\cap N_G(y)\subset N_G(y)\cap N_G(z)$.
\item[(ii)] In Figure \ref{Fig:Skel}, the edge $x'y'$ of $G^s$ is not Cartesian, and
there is a $z'\in V(G)$ with $N_G(x')\subset N_G(z')\subset N_G(y')$.
\end{itemize}
Our aim is to remove from $G^s$ all edges that meet one of these criteria.
We package the above criteria into the following definition.
An edge $xy$ of $G^s$ is {\bf dispensable} if
$x=y$ or there exists $z\in V(G)$ for which both of the following statements hold.
\begin{itemize}
\item[{(1)}] $N_G(x)\cap N_G(y)\subset N_G(x)\cap N_G(z)\;\;$ or $
\;\;N_G(x)\subset N_G(z)\!\subset N_G(y)$,
\item[{(2)}] $N_G(y)\cap N_G(x)\subset N_G(y)\cap N_G(z)\;\;$ or $\;\;N_G(y)\subset N_G(z)\!\subset N_G(x)$.
\end{itemize}

Observe that the above statements (1) and (2) are symmetric in $x$ and~$y$.
It is easy to check that (i) or (ii) holding for a triple $x,y,z$ is equivalent to
{\it both} of (1) and (2) holding.
Now we come to this section's main definition.
The {\bf Cartesian skeleton} of a graph $G$ is the spanning subgraph $S(G)$ of $G^s$
obtained by removing all dispensable edges from $G^s$.

The right side of Figure \ref{Fig:Skel} is the same as its left side, except all dispensable
edges of $A^s, B^s$ and $(A\times B)^s$ are deleted. Thus the remaining dotted
edges are $S(A), S(B)$ and $S(A\times B)$. Note that although
$S(G)$ was defined without regard to the  factorization $G=A\times B$, we
nonetheless have $S(A\times B)=S(A) \Box S(B)$.
The following  proposition from~\cite{HAMIMR} asserts that this always holds for
$R$-thin graphs.

\begin{proposition}
\label{Prop:Prod}
If $A,B$ are $R$-thin graphs, then $S(A\times B)=S(A)\Box S(B)$,
provided that neither $A$ nor $B$ has any isolated vertices.
This is {\it equality}, not mere isomorphism; the graphs
$S(A\times B)$ and $S(A)\Box S(B)$ have identical vertex and edge sets.
\end{proposition}

As $S(G)$ is defined entirely in terms of the adjacency structure
of $G$, we have the following immediate consequence.% of Definition~\ref{DefSkeleton}.

\begin{proposition}
\label{Prop:SkelMap}
Any isomorphism $\varphi : G\to H$, as a map $V(G)\to V(H)$, is also an isomorphism
$\varphi:S(G)\to S(H)$.
\end{proposition}

We will also need a result concerning connectivity of Cartesian skeletons.
The following result (which does not require $R$-thinness) is from~\cite{HAMIMR}.
(For another proof, see Chapter 8 of~\cite{HIK}.)

\begin{proposition}
\label{Prop:Conn}
Suppose $G$ is connected.
\begin{itemize}
\item[{\em (i)}] If $G$ has an odd cycle, then $S(G)$ is connected.
\item[{\em (ii)}] If $G$ is nontrivial bipartite, then $S(G)$ has two connected
components. Their respective vertex sets
are the two partite sets of $G$.
\end{itemize}
\end{proposition}


%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\section{Main Result}
\label{Section:Main}

The next proposition is the technical heart of this paper, and uses the
material of the previous three sections. It is followed
by (and implies part of)
Theorem~\ref{Theo:Main}, our main characterization
of vertex-transitive direct products.

\begin{proposition}
\label{Prop:ThinVT}
Let $A$ and $B$ be $R$-thin, connected graphs,
either both non-bipartite, or both bipartite.
If $A\times B$ is vertex-transitive, then both $A$ and $B$
are vertex-transitive.
\end{proposition}

\begin{proof}
The proof has two parts.
Part 1 proves the result  assuming that
$A$ and $B$ are both non-bipartite.
Part 2 proves it if they are both bipartite.
%Though Part 2 has been previously established (for instance, Theorem 8.19 of~\cite{HIK}),
%it is reproved here (with a new approach) for completeness and self-containment. However, the
%reader who is familiar with the non-bipartite scenario may choose to skip Part 2.

\medskip
\noindent
{\bf Part 1.} Assume $A$ and $B$ are non-bipartite and
$A\times B$ is vertex-transitive. We will prove that $A$ is
vertex-transitive. (The same reasoning works for $B$.)
In what follows, $a,a'\in V(A)$ are two arbitrary vertices.
We will construct  $\theta\in \mbox{Aut}(A)$ with $\theta(a)=a'$.

Fix $b\in V(B)$ and select $\varphi\in \mbox{Aut}(A\times B)$ with $\varphi(a,b)=(a',b)$.
By Proposition~\ref{Prop:SkelMap}, $\varphi$ is also an automorphism
$\varphi: S(A\times B)\to S(A\times B)$, and by Proposition~\ref{Prop:Prod}, it
is an automorphism $\varphi: S(A)\Box S(B)\to S(A)\Box S(B)$.
By Proposition~\ref{Prop:Conn}, $S(A)$ and $S(B)$ are connected.
Form prime factorizations $S(A)=G_1\Box\cdots \Box G_k$, and
$S(B)=G_{k+1}\Box\cdots \Box G_\ell$, so
\begin{eqnarray*}
S(A)\Box S(B) &=&
\overbrace{G_1\Box\cdots \Box G_k}^{S(A)}\;\Box\; \overbrace{G_{k+1}\Box\cdots \Box G_\ell}^{S(B)},
\end{eqnarray*}
We've now coordinatized $S(A)$ and $S(B)$ (hence also $A$ and $B$) so that
\[\begin{array}{ccc}
a=(a_{1},\ldots, a_{k}), &
a'=(a_{1}',\ldots, a_{k}'), &
b=\,(b_{k+1},\ldots, b_\ell)
\end{array}\]
for tuples of $a_{i}, a_{i}'\in V(G_i)$ ($1\leq i\leq k$), and $b_i\in V(G_i)$
($k+1\leq i\leq \ell$). Furthermore,
$\varphi$ is
\begin{eqnarray}
\label{Map:Phi2}
\varphi:(G_1\Box\cdots \Box G_k)\Box ( G_{k+1}\Box\cdots \Box G_\ell)&\longrightarrow &(G_1\Box\cdots \Box G_k)\Box ( G_{k+1}\Box\cdots \Box G_\ell.)
\end{eqnarray}

%\[\begin{array}{cccc}
%a=(a_{1}, a_{2},\ldots, a_{k}), &
%a'=(a_{1}', a_{2}',\ldots, a_{k}'), & \mbox{and} &
%b=\,(b_{k+1},\ldots, b_\ell).
%\end{array}\]
%for tuples of $a_{i}, a_{i}'\in V(G_i)$ ($1\leq i\leq k$), and $b_i\in V(G_j)$
%($k+1\leq i\leq \ell$).

Theorem~\ref{Prop:Cartesian:Iso} applied to
(\ref{Map:Phi2}) says there is a permutation
$\pi$  of $\{1,2,\ldots,\ell\}$ and isomorphisms
$\varphi_{i}:G_{\pi(i)}\to G_i$ for which
\begin{equation}
\label{Map:Phi3}
\mbox{\small
$\!\!\varphi\big((x_1,\ldots, x_k),(x_{k+1},\ldots,x_\ell)\big)=
\Big(\!\big(\varphi_{1}(x_{\pi(1)}),\ldots, \varphi_{k}(x_{\pi(k)})\big),
\big(\varphi_{k+\!1}(x_{\pi(k+\!1)}),\ldots,
\varphi_{\ell}(x_{\pi(\ell)})\big)\!\Big).$}
\end{equation}
If we are lucky, then $\pi$ permutes the
indices $\{1,\ldots, k\}$ among themselves,
and $\{k+1,\ldots, \ell\}$ among {\it themselves}. We can then define
$\theta:A\to A$, as
\begin{eqnarray*}
\theta(x_1,\ldots, x_k)&=&
\big(\varphi_{1}(x_{\pi(1)}),\,  \varphi_{2}(x_{\pi(2)}), \,\ldots,
\varphi_{k}(x_{\pi(k)})\big).
\end{eqnarray*}
It is easy to check (and is proved below)
that $\theta$ is an automorphism of
$A$ sending
$a=(a_{1},\ldots, a_{k})$ to
$a'=(a_{1}',\ldots, a_{k}')$,
as desired.

But in general, $\pi$ will not respect the indices like this,
and constructing~$\theta$ involves more care.
In general, if we decompose $\pi$ into disjoint
cycles, some of them may interchange some indices in
$\{1,\ldots, k\}$ with those in
$\{k+1,\ldots, \ell\}$.
Figure~\ref{Fig:ThetaPhi} illustrates a typical such cycle
$\big(i\;\pi^{\,}(i)\;\pi^2(i)\,\ldots \,\pi^6(i)\big)$ of length 7.

%%%%%%%%%%%%% BEGIN FIGURE 6 %%%%%%%%%%%%%%%%
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=1.08,style=thick]
\foreach \x in {0,1,3,5,8,9,11} \draw [fill=lightgray,color=lightgray] (\x,0)--+(0,-0.5)--+(1,-0.5)--+(1,0);
\draw (0,0)--(7,0)--(7,-0.5)--(0,-0.5)--(0,0);
\draw (7.1,0)--(12,0)--(12,-0.5)--(7.1,-0.5)--(7.1,0);
\foreach \x in {1,2,3,4,5,6,8,9,10,11} \draw (\x,0)--+(0,-0.5);
\foreach \x in {2.5,4.5, 6.5,7.5,10.5} \draw (\x,-0.25) node {$\cdots$};
{\small
%\draw (-0.5,-0.25) node {$\varphi$};
\draw (0.5,-0.25) node {$G_{\pi^4(i)}$};
\draw (5.5,-0.25) node {$G_i$};
\draw (8.5,-0.25) node {$G_{\pi(i)}$};
\draw (9.5,-0.25) node {$G_{\pi^{2}(i)}$};
\draw (11.5,-0.25) node {$G_{\pi^{3}(i)}$};

\draw (1.5,-0.25) node {$G_{\pi^{5}(i)}$};
\draw (3.5,-0.25) node {$G_{\pi^{6}(i)}$};
\draw (1.4,0.65) node {\small $\varphi_{\pi^{4}(i)}$};
\draw (2.6,0.75) node {$\varphi_{\pi^{5}(i)}$};
\draw (4.6,0.75) node {$\varphi_{\pi^{6}(i)}$};
\draw (7.1,0.75) node {$\varphi_{i}$};
\draw (8.9,0.75) node {$\varphi_{\pi^{\,}(i)}$};
\draw (10.1,0.75) node {$\varphi_{\pi^{2}(i)}$};
\draw (6,1.15) node {$\varphi_{\pi^{3}(i)}$};
}
\draw [<-,>=stealth] (0.6,0.02)..controls +(0,0.65) and +(0,0.65)..(1.4,0.0);
\draw [<-,>=stealth] (1.6,0.02)..controls +(0,0.7) and +(0,0.7)..(3.4,0.0);
\draw [<-,>=stealth] (3.6,0.02)..controls +(0,0.7) and +(0,0.7)..(5.4,0.0);
\draw [<-,>=stealth] (5.6,0.02)..controls +(0,0.7) and +(0,0.7)..(8.4,0.0);
\draw [<-,>=stealth] (8.6,0.02)..controls +(0,0.65) and +(0,0.65)..(9.4,0.0);
\draw [<-,>=stealth] (9.6,0.02)..controls +(0,0.7) and +(0,0.7)..(11.4,0.0);
\draw [<-,>=stealth] (11.6,0.02)..controls +(0,1.7) and +(0,2.05)..(0.25,0.0);

\draw (3.5,-0.9) node {$\underbrace{\mbox{\rule{2.9in}{0in}}}_{S(A)}$};
\draw (9.5,-0.9) node {$\underbrace{\mbox{\rule{2in}{0in}}}_{S(B)}$};

\end{tikzpicture}
\caption{Effect of $\varphi$ on coordinates corresponding to a typical cycle of $\pi$
}
\label{Fig:ThetaPhi}
\end{figure}
%%%%%%%%%%%%% END FIGURE 6 %%%%%%%%%%%%%%%%

To control such mixing of coordinates, we define a {\bf stacking operation} on
$V(A\times B)$.  This  will allow us to modify $\varphi$ so
its $S(A)$ coordinate functions do not depend on  the factors of $S(B)$.
The idea, introduced in~\cite{HAMMACK3},
takes an input vertex $(x,y_0)\in V(A\times B)$, applies~$\varphi$
to get $\varphi(x,y_0)=(x_1,y_1)$, then
replaces the $x_1$ with $x$.
\[\begin{array}{llllll}
\multicolumn{6}{l}{\mbox{{\bf Stacking Operation}}}  \\
& 0. & \mbox{Begin with input vertex} &
(x,\;y_0)& \in & V\big(S(A)\Box S(B)\big)=V(A\times B) \\
& 1. &  \mbox{Apply $\varphi$:} &
(x_1,y_1)& \in & V\big(S(A)\Box S(B)\big)=V(A\times B)\\
& 2. &  \mbox{Replace $x_1$ with $x$:} &
(x,\;y_1)& \in & V\big(S(A)\Box S(B)\big)=V(A\times B) \\
\end{array}\]

The stacking operation sends a vertex $(x,y_0)$ to an output~$(x,y_1)$,
to which we can again apply the stacking operation to get
$(x,y_2)$, etc. This process yields a sequence
\begin{equation}
(x,y_0), (x,y_1), (x,y_2), (x,y_3),\ldots .
\label{Sequence}
\end{equation}
For example, let's trace this sequence with $x=(r,s,\ldots, t, \ldots, u,\ldots)$, and where we
only consider those coordinates which correspond to the cycle of $\pi$ indicated in
Figure~\ref{Fig:ThetaPhi}. The first five terms are as
follows, where for typographical efficiency we use the abbreviations
$\bar{r}=\varphi_{\pi^3(i)}(r)$ as well as $\bar{\bar{r}}=\varphi_{\pi^2(i)}\circ\varphi_{\pi^3(i)}(r)$
and $\bar{\bar{\bar{r}}}=\varphi_{\pi(i)}\circ\varphi_{\pi^2(i)}\circ\varphi_{\pi^3(i)}(r)$.


%%%%%%%%%%%%% BEGIN FIGURE 7 %%%%%%%%%%%%%%%%
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=1,style=thick]
\foreach \x in {0,1,3,5,8,9,11} \draw [fill=lightgray,color=lightgray] (\x,0)--+(0,-0.5)--+(1,-0.5)--+(1,0);
\draw (0,0)--(7,0)--(7,-0.5)--(0,-0.5)--(0,0);
\draw (7.1,0)--(12,0)--(12,-0.5)--(7.1,-0.5)--(7.1,0);
\foreach \x in {1,2,3,4,5,6,8,9,10,11} \draw (\x,0)--+(0,-0.5);
\foreach \x in {2.5,4.5, 6.5,7.5,10.5} \draw (\x,-0.25) node {$\cdots$};
{\small
\draw (-1.8,-0.25) node [right, white] {$(u_0,v_0)=$};
\draw (2.6,0.75) node {$\varphi_{\pi^{5}(i)}$};
\draw (4.6,0.75) node {$\varphi_{\pi^{6}(i)}$};
\draw (7.1,0.75) node {$\varphi_{i}$};
\draw (8.8,0.75) node {$\varphi_{\pi^{\,}(i)}$};
\draw (10.1,0.75) node {$\varphi_{\pi^{2}(i)}$};
\draw (5.9,1.1) node {$\varphi_{\pi^{3}(i)}$};
}
\draw [<-,>=stealth] (0.6,0.02)..controls +(0,0.65) and +(0,0.65)..(1.4,0.0);
\draw [<-,>=stealth] (1.6,0.02)..controls +(0,0.7) and +(0,0.7)..(3.4,0.0);
\draw [<-,>=stealth] (3.6,0.02)..controls +(0,0.7) and +(0,0.7)..(5.4,0.0);
\draw [<-,>=stealth] (5.6,0.02)..controls +(0,0.7) and +(0,0.7)..(8.4,0.0);
\draw [<-,>=stealth] (8.6,0.02)..controls +(0,0.65) and +(0,0.65)..(9.4,0.0);
\draw [<-,>=stealth] (9.6,0.02)..controls +(0,0.7) and +(0,0.7)..(11.4,0.0);
\draw [<-,>=stealth] (11.6,0.02)..controls +(0,1.75) and +(0,1.9)..(0.4,0.0);
\end{tikzpicture}

\noindent
\begin{tikzpicture}[scale=1,style=thick]
\foreach \x in {0,1,3,5,8,9,11} \draw [fill=lightgray,color=lightgray] (\x,0)--+(0,-0.5)--+(1,-0.5)--+(1,0);
\draw (0,0)--(7,0)--(7,-0.5)--(0,-0.5)--(0,0);
\draw (7.1,0)--(12,0)--(12,-0.5)--(7.1,-0.5)--(7.1,0);
\foreach \x in {1,2,3,4,5,6,8,9,10,11} \draw (\x,0)--+(0,-0.5);
\foreach \x in {2.5,4.5, 6.5,7.5,10.5} \draw (\x,-0.25) node {$\cdots$};
{\small
\draw (-1.8,-0.25) node [right] {$(x,y_0)=$};
\draw (0.5,-0.25) node {$r$};
\draw (5.5,-0.25) node {$u$};
\draw (8.5,-0.25) node {$*$};
\draw (9.5,-0.25) node {$*$};
\draw (11.5,-0.25) node {$*$};
\draw (1.5,-0.25) node {$s$};
\draw (3.5,-0.25) node {$t$};
}
\end{tikzpicture}

\noindent
\begin{tikzpicture}[scale=1,style=thick]
\foreach \x in {0,1,3,5,8,9,11} \draw [fill=lightgray,color=lightgray] (\x,0)--+(0,-0.5)--+(1,-0.5)--+(1,0);
\draw (0,0)--(7,0)--(7,-0.5)--(0,-0.5)--(0,0);
\draw (7.1,0)--(12,0)--(12,-0.5)--(7.1,-0.5)--(7.1,0);
\foreach \x in {1,2,3,4,5,6,8,9,10,11} \draw (\x,0)--+(0,-0.5);
\foreach \x in {2.5,4.5, 6.5,7.5,10.5} \draw (\x,-0.25) node {$\cdots$};
{\small
\draw (-1.8,-0.25) node [right] {$(x,y_1)=$};
\draw (0.5,-0.25) node {$r$};
\draw (1.5,-0.25) node {$s$};
\draw (3.5,-0.25) node {$t$};
\draw (5.5,-0.25) node {$u$};
\draw (8.5,-0.25) node {$*$};
\draw (9.5,-0.25) node {$*$};
\draw (11.5,-0.25) node {$\bar{r}$};
}
\end{tikzpicture}

\noindent
\begin{tikzpicture}[scale=1,style=thick]
\foreach \x in {0,1,3,5,8,9,11} \draw [fill=lightgray,color=lightgray] (\x,0)--+(0,-0.5)--+(1,-0.5)--+(1,0);
\draw (0,0)--(7,0)--(7,-0.5)--(0,-0.5)--(0,0);
\draw (7.1,0)--(12,0)--(12,-0.5)--(7.1,-0.5)--(7.1,0);
\foreach \x in {1,2,3,4,5,6,8,9,10,11} \draw (\x,0)--+(0,-0.5);
\foreach \x in {2.5,4.5, 6.5,7.5,10.5} \draw (\x,-0.25) node {$\cdots$};
{\small
\draw (-1.8,-0.25) node [right] {$(x,y_2)=$};
\draw (0.5,-0.25) node {$r$};
\draw (1.5,-0.25) node {$s$};
\draw (3.5,-0.25) node {$t$};
\draw (5.5,-0.25) node {$u$};
\draw (8.5,-0.25) node {$*$};
\draw (9.5,-0.25) node {$\bar{\bar{r}}$};
\draw (11.5,-0.25) node {$\bar{r}$};
}
\end{tikzpicture}

\noindent
\begin{tikzpicture}[scale=1,style=thick]
\foreach \x in {0,1,3,5,8,9,11} \draw [fill=lightgray,color=lightgray] (\x,0)--+(0,-0.5)--+(1,-0.5)--+(1,0);
\draw (0,0)--(7,0)--(7,-0.5)--(0,-0.5)--(0,0);
\draw (7.1,0)--(12,0)--(12,-0.5)--(7.1,-0.5)--(7.1,0);
\foreach \x in {2.5,4.5, 6.5,7.5,10.5} \draw (\x,-0.25) node {$\cdots$};
\foreach \x in {1,2,3,4,5,6,8,9,10,11} \draw (\x,0)--+(0,-0.5);
{\small
\draw (-1.8,-0.25) node [right] {$(x,y_3)=$};
\draw (0.5,-0.25) node {$r$};
\draw (1.5,-0.25) node {$s$};
\draw (3.5,-0.25) node {$t$};
\draw (5.5,-0.25) node {$u$};
\draw (8.5,-0.25) node {$\bar{\bar{\bar{r}}}$};
\draw (9.5,-0.25) node {$\bar{\bar{r}}$};
\draw (11.5,-0.25) node {$\bar{r}$};
}
\end{tikzpicture}

\noindent
\begin{tikzpicture}[scale=1,style=thick]
\foreach \x in {0,1,3,5,8,9,11} \draw [fill=lightgray,color=lightgray] (\x,0)--+(0,-0.5)--+(1,-0.5)--+(1,0);
\draw (0,0)--(7,0)--(7,-0.5)--(0,-0.5)--(0,0);
\draw (7.1,0)--(12,0)--(12,-0.5)--(7.1,-0.5)--(7.1,0);
\foreach \x in {2.5,4.5, 6.5,7.5,10.5} \draw (\x,-0.25) node {$\cdots$};
\foreach \x in {1,2,3,4,5,6,8,9,10,11} \draw (\x,0)--+(0,-0.5);
{\small
\draw (-1.8,-0.25) node [right] {$(x,y_4)=$};
\draw (0.5,-0.25) node {$r$};
\draw (1.5,-0.25) node {$s$};
\draw (3.5,-0.25) node {$t$};
\draw (5.5,-0.25) node {$u$};
\draw (8.5,-0.25) node {$\bar{\bar{\bar{r}}}$};
\draw (9.5,-0.25) node {$\bar{\bar{r}}$};
\draw (11.5,-0.25) node {$\bar{r}$};
}
\end{tikzpicture}
\caption{The effect of the stacking operation on a typical cycle of $\pi$.}
\label{Fig:Iterations}
\end{figure}
%%%%%%%%%%%%% END FIGURE 7 %%%%%%%%%%%%%%%%

By the third iteration, the coordinates of $y_0$ in this cycle have been ``flushed out''
and replaced (or ``stacked'') with images of $r$. Also, further iterations affect no further changes on
this cycle.  For $M\geq \ell-k$, the terms $(x,y_M)$ of Sequence~\ref{Sequence} agree on
all cycles that permute at least one vertex of $\{1,\ldots,k\}$. (A cycle
permuting only indices in $\{k+1,\ldots,\ell\}$ has not been flushed out.)

Consider now what happens when we apply $\varphi$ to the stacked vertex
$(x,y_M)$. This is shown in Figure~\ref{Fig:PhiFlushed}, with $(x,y_0)$ as in the bottom of Figure~\ref{Fig:Iterations}.
Notice that $\varphi(x, y_M)=\big(\theta(x), \eta(y_M)\big)$,
where $\theta:V(A)\to V(A)$ is a bijection and $\eta(y_M)$ is some vertex of
$S(B)$.

\smallskip
\noindent
{\bf Remark 1:} Note that $\eta$ need not be the identity. If $\pi$ has a non-trivial cycle that
permutes only indices in $\{k+1,\ldots,\ell\}$, then the corresponding coordinates of
$y_M$ do not get stacked, so $\varphi$ may alter these coordinates. 

%%%%%%%%%%%%% BEGIN FIGURE 8 %%%%%%%%%%%%%%%%
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=1.05,style=thick]
{\small
\draw (1.4,0.65) node {\small $\varphi_{\pi^{4}(i)}$};
\draw (2.6,0.75) node {$\varphi_{\pi^{5}(i)}$};
\draw (4.6,0.75) node {$\varphi_{\pi^{6}(i)}$};
\draw (3,1.6) node {$\varphi_i\circ\varphi_{\pi(i)}\circ\varphi_{\pi^2(i)}\circ\varphi_{\pi^3(i)}$};
\draw (8.5,0.9) node {$\mbox{id}$};
\draw (9.5,0.9) node {$\mbox{id}$};
\draw (11.5,0.9) node {$\mbox{id}$};
}
\draw [<-,>=stealth] (0.6,0.02)..controls +(0,0.65) and +(0,0.65)..(1.4,0.0);
\draw [<-,>=stealth] (1.6,0.02)..controls +(0,0.7) and +(0,0.7)..(3.4,0.0);
\draw [<-,>=stealth] (3.6,0.02)..controls +(0,0.7) and +(0,0.7)..(5.4,0.0);
\draw [<-,>=stealth] (8.6,0.02)..controls +(0.7,0.7) and +(-0.7,0.7)..(8.4,0.0);
\draw [<-,>=stealth] (9.6,0.02)..controls +(0.7,0.7) and +(-0.7,0.7)..(9.4,0.0);
\draw [<-,>=stealth] (11.6,0.02)..controls +(0.7,0.7) and +(-0.7,0.7)..(11.4,0.0);

\draw [<-,>=stealth] (5.6,0.02)..controls +(0,1.75) and +(0,1.9)..(0.4,0.0);

\foreach \x in {0,1,3,5,8,9,11} \draw [fill=lightgray,color=lightgray] (\x,0)--+(0,-0.5)--+(1,-0.5)--+(1,0);
\draw (0,0)--(7,0)--(7,-0.5)--(0,-0.5)--(0,0);
\draw (7.1,0)--(12,0)--(12,-0.5)--(7.1,-0.5)--(7.1,0);
\foreach \x in {2.5,4.5, 6.5,7.5,10.5} \draw (\x,-0.25) node {$\cdots$};
\foreach \x in {1,2,3,4,5,6,8,9,10,11} \draw (\x,0)--+(0,-0.5);
{\small
\draw (-1.8,-0.25) node [right] {$(x,y_M)=$};
\draw (0.5,-0.25) node {$r$};
%\draw (1.5,-0.25) node {$s$};
%\draw (3.5,-0.25) node {$t$};
%\draw (5.5,-0.25) node {$u$};
\draw (8.5,-0.25) node {$\bar{\bar{\bar{r}}}$};
\draw (9.5,-0.25) node {$\bar{\bar{r}}$};
\draw (11.5,-0.25) node {$\bar{r}$};
}

\draw (3.5,-0.9) node {$\underbrace{\mbox{\rule{2.9in}{0in}}}_{S(A)}$};
\draw (9.5,-0.9) node {$\underbrace{\mbox{\rule{2in}{0in}}}_{S(B)}$};
\end{tikzpicture}
\caption{The effect of $\varphi$ on a stacked vertex $(x,y_M)$.}
\label{Fig:PhiFlushed}
\end{figure}
%%%%%%%%%%%%% END FIGURE 8 %%%%%%%%%%%%%%%%

\noindent
{\bf Remark 2:} Our cycle $\big(\pi^4(i), \pi^5(i), \pi^6(i),i, \pi(i), \pi^2(i), \pi^3(i)\big)$ of figures~\ref{Fig:ThetaPhi}, \ref{Fig:Iterations} and~\ref{Fig:PhiFlushed}
has a string of entries between $1$ and $k$, followed by a string
between $k+1$ and $\ell$. In general a cycle of $\pi$ may alternate between
these two types of strings numerous times. Notice that in such a case coordinates
of $S(B)$ still get stacked with images coordinates of $S(A)$.

\smallskip
Since $\varphi(a,b)=(a',b)$,
the stacking operation does not alter $(a,b)$.
After $M$ iterations we still have
$(a,b_M)=(a,b)$, so
$(a',b)=\varphi(a,b)=\varphi(a, b_M)=(\theta(a), \eta(b_M))$.
This implies
\begin{equation}
\theta(a)=a'.
\label{Eqn:Theta2}
\end{equation}

To complete Part 1, we just need to show $\theta\in{\rm Aut}(A)$.
Take $xy\in E(A)$. We claim
$\theta(x)\theta(y) \in E(A)$. Fix $bb'\in E(B)$, so that
$(x,b)(y,b')\in E(A\times B)$. Apply the stacking operation on the two endpoints, in
parallel.
\[\begin{array}{llllll}
%\multicolumn{6}{l}{\mbox{{\bf Stacking Operation}}}  \\
& 0. & \mbox{Begin with input edge:} &
(x,b)(y,b')& \in & E(A\times B) \\
& 1. &  \mbox{Apply $\varphi$ to endpoints:} &
(x_1,b_1)(y_1,b_1')& \in & E(A\times B)\\
& 2. &  \mbox{Replace $x_1$ with $x$, and $y_1$ with $y$:} &
(x,b_1)(y,b_1')& \in & E(A\times B)
\end{array}\]
After $M\geq \ell-k$ iterations, we have $(x,b_M)(y,b_M') \in  E(A\times B)$.
Applying $\varphi$ to both endpoints gives
$\big(\theta(x), \eta(b_M)\big)\big(\theta(y),\eta(b_M')\big) \in  E(A\times B)$.
Thus $\theta(x)\theta(y)\in E(A)$, meaning $\theta:A\to A$
is a bijective homomorphism, hence  also an automorphism because $A$ is finite.

In summary, $\theta\in {\rm Aut}(A)$, and
$\theta(a)=a'$ by Equation~(\ref{Eqn:Theta2}).
This means $A$ is vertex-transitive.
Because the direct product is commutative, it follows that the other factor
$B$ is also vertex transitive.

\medskip
\noindent
{\bf Part 2.} Assume $A$ and $B$ are bipartite and
$A\times B$ is vertex-transitive. We will show $A$ is
vertex-transitive. (And thus so is $B$, by commutativity of $\times$.)
To begin, we analyze skeletons. Proposition~\ref{Prop:Conn}
implies $S(A)=A_0+A_1$ is the disjoint union of two graphs
whose respective vertex sets are the partite sets of $A$.
Similarly $S(B)=B_0+B_1$. Thus
\begin{eqnarray*}
S(A\times B)=S(A)\Box S(B)&=&(A_0+A_1)\Box(B_0+B_1)\\
&=&A_0\Box B_0+A_0\Box B_1+A_1\Box B_0+A_1\Box B_1.
\end{eqnarray*}
This is illustrated in Figure~\ref{Fig:BipProd}.
By Weichsel's theorem, $A\times B$ is bipartite and has two
components. One component has as partite sets the vertices
of $A_0\Box B_0$ and $A_1\Box B_1$, and the other component's
partite sets are the vertices of $A_0\Box B_1$ and $A_1\Box B_0$.


%%%%%%%%%%%%% BEGIN FIGURE 9 %%%%%%%%%%%%%%%%
\begin{figure}[H]
\centering
\begin{tikzpicture}[style=thick, scale=0.9]
\draw (2,1.1)--+(2,2) (2,1.5)--+(1.5,1.5) (2,2)--+(1.5,1.5);
\draw (2.5,3.6)--+(2,-2) (2,3)--+(2,-2) (2.5,3)--+(2,-2);
\draw (2.1,0.4)--(3.5,0.2) (2.1,0.5)--(3.5,0.5) (3.5,0.1)--(2.1,0.1)--(3.5,0.4);
\draw (0.4,2)--(0.2,3) (0.5,2)--(0.5,3) (0.1,3)--(0.1,2)--(0.4,3);
\foreach \x in {1,3.4} \foreach \y in {1,3} \draw [fill=white]
(\x,\y)--+(1.5,0)--+(1.5,1.2)--+(0,1.2)--+(0,0);

\foreach \x in {1,3.4} \draw [fill=white]
(\x,0)--+(1.5,0)--+(1.5,0.7)--+(0,0.7)--+(0,0);
\foreach \y in {1,3} \draw [fill=white]
(0,\y)--+(0,1.2)--+(0.6,1.2)--+(0.6,0)--+(0,0);

{\small
\draw (0.3,1.3) [fill=black] circle (2pt) node [above] {$b$};
\draw (1.3,1.3) [fill=black] circle (2pt) node [right] {{\footnotesize $(a,\!b)$}};
\draw (3.7,1.3) [fill=black] circle (2pt) node [right] {{\footnotesize $(a'\!,\!b)$}};
\draw (1.3,0.2) [fill=black] circle (2pt) node [above] {$a$};
\draw (3.7,0.2) [fill=black] circle (2pt) node [above] {$a'$};
}
\foreach \x in {0,1} \draw (2*\x+1.8,-0.3) node {\small $A_\x$};
\foreach \x in {0,1} \draw (-0.3,2*\x+1.6) node {\small $B_\x$};
\draw (5,0.3) node {$A$};
\draw (0.3,4.55) node {$B$};
\draw (5.8,2.5) node {$A\times B$};
\draw (4.15,3.7) node {$A_1\!\Box\! B_1$};
\draw (1.75,3.7) node {$A_0\!\Box\! B_1$};
\draw (4.15,1.9) node {$A_1\!\Box\! B_0$};
\draw (1.75,1.9) node {$A_0\!\Box\! B_0$};
\draw [<-,>=stealth] (2.5,3.8)..controls +(0.3,0.1) and +(-0.3,0.1)..+(0.9,0);
\draw  (2.95,3.9) node [above] {$\psi_1$};
\draw [->,>=stealth] (2.5,1.35)..controls +(0.3,-0.1) and +(-0.3,-0.1)..+(0.9,0);
\draw  (2.95,1) node {$\psi_0$};
\end{tikzpicture}
\caption{The effect of $\varphi$ on a direct product of two connected bipartite graphs $A$ and $B$.}
\label{Fig:BipProd}
\end{figure}
%%%%%%%%%%%%% END FIGURE 9 %%%%%%%%%%%%%%%%

As $A\times B$ is vertex-transitive, it has automorphisms mapping
any of its partite sets to any other, so by
Proposition~\ref{Prop:SkelMap}, the four skeleton components
$A_0\Box B_0$, $A_0\Box B_1$, $A_1\Box B_0$ and $A_1\Box B_1$
are all isomorphic to one other.
By cancellation, $A_0\cong A_1$ and $B_0\cong B_1$.

Let $a,a'\in V(A)$. We will produce an automorphism
$\theta$ of $A$ with $\theta(a)=a'$. Notice that it suffices to prove this for
$a$ and $a'$ in different partite sets of $A$. For if this is established and
$a,a'$ are in the same partite set, then we can take an $a''$ in the opposite partite set.
The composition of two automorphisms mapping $a\mapsto a''$ and
$a''\mapsto a'$  is an automorphism of $A$ mapping $a$ to $a'$.
Thus assume $a\in V(A_0)$ and $a'\in V(A_1)$.
Fix some $b\in V(B_0)$, and let
$\varphi$ be an automorphism of $A\times B$ with
$\varphi(a,b)=(a',b)$. 
(See Figure~\ref{Fig:BipProd}.)
From this we will now construct $\theta\in\mbox{Aut}(A)$ with $\theta(a)=a'$.

The map $\varphi$ restricts to isomorphisms
$\psi_1:A_1\Box B_1\to A_0\Box B_1$ and
$\psi_0:A_0\Box B_0\to A_1\Box B_0$, which, together,
send one component of $A\times B$ to the other.
(See Figure~\ref{Fig:BipProd}.)
%Let's agree to modify $\varphi$ (if necessary) so that on the
%other component it restricts to
%$\varphi_1^{-1}:A_0\Box B_1\to A_1\Box B_1$ and
%$\varphi_1^{-1}:A_1\Box B_0\to A_0\Box B_0$. That is,
%we can assume $\varphi$ is an involution that swaps the
%two components of $A\times B$.

Prime factor $A_0$ as $A_0=G_1\Box\cdots \Box G_k$, and $B_0$ as
$B_0=G_{k+1}\Box\cdots \Box G_\ell$. As $A_1\cong A_0$
and $B_1\cong B_0$,
we can label the vertices of $A_1$ and $B_1$ so that they also have
prime factorizations $A_1=G_1\Box\cdots \Box G_k$ and
$B_1=G_{k+1}\Box\cdots \Box G_\ell$.
Then
{\small
\[\begin{array}{ll}
A_0\!\Box\! B_1 =
\overbrace{G_1\Box\cdots \Box G_k}^{A_0}\;\Box\; \overbrace{G_{k+1}\Box\cdots \Box G_\ell}^{B_1},&
A_1\!\Box\! B_1 =
\overbrace{G_1\Box\cdots \Box G_k}^{A_1}\;\Box\; \overbrace{G_{k+1}\Box\cdots \Box G_\ell}^{B_1},\\
A_0\!\Box\! B_0 =
\overbrace{G_1\Box\cdots \Box G_k}^{A_0}\;\Box\; \overbrace{G_{k+1}\Box\cdots \Box G_\ell}^{B_0},&
A_1\!\Box\! B_0 =
\overbrace{G_1\Box\cdots \Box G_k}^{A_1}\;\Box\; \overbrace{G_{k+1}\Box\cdots \Box G_\ell}^{B_0},
\end{array}\]
}
and our restricted isomorphisms  $\psi_1$ and $\psi_0$  are
{\small
\begin{eqnarray}
\label{Map:PhiX2}
\psi_1:(G_1\Box\cdots \Box G_k)\;\Box\; (G_{k+1}\Box\cdots \Box G_\ell)&\longrightarrow &(G_1\Box\cdots \Box G_k)\;\Box\; (G_{k+1}\Box\cdots \Box G_\ell),\\
\label{Map:PhiY2}
\psi_0:(G_1\Box\cdots \Box G_k)\;\Box\; (G_{k+1}\Box\cdots \Box G_\ell )&\longrightarrow
& (G_1\Box\cdots \Box G_k)\;\Box\; (G_{k+1}\Box\cdots \Box G_\ell).
\end{eqnarray}
}
We have now coordinatized $A_0$, $A_1$, $B_0$ and $B_1$ (hence also $A\times B$) so that
\[\begin{array}{ccc}
a=(a_{1},\ldots, a_{k}), &
a'=(a_{1}',\ldots, a_{k}'), &
b=\,(b_{k+1},\ldots, b_\ell)
\end{array}\]
for tuples of $a_{i}, a_{i}'\in V(G_i)$ ($1\leq i\leq k$), and $b_i\in V(G_i)$
($k+1\leq i\leq \ell$).

Theorem~\ref{Prop:Cartesian:Iso} applied to
(\ref{Map:PhiX2}) and~(\ref{Map:PhiY2}) yields permutations
$\pi$ and $\sigma$ of $\{1,\ldots,\ell\}$ and isomorphisms
$\varphi_{i}:G_{\pi(i)}\to G_i$
and
$\varphi_{i}':G_{\sigma(i)}\to G_i$
so that
\begin{eqnarray}
\label{Map:PhiX3}
\mbox{\small $\psi_1\big((x_1,\ldots x_k),(x_{k+1},\ldots,x_\ell)\big)=
\big((\varphi_{1}(x_{\pi(1)}),\ldots, \varphi_{k}(x_{\pi(k)})),
(\varphi_{k\!+\!1}(x_{\pi(k\!+\!1)}), \,\ldots,\,
\varphi_{\ell}(x_{\pi(\ell)}))\big),$}\\
\label{Map:PhiY3}
\mbox{\small $\psi_0\big((x_1,\ldots x_k),(x_{k+1},\ldots,x_\ell)\big)=
\big((\varphi_{1}'(x_{\sigma(1)}),\ldots, \varphi_{k}'(x_{\sigma(k)})),
(\varphi_{k\!+\!1}'(x_{\sigma(k\!+\!1)}), \,\ldots,\,
\varphi_{\ell}'(x_{\sigma(\ell)}))\big).$}
\end{eqnarray}

Consider the effect of $\psi_1$ on a typical cycle of $\pi$, say a cycle
$(i,\pi(i), \pi^2(i), \ldots, \pi^6(i))$ of length 7, similar to that of
 Figure~\ref{Fig:ThetaPhi} (except that this time the map is
 $A_1\Box B_1\to A_0\Box B_1$ rather than $S(A)\Box S(B)\to S(A)\Box S(B)$).
 This is represented schematically in
Figure~\ref{Fig:ThetaPhi2}.

%%%%%%%%%%%%% BEGIN FIGURE 10 %%%%%%%%%%%%%%%%
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=1.08,style=thick]
\foreach \x in {0,1,3,5,8,9,11} \foreach \y in {0,2}\draw [fill=lightgray,color=lightgray] (\x,\y)--+(0,-0.5)--+(1,-0.5)--+(1,0);
\draw (0,2)--(7,2)--(7,1.5)--(0,1.5)--(0,2);
\draw (0,0)--(7,0)--(7,-0.5)--(0,-0.5)--(0,0);
\draw (7.1,2)--(12,2)--(12,1.5)--(7.1,1.5)--(7.1,2);
\draw (7.1,0)--(12,0)--(12,-0.5)--(7.1,-0.5)--(7.1,0);
\foreach \x in {1,2,3,4,5,6,8,9,10,11}  \foreach \y in {0,2} \draw (\x,\y)--+(0,-0.5);
\foreach \x in {2.5,4.5, 6.5,7.5,10.5}  \foreach \y in {0,2} \draw (\x,\y-0.25) node {$\cdots$};
{\small
%\draw (-0.5,-0.25) node {$\varphi$};
\foreach \y in {0,2} \draw (0.5,\y-0.25) node {$G_{\pi^4(i)}$};
\foreach \y in {0,2} \draw (5.5,\y-0.25) node {$G_i$};
\foreach \y in {0,2} \draw (8.5,\y-0.25) node {$G_{\pi(i)}$};
\foreach \y in {0,2} \draw (9.5,\y-0.25) node {$G_{\pi^{2}(i)}$};
\foreach \y in {0,2} \draw (11.5,\y-0.25) node {$G_{\pi^{3}(i)}$};
\foreach \y in {0,2} \draw (1.5,\y-0.25) node {$G_{\pi^{5}(i)}$};
\foreach \y in {0,2} \draw (3.5,\y-0.25) node {$G_{\pi^{6}(i)}$};

\draw (0,0.35) node {\small $\varphi_{\pi^{4}(i)}$};
\draw (2.1,0.35) node {$\varphi_{\pi^{5}(i)}$};
\draw (4.1,0.35) node {$\varphi_{\pi^{6}(i)}$};
\draw (5.85,0.35) node {$\varphi_{i}$};
\draw (8.05,0.35) node {$\varphi_{\pi^{\,}(i)}$};
\draw (10.05,0.3) node {$\varphi_{\pi^{2}(i)}$};
\draw (11.6,0.5) node {$\varphi_{\pi^{3}(i)}$};
}
\draw [<-,>=stealth] (0.5,0)..controls +(0,1) and +(-0.5,-0.5)..(1.5,1.5);
\draw [<-,>=stealth] (1.5,0)..controls +(0,1.1) and +(-0.5,-0.5)..(3.5,1.5);
\draw [<-,>=stealth] (3.5,0)..controls +(0,1.2) and +(-0.5,-0.5)..(5.5,1.5);
\draw [<-,>=stealth] (5.5,0)..controls +(0,1.3) and +(-0.5,-0.5)..(8.5,1.5);
\draw [<-,>=stealth] (8.5,0)..controls +(0,1.4) and +(-0.5,-0.5)..(9.5,1.5);
\draw [<-,>=stealth] (9.5,0)..controls +(0,1.5) and +(-0.5,-0.5)..(11.5,1.5);
\draw [<-,>=stealth] (11.5,0)..controls +(0,1.5) and +(0,-1.5)..(0.5,1.5);

\draw (3.5,2.4) node {$\overbrace{\mbox{\rule{2.9in}{0in}}}^{\mbox{\small $A_1$}}$};
\draw (9.5,2.4) node {$\overbrace{\mbox{\rule{2in}{0in}}}^{\mbox{\small $B_1$}}$};
\draw (3.5,-0.9) node {$\underbrace{\mbox{\rule{2.9in}{0in}}}_{\mbox{\small $A_0$}}$};
\draw (9.5,-0.9) node {$\underbrace{\mbox{\rule{2in}{0in}}}_{\mbox{\small $B_1$}}$};

\end{tikzpicture}
\caption{The effect of $\psi_1$ on coordinates corresponding to a typical cycle of $\pi$.
}
\label{Fig:ThetaPhi2}
\end{figure}
%%%%%%%%%%%%% END FIGURE 10 %%%%%%%%%%%%%%%%

Notice that when we apply the stacking operation to a vertex
$(x,y_0)\in V(A_1\Box B_1)$, we arrive at a vertex $(x,y_1)$
that is still in $V(A_1\Box B_1)$. Furthermore, iterations of the stacking
operation on $(x,y_0)$ are exactly as indicated in Figure~\ref{Fig:Iterations},
and we get a sequence
\[\begin{array}{ll}
(x,y_0), \;\; (x,y_1), \;\; (x,y_2), \;\; \ldots, \;\;(x,y_M) & \mbox{in $A_1\Box B_1$}.
\end{array}\]
As in the first part of the proof, if $M\geq \ell-k$, then, in general, any $j$th coordinate of
$y_M$ for which  $\pi^s(j)\leq k$ (for some $s$) has been flushed out and replaced with the
image of a vertex of some $G_i$ with $1\leq i \leq k$.
It follows that 
$\psi_1(x,y_M)=\big(\theta_1(x), \eta_1(y_M)\big)$, where
$\theta_1:V(A_1)\to V(A_0)$ is a bijection.  (This is illustrated in Figure~\ref{Fig:ThetaPhi3}.)

%%%%%%%%%%%%% BEGIN FIGURE 11 %%%%%%%%%%%%%%%%
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=1.08,style=thick]
\foreach \x in {0,1,3,5,8,9,11} \foreach \y in {0,2}\draw [fill=lightgray,color=lightgray] (\x,\y)--+(0,-0.5)--+(1,-0.5)--+(1,0);
\draw (0,2)--(7,2)--(7,1.5)--(0,1.5)--(0,2);
\draw (0,0)--(7,0)--(7,-0.5)--(0,-0.5)--(0,0);
\draw (7.1,2)--(12,2)--(12,1.5)--(7.1,1.5)--(7.1,2);
\draw (7.1,0)--(12,0)--(12,-0.5)--(7.1,-0.5)--(7.1,0);
\foreach \x in {1,2,3,4,5,6,8,9,10,11}  \foreach \y in {0,2} \draw (\x,\y)--+(0,-0.5);
\foreach \x in {2.5,4.5, 6.5,7.5,10.5}  \foreach \y in {0,2} \draw (\x,\y-0.25) node {$\cdots$};
{\small
\draw (-1.9,1.8) node [right] {$(x,y_M)=$};
\draw (-2.2,-0.25) node [right] {$\psi_1(x,y_M)=$};
%\draw (-0.5,-0.25) node {$\varphi$};
\foreach \y in {2} \draw (0.5,\y-0.25) node {$r$};
\foreach \y in {2} \draw (5.5,\y-0.25) node {$u$};
\foreach \y in {0,2} \draw (8.5,\y-0.25) node {$\bar{\bar{\bar{r}}}$};
\foreach \y in {0,2} \draw (9.5,\y-0.25) node {$\bar{\bar{r}}$};
\foreach \y in {0,2} \draw (11.5,\y-0.25) node {$\bar{r}$};
\foreach \y in {2} \draw (1.5,\y-0.25) node {$s$};
\foreach \y in {2} \draw (3.5,\y-0.25) node {$t$};

\draw (4.6,0.75) node [right] {\small $\varphi_i\!\circ\!\varphi_{\pi(i)}\!\circ\!\varphi_{\pi^2(i)}\!\circ\!\varphi_{\pi^3(i)}$};
\draw (0,0.35) node {\small $\varphi_{\pi^{4}(i)}$};
\draw (2.1,0.35) node {$\varphi_{\pi^{5}(i)}$};
\draw (4.1,0.35) node {$\varphi_{\pi^{6}(i)}$};
%\draw (5.85,0.35) node {$\varphi_{i}$};
\draw (8.5,0.75) node [right] {$\mbox{id}$};
\draw (9.5,0.75) node  [right] {$\mbox{id}$};
\draw (11.5,0.75) node  [right] {$\mbox{id}$};
}
\draw [<-,>=stealth] (0.5,0)..controls +(0,1) and +(-0.5,-0.5)..(1.5,1.5);
\draw [<-,>=stealth] (1.5,0)..controls +(0,1.1) and +(-0.5,-0.5)..(3.5,1.5);
\draw [<-,>=stealth] (3.5,0)..controls +(0,1.2) and +(-0.5,-0.5)..(5.5,1.5);
\draw [<-,>=stealth] (8.5,0)--(8.5,1.5);
\draw [<-,>=stealth] (9.5,0)--(9.5,1.5);
\draw [<-,>=stealth] (11.5,0)--(11.5,1.5);
\draw [<-,>=stealth] (5.5,0)..controls +(0,1.3) and +(0,-1.5)..(0.5,1.5);

\draw (3.5,2.4) node {$\overbrace{\mbox{\rule{2.9in}{0in}}}^{\mbox{\small $A_1$}}$};
\draw (9.5,2.4) node {$\overbrace{\mbox{\rule{2in}{0in}}}^{\mbox{\small $B_1$}}$};
\draw (3.5,-0.9) node {$\underbrace{\mbox{\rule{2.9in}{0in}}}_{\mbox{\small $A_0$}}$};
\draw (9.5,-0.9) node {$\underbrace{\mbox{\rule{2in}{0in}}}_{\mbox{\small $B_1$}}$};

\end{tikzpicture}
\caption{The effect of $\psi_1$ on a stacked vertex.
}
\label{Fig:ThetaPhi3}
\end{figure}
%%%%%%%%%%%%% END FIGURE 11 %%%%%%%%%%%%%%%%

Likewise the stacking operation applied to a vertex
$(w,z_0)\in V(A_0\Box B_0)$ yields a vertex $(w,z_1)\in V(A_0\Box B_0)$.
Applying the stacking operation iteratively  to $(w,z_0)$, gives a sequence
\[\begin{array}{ll}
(w,z_0), \; (w,z_1), \; (w,z_2), \;\,\ldots, \; \;(w,z_M) & \mbox{in $A_0\Box B_0$}.
\end{array}\]
As before,
$\psi_0(w,z_M)=\big(\theta_0(w), \eta_0(z_M)\big)$, for some
bijection $\theta_0:V(A_0)\to V(A_1)$. 

Let $\theta:A\to A$ be the map that restricts to $\theta_0$ on $V(A_0)$ and
$\theta_1$ on $V(A_1)$. Thus $\theta$ reverses the bipartition of $A$.
Because $\varphi(a,b)=(a',b)$, the stacking operation does not alter $(a,b)$. That is,
applying it $M$ times to $(a,b)$ yields $(a,b_M)$ with $b_M=b$. Therefore
\[(a',b)=\varphi(a,b)=\varphi(a,b_M)=\psi_0(a,b_M)=(\theta_0(a), \sigma_0(a,b_M)),\]
which means $\theta_0(a)=a'$, that is, $\theta(a)=a'$.

%But the fact that $\varphi^2=\mbox{id}$ means
%$\pi_1$ and $\pi_0$ have order 2, that is, they are products of disjoint
%transpositions.
%For example, Figure~\ref{Fig:BipartiteStacking} shows the effect of a  typical
%$\varphi$.


%To reach our goal, we define a {\bf stacking operation} on vertices of
%$A\times B$.  This idea, introduced in~\cite{HAMMACK3},
%takes an input vertex $(u,v)\in V(A\times B)$, applies~$\varphi$, then
%throws away the first coordinate and replaces it with $u$.
%\[\begin{array}{llllll}
%\multicolumn{6}{l}{\mbox{{\bf Stacking Operation}}}  \\
%& 0. & \mbox{Begin with input vertex} &
%(u,\;v)& \in & V\big(S(A)\Box S(B)\big)=V(A\times B) \\
%& 1. &  \mbox{Apply $\varphi$:} &
%(u_1,v_1)& \in & V\big(S(A)\Box S(B)\big)=V(A\times B)\\
%& 2. &  \mbox{Replace $u_1$ with $u$:} &
%(u,\;v_1)& \in & V\big(S(A)\Box S(B)\big)=V(A\times B) \\
%\end{array}\]

%Applying the stacking operation to  $(u,v)$ yields an output vertex
%$(u,v_1)$.  The important thing to notice is that the first coordinate of
%$\varphi(u,v_1)$ does not depend of $v_1$.
%For example, let's trace this  with $(u,v)\in V(S(A_1)\Box S(B_1))$, and where we
%only consider those coordinates shown in Figure~\ref{Fig:BipartiteStacking}.
%(Note $\varphi(u,v)=\varphi_1(u,v)$ in this case, so
%refer to the top part of the figure.)



%\bigskip
%Note that $\varphi(u,v_1)=(\theta_1(u), \sigma_1(u,v_1))$, where $\theta_1:V(A_1)\to V(A_0)$
%is a bijection, and $\sigma_1$ is a map $V(A_1\Box B_1)\to V(B_1)$.
%In exactly the same way, if $(u,v)\in V(A_0\Box B_0)$, then applying stacking operation to %this
%vertex gives some $(u,v_1)\in V(A_0\Box B_0)$, and then applying $\varphi$ gives
%$\varphi(u,v_1)=(\theta_0(u),\sigma_0(u,v_1))$ for a bijection $\theta_0:V(A_0)\to V(A_1)$.

%Define a bijection $\theta:V(A)\to V(A)$ to be $\theta_0$ on $V(A_0)$ and $\theta_1$ on $V(A_1)$.



To complete the proof we need to show $\theta\in \mbox{Aut}(A)$.
For this, take an edge $wx\in E(A)$, with $w\in V(A_0)$ and
$x\in V(A_1)$. We claim  $\theta(w)\theta(x)\in E(A)$.
Fix an edge
$z_0y_0$ of $B$ with $z_0\in V(B_0)$ and $y_0\in V(B_1)$,
so $(w,z_0)(x,y_0)$ is an edge of $A\times B$ with
$(w,z_0)\in V(A_0\Box B_0)$ and $(x,y_0)\in V(A_1\Box B_1)$.
Apply the stacking operation on the two endpoints, in
parallel.
\[\begin{array}{llllll}
%\multicolumn{6}{l}{\mbox{{\bf Stacking Operation}}}  \\
& 0. & \mbox{Begin with input edge:} &
(w,z_0)(x,y_0)& \in & E(A\times B) \\
& 1. &  \mbox{Apply $\varphi$ ($\psi_0$ on left, $\psi_1$ on right):} &
(w_1,z_1)(x_1,y_1)& \in & E(A\times B)\\
& 2. &  \mbox{Replace $w_1$ with $w$, and $x_1$ with $x$:} &
(w,z_1)(x,y_1)& \in & E(A\times B) \\
\end{array}\]
Iterating this $M$ times produces an edge $(w,z_M)(x,y_M)\in E(A\times B)$.
Applying $\varphi$ to both endpoints, we get
\[\big(\theta_0(w), \sigma_0(z_M)\big)\big(\theta_1(x),\sigma_1(y_M)\big) \in  E(A\times B).\]
From this, $\theta_0(w)\theta_1(x)\in E(A)$, meaning $\theta(w)\theta(x)\in E(A)$. Thus
$\theta:A\to A$ is a bijective homomorphism, hence  also an automorphism because $A$ is finite.
As $\theta(a)=a'$, the graph $A$ is vertex transitive. The proof is complete.
\end{proof}

We now reach our main theorem.

\pagebreak
\begin{theorem}
\label{Theo:Main}
If $A$ and $B$ are both non-bipartite or both
bipartite, then $A\times B$ is vertex-transitive
if and only if both $A$ and $B$ are vertex-transitive.
If $A$ has an odd cycle and $B$ is bipartite, then $A\times B$ is
vertex-transitive if and only if both $A\times K_2$ and $B$ are
vertex-transitive.
\end{theorem}

\begin{proof}
If both $A$ and $B$ are vertex-transitive,
then Proposition~\ref{Prop:EasyDirection} implies $A\times B$ is vertex-transitive.
By the same proposition, if both $A\times K_2$ and $B$ are vertex-transitive and $B$ is bipartite,
then $A\times B$ is vertex-transitive (as $A\times K_2$ is bipartite).
Thus it remains to prove the converses of the two statements.

First, suppose $A$ and $B$ are non-bipartite, and $A\times B$ is
vertex-transitive. Write $A=A_1+\cdots +A_m$ and
$B=B_1+\cdots +B_m$ as disjoint unions of their components, with
$A_1$ and $B_1$ non-bipartite. Then $A\times B=\sum_{i,j} A_i\times B_j$.
By Weichsel's theorem, $A_i\times B_1$ and
$A_j\times B_1$ are connected for any $i,j$,
so these are two components of $A\times B$.
But as $A\times B$ is vertex-transitive, all
its components are isomorphic, so
$A_i\times B_1\cong A_j\times B_1$ and
$A_i\cong A_j$ by Theorem~\ref{Theorem:Lovasz}.
Thus any two components of $A$ are
isomorphic (and non-bipartite). By the same argument, any two
components of $B$ are isomorphic (and non-bipartite).

In the previous paragraph we remarked that $A_1\times B_1$ is
vertex-transitive.
By Lemma~\ref{Lemma:Thin},
$(A_1\times B_1)/R$ is vertex-transitive, and it is $R$-thin by the remarks in Section~\ref{Section:Thin}.
Because $(A_1\times B_1)/R\cong A_1/R\times B_1/R$, and both
$A_1/R$ and $B_1/R$ are non-bipartite, Proposition~\ref{Prop:ThinVT}
says $A_1/R$ and $B_1/R$ are vertex-transitive.

Now, because all $R$-classes of $A\times B$
have the same size, and each $R$-class of
$A\times B$ is a product of $R$-classes of
$A$ and $B$, respectively, we conclude that
all $R$-classes of $A$ (hence of $A_1$) have the same size, and
all $R$-classes of $B$ (hence of $B_1$) have the same size.
Lemma~\ref{Lemma:Thin} now implies that
$A_1$  and $B_1$ are vertex-transitive. But the components of $A$ are
all isomorphic to $A_1$, so $A$ is vertex-transitive. Likewise, so is
$B$.

Next suppose $A$ and $B$ are both bipartite, and 
$A\times B$ is vertex-transitive.
Again, $A\times B=\sum_{i,j} A_i\times B_j$, and by Weichsel's theorem,
each summand $A_i\times B_i$ has exactly two components.
Because $A\times B$ is vertex-transitive, its components are all
isomorphic, and vertex-transitive themselves, and it
follows that each $A_i\times B_i$ is vertex-transitive.

Thus $A_i\times B_1\cong A_j\times B_1$ for any
$i,j$, so  $A_i\cong A_j$ by Theorem~\ref{Theorem:Lovasz}, that is,
all components of $A$ are isomorphic. Similarly, all
components of $B$ are isomorphic.

By Lemma~\ref{Lemma:Thin},
$(A_1\times B_1)/R$ is vertex-transitive, and it is also $R$-thin.
As $(A_1\times B_1)/R\cong A_1/R\times B_1/R$, 
and $A_1/R$ and $B_1/R$ are both bipartite,
Proposition~\ref{Prop:ThinVT}
implies that both $A_1/R$ and $B_1/R$ are vertex-transitive.

From here, the proof proceeds exactly as in
the non-bipartite case, and we conclude that
both $A_1$ and $B_1$ are vertex-transitive, thus also $A$ and $B$.

For the second statement's converse, let $A$ be non-bipartite, $B$ bipartite, and $A\times B$ vertex-transitive. By
Proposition~\ref{Prop:EasyDirection}, $(A\times B)\times K_2\cong$
$(A\times K_2)\times B$ is vertex-transitive. As $A\times K_2$
and $B$ are bipartite, the first statement of the theorem (proved
above) implies that  $A\times K_2$ and $B$ are vertex-transitive.
\end{proof}

\begin{thebibliography}{99}
%\setlength{\itemsep}{0pt}
\bibitem{CHANG} C.C.~Chang, Cardinal factorization of finite relational structures,
{\it Fund. Math.} {\bf 60} (1967)  251--269.

\bibitem{HAMMACK3} C.~Crenshaw and R.~Hammack, Edge-transitive bipartite
direct products, preprint.

\bibitem{HAMIMR} R.~Hammack and W.~Imrich, On Cartesian skeletons of graphs,
\emph{Ars Math. Contemp.},
  {\bf{2}} (2009) 191--205.


\bibitem{HIK} {\it Handbook of Product Graphs,} second edition, by R.~Hammack,
W.~Imrich and S.~Klav\v{z}ar, 
Series: Discrete Mathematics and Its Applications, CRC Press, Boca Raton, FL, 2011.

\bibitem{LOVASZ} L.~Lov\'{a}sz,  \textit{On the cancellation law among finite relational structures}, Period. Math. Hungar. {\bf 1}(2) (1971) 145--156.

\bibitem{FACTOR} R.~McKenzie, Cardinal multiplication of structures with a reflexive relation,
{\it Fund. Math.} {\bf 70} (1971)  59--101.

\bibitem{SAB} G.~Sabidussi, Graph multiplication, {\em Math. Z.}, {\bf 72} (1960) 446--457.

\bibitem{VIZ} G.V.~Vizing, The Cartesian product of graphs,
{\em Vy\v{c}isl Sistemy}, {\bf 9} (1963) 30--43.

\bibitem{WILSON} S.~Wilson, A worthy family of semisymmetric graphs,
{\it Discrete Math.}, {\bf 271} (2003) 283--294.

\end{thebibliography}

\end{document}



