\documentclass{smjour} \usepackage{graphth} %% for Journal of Graph Theory \usepackage{array} \usepackage{amsfonts} %% need \mathbb{Z} %\usepackage{showkeys} %% delete for final run ??? %% needs format files from John Wiley & Sons Publishers: %% ftp://ftp.wiley.com/public/journals/tex/graphth/ % If you do do not have PostScript fonts, %comment out the next line: \usepackage{smjourps} %%%%%%%%% DELETE THESE BEFORE SUBMITTING TO JGT %%%%%%%%%% ??? \setlength{\textwidth}{6.5 in} \setlength{\textheight}{9.0 in} \voffset=-1.00in \belowtheoremskip=8pt minus .1pt %% too much space in \pmod \renewcommand{\pmod}[1]{\allowbreak \mkern6mu %% was 18mu ({\rm mod}\,\,#1)} %% kill dot at end of section reference ??? %% then put back into thm numbers \def\thesection {\arabic{section}} \makeatletter %% be careful!! \def\@begintheorem#1#2{\ifvmode\vskip-\lastskip\fi \vskip\abovetheoremskip \trivlist \item[\hskip\labelsep\theoremfont{#1\ \/\/% \ifthmsectionnum\thesection.\fi#2}\ifperiodaftertheorem\@thmcountersep\fi]% \let\savetheoremlabel\@currentlabel \def\@currentlabel{\ifthmsectionnum\thesection.\fi\savetheoremlabel}\ \theoremtextfont} \def\@opargbegintheorem#1#2#3{\trivlist \item[\hskip\labelsep{\theoremfont #1\ \/\/% \ifthmsectionnum\thesection.\fi#2\ \ #3\ifperiodaftertheorem\@thmcountersep\fi}]% \def\@currentlabel{\ifthmsectionnum\thesection.\fi\thetheorem}\ \theoremtextfont} \def\@sect#1#2#3#4#5#6[#7]#8{\def\\{\hfill\break}% \ifnum #2>\c@secnumdepth% \let\@svsec\@empty\else% \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\enskip}\fi% \@tempskipa #5\relax% \ifdim \@tempskipa>\z@% \begingroup #6\relax% \@hangfrom{\hskip #3\relax\@svsec}% {\interlinepenalty\@M% \setbox2=\hbox{\hskip #3\relax\@svsec}% \ifnum #2=1 \vtop{\advance\hsize by-\wd2% \parindent=0pt \raggedright% \setbox1=\hbox{\def\\ {\relax}\sectionfont#8}% \ifdim\wd1>.8\textwidth \hsize=\sectionwrap\fi% \hyphenpenalty=10000% \uppercase{#8}}\else#8\fi\par}% \endgroup% \csname #1mark\endcsname{#7}\addcontentsline% {toc}{#1}{\ifnum #2>\c@secnumdepth \else% \protect\numberline{\csname the#1\endcsname.}\fi% #7}\else% \def\@svsechd{#6\hskip #3\relax %% \relax added 2 May 90% \@svsec #8\csname #1mark\endcsname% {#7}\addcontentsline% {toc}{#1}{\ifnum #2>\c@secnumdepth \else% \protect\numberline{\csname the#1\endcsname}\fi% #7}}\fi% \@xsect{#5}\let\\ =\savedblbslash} %% end of killing the dot ??? (and end of CAREFUL section) %%%%%%%%% END OF SECTION TO DELETE %%%%%%%%%% ??? %%%%%%%%% OUR MACRO DEFINITIONS %%%%%%%%%% \newcommand{\qc}{\mathord{\mathcal C}} \newcommand{\qd}{\mathord{\mathcal D}} \newcommand{\qf}{\mathord{\mathcal E}} \newcommand{\arcto}{\mathord{\rightarrow}} \newcommand{\integer}{\mathord{\mathbb{Z}}} \newcommand{\Cay}{\mathop{\rm{Cay}}} \newcommand{\text}[1]{\mbox{\upshape#1}} \newcommand{\see}[1]{(see~\ref{#1})} \newcommand{\pref}[1]{(\ref{#1})} \newcommand{\nonham}[4]{$\Cay(\integer_{#1}; #2,#3,#4)$} %% for list of nonhamiltonians in Figure \ref{nonham-list} \newcounter{case} \renewenvironment{case}{\refstepcounter{case}\em \medskip \noindent Case \textup{\thecase.}}{\upshape} \renewcommand{\thecase}{\arabic{case}} %% ??? \newcounter{subcase}[case] \renewcommand{\thesubcase}{\thecase.\arabic{subcase}} \newenvironment{subcase}{\refstepcounter{subcase}\em \medskip \noindent Subcase \textup{\thesubcase.}}{\upshape} %% ??? %%% Sometimes we want the number of a theorem to be a copy of %%% another theorem number, with an apostrophe added. %%% For example, we use 7.2' to number a copy of Theorem 7.2. %%% We now define an environment to implement this. \makeatletter %% be CAREFUL with this!! \newenvironment{thmref}{\thmrefer}{} \newcommand{\thmrefer}[1]{ \renewcommand{\@currentlabel}{{\protect\ref{#1}$'$}}} \makeatother %% end of CAREFUL section \newtheorem{lem}[theorem]{Lemma} \newtheorem{cor}[theorem]{Corollary} \newtheorem{defn}[theorem]{Definition} \newtheorem{notation}[theorem]{Notation} \newtheorem{conj}[theorem]{Conjecture} \newcommand{\oldendconj}{} \let\oldendconj=\endconj \renewcommand{\endconj}{\qed\oldendconj} %% put QED at end \newtheorem{prop}[theorem]{Proposition} %%%%%%%%% end of our macros %%%%%%%%% \begin{document} \theoremsectionnumbers %%%%% To be entered at Wiley: =====>> \yearofpublication{(Year)} \volume{(Volume Number)} \issuenumber{(Optional Issue Number)} \cccline{(cccline information)} %i.e., \cccline{1042-98329/94/020253-18} %% Uncomment any of the next three if you want to use any one==> %\received{(received)} %\revised{(revised)} %\accepted{(accepted)} \authorrunninghead{(Author Running Head)} \titlerunninghead{(Title Running Head)} \setcounter{page}{1} %% Start each article with a new odd number. %% <<== End of commands to be entered at Wiley %%%%%%%%% DELETE THESE BEFORE SUBMITTING %%%%%%%%%% ??? \setlength{\textwidth}{6.5 in} \setlength{\textheight}{9.0 in} \voffset=-1.00in \def\jfootline{\iftitle\global\titlefalse \vtop to0pt{\everypar={}\leftskip=0pt\rightskip=0pt \vskip12pt \iffootlinehrule% \hrule height .3pt \vskip8pt\else\vskip1sp\fi %% \parindent=0pt \parskip=0pt \parfillskip=0pt \baselineskip=9pt \footlinefont \hbox to \textwidth{Submitted to the Journal of Graph Theory in January 1997. \hfill} \vskip1pt \iffootlinefolio \vskip4pt \hbox to\textwidth{\hfill\foliofont\the\c@page}\fi \vss}\else\hfill\fi} \authorrunninghead{S.~Locke and D.~Witte} \titlerunninghead{Non-hamiltonian circulant digraphs} %% blank headlines are fine \makeatletter \def\jheadline{\hbox to\textwidth{\iftitle\else\ifodd\c@page {\hfill}% \enspace{\foliofont\the\c@page} \else{\foliofont\the\c@page} \enspace\hfill\fi\fi}} \makeatother \def\abstract#1{{\leftskip=\abstractmargin \rightskip=\leftskip \vskip\aboveabstractskip \abstractsize\ifabstractname \abstractnamefont\noindent ABSTRACT\vskip\belowabstractnameskip\fi\abstractfont \noindent#1 { %% don't want the copyright notice } \vskip\belowabstractskip}} %%%%%%%%% END OF SECTION TO DELETE %%%%%%%%%% ??? %% Authors, start here ==>> \title{On non-hamiltonian circulant %%??? linebreak here in final digraphs \\ of outdegree three} \author{Stephen C.~Locke} \affil{Department of Mathematical Sciences, \\ Florida Atlantic University, Boca Raton, FL 33431} \author{Dave Witte} \affil{Department of Mathematics, \\ Oklahoma State University, Stillwater, OK 74078} \abstract{We construct infinitely many connected, circulant digraphs of outdegree three that have no hamiltonian circuit. All of our examples have an even number of vertices, and our examples are of two types: either every vertex in the digraph is adjacent to two diametrically opposite vertices, or every vertex is adjacent to the vertex diametrically opposite to itself.} %% Optional, Keywords % \keywords{} \begin{article} %% Do not remove this command. It is necessary. %% Enter text of article here ===>> \section{Introduction} It is well known (and not difficult to prove) that every connected, circulant graph has a hamiltonian cycle (except the trivial counterexamples on one or two vertices). (See \cite{ChenQuimpo} for much stronger results.) The situation is different in the directed case: some connected, circulant digraphs are not hamiltonian. In general, no good characterization of the hamiltonian circulant digraphs is known. For those of outdegree two, however, R.~A.~Rankin found a simple arithmetic criterion that determines which are hamiltonian. To state this result, we introduce a bit of notation. (In this paper, circulant digraphs are represented as Cayley digraphs on cyclic groups.) \begin{defn} For any natural number~$n$, we use $\integer_n$ to denote the additive cyclic group of integers modulo~$n$. For any set~$A$ of integers, let $\Cay(\integer_n;A)$ be the digraph whose vertex set is~$\integer_n$, and in which there is an arc from~$u$ to~$u+a$ $\pmod{n}$, for every $u \in \integer_n$ and every $a \in A$. A digraph is \emph{circulant} if it is (isomorphic to) $\Cay(\integer_n;A)$, for some choice of~$n$ and~$A$. \end{defn} Note that $\Cay(\integer_n;A)$ is regular, and its outdegree is equal to the cardinality of the generating set~$A$. It is easy to see that $\Cay(\integer_n;A)$ is connected if and only if $\gcd(a_1,a_2,\ldots,a_m,n) = 1$, where $A = \{a_1,a_2,\ldots,a_m\}$. \begin{theorem}[{(Rankin \cite[Thm.~4]{Rankin})}] \label{Rankin-thm} A connected, circulant digraph $\Cay(\integer_n;a,b)$ of outdegree two has a hamiltonian circuit if and only if there are nonnegative integers $s$~and~$t$, such that $s+t = \gcd(sa+tb,n) = \gcd(a-b,n)$. \end{theorem} In contrast, little is known about the hamiltonicity of circulant digraphs of outdegree three (or more). The following theorem provides an interesting class of examples that are hamiltonian. \begin{theorem}[{(Curran-Witte \cite[Thm.~9.1]{CurranWitte})}] \label{CW-thm} Suppose $\Cay(\integer_n;A)$ is connected, and has outdegree at least three. If $\gcd(a,n) \gcd(b_1,b_2,\ldots,b_m) \ge n$, whenever $a,b_1,b_2,\ldots,b_m \in A$ and $a \not\in \{b_1,b_2,\ldots,b_m\}$, then $\Cay(\integer_n;A)$ has a hamiltonian circuit. \end{theorem} One non-hamiltonian example, $\Cay(\integer_{12};3,4,6)$, was found by D.~Witte \cite[p.~301]{WitteGallian}. In this paper, we construct infinitely many non-hamiltonian, connected, circulant digraphs of outdegree three (without loops or multiple arcs). (Figure~\ref{nonham-list} lists examples with less than~$48$ vertices. For brevity, the table does not list $\Cay(\integer_n; xa,xb,xc)$ if it includes $\Cay(\integer_n; a,b,c)$, and $\gcd(x,n) = 1$.) In all of our examples, $n$~is even, and the examples come in two families: either the generating set~$A$ contains the element~$n/2$ of order two in~$\integer_n$ \see{n/2-thmref}, or two of the elements of~$A$ differ by~$n/2$ \see{b+k-thmref}. \begin{figure} \renewcommand{\arraystretch}{1.5} \begin{center} \begin{tabular}{lllll} \nonham{12}{ 2}{ 3}{ 8} & \nonham{28}{ 2}{ 7}{16} & \nonham{36}{ 2}{ 9}{20} & \nonham{42}{ 2}{12}{33} \\ \nonham{12}{ 3}{ 4}{ 6} & \nonham{30}{ 2}{ 3}{18} & \nonham{36}{ 2}{15}{20} & \nonham{42}{ 2}{15}{36} \\ \nonham{18}{ 2}{ 3}{12} & \nonham{30}{ 2}{ 6}{21} & \nonham{36}{ 3}{ 8}{18} & \nonham{42}{ 2}{18}{39} \\ \nonham{18}{ 2}{ 6}{15} & \nonham{30}{ 2}{ 9}{24} & \nonham{40}{ 2}{ 5}{22} & \nonham{42}{ 3}{14}{24} \\ \nonham{20}{ 2}{ 5}{12} & \nonham{30}{ 2}{10}{25} & \nonham{40}{ 4}{ 5}{24} & \nonham{42}{ 6}{ 7}{28} \\ \nonham{24}{ 2}{ 3}{14} & \nonham{30}{ 3}{10}{18} & \nonham{42}{ 2}{ 3}{24} & \nonham{44}{ 2}{11}{24} \\ \nonham{24}{ 2}{ 9}{12} & \nonham{30}{ 5}{ 6}{20} & \nonham{42}{ 2}{ 6}{27} \\ \nonham{24}{ 3}{ 4}{16} & \nonham{36}{ 2}{ 3}{20} & \nonham{42}{ 2}{ 7}{28} \\ \end{tabular} \caption{Non-hamiltonian, connected, circulant digraphs of outdegree~3 with less than~48 vertices. \label{nonham-list}} \end{center} \end{figure} \begin{thmref}{n/2-thm} \label{n/2-thmref} \begin{proclaim}{Theorem \ref{n/2-thm}$'$} For $k \ge 1$, the circulant digraph $\Cay(\integer_{12k}; 6k,6k+2,6k+3)$ has no hamiltonian circuit. \end{proclaim} \end{thmref} If $\gcd(x,n) = 1$, then $\Cay(\integer_n; xa,xb,xc)$ is isomorphic to $\Cay(\integer_n; a,b,c)$, so this theorem can be restated in the following more general form. \begin{cor} \label{n/2-cor} If $\gcd(a-b,12k) = 1$, and either $2a-3b\equiv 6k \pmod{12k}$ or $3a-2b \equiv 6k \pmod{12k}$, then $\Cay(\integer_{12k}; 6k,a,b)$ has no hamiltonian circuit. \end{cor} \begin{thmref}{b+k-thm} \label{b+k-thmref} \begin{proclaim}{Theorem \ref{b+k-thm}$'$} The circulant digraph $\Cay(\integer_{2k}; a, b, b+k )$ has no hamiltonian circuit if and only if $\gcd(a,b,k) \not= 1$, or \begin{itemize} \item $\gcd(a-b,k) = 1$; and \item $\gcd(a,2k) \not= 1$; and \item $\gcd(b,k) \not= 1$; and \item either $a$~or~$k$ is odd; and \item $a$ is even, or both of $b$~and~$k$ are even. \end{itemize} \end{proclaim} \end{thmref} It is natural to ask whether there are any other non-hamiltonian examples. In this vein, an exhaustive computer search reported that every non-hamiltonian, connected, circulant digraph of outdegree three with no more than~$95$ vertices is described by either Corollary~\ref{n/2-cor} or Theorem~\ref{b+k-thmref}. (If this computer calculation is correct, then Corollary~\ref{<420vertices} implies that if there exists a connected, non-hamiltonian, circulant digraph with outdegree four (or more), then it must have more than 95 vertices.) Perhaps the first question to ask is whether the converse of Corollary~\ref{n/2-cor} is true: if $\Cay(\integer_{2n}; n,a,b)$ has no hamiltonian circuit, must it be the case that $n$~is divisible by~$6$, $\gcd(a-b,2n) = 1$, and either $2a-3b$ or $3a-2b$ is $\equiv n \pmod{2n}$? More fundamental, but also, presumably, more difficult, is to determine whether there are any examples with an odd number of vertices, or of outdegree~$\ge 4$. Our results do not provide any counterexamples to the following conjecture. \begin{conj}[{(Curran-Witte \cite[p.~74]{CurranWitte})}] \label{CW-conj} Suppose $\Cay(\integer_n;A)$ is connected, and has outdegree at least three. If, for every proper subset~$A'$ of~$A$, the subdigraph $\Cay(\integer_n;A')$ is not connected, then $\Cay(\integer_n;A)$ has a hamiltonian circuit. \end{conj} As mentioned above, circulant digraphs are Cayley digraphs on cyclic groups. Thus, this paper is related to the literature on hamiltonian circuits in Cayley digraphs \cite{AlspachSurvey}, \cite{CurranGallian}, \cite{WitteGallian}. Indeed, Rankin's Theorem~\pref{Rankin-thm} was proved for $2$-generated Cayley digraphs on any abelian group, not just on cyclic groups (and even some Cayley digraphs on nonabelian groups). Similarly, Theorem~\ref{CW-thm} and Conjecture~\ref{CW-conj} are only special cases of statements for all abelian groups. A basic lemma and some definitions are presented in Section~\ref{parity-section}. The proofs of Theorems \ref{n/2-thm} and~\ref{b+k-thm} are given in Sections \ref{n/2-section} and~\ref{b+k-section}, respectively. A small result on the hamiltonicity of circulants of outdegree four or more appears in Section~\ref{out-four-section}. \section{A parity lemma} \label{parity-section} \begin{defn} Given a digraph~$G$, let $\qc = \qc(G)$ be the set of all spanning subdigraphs of~$G$ with indegree~$1$ and outdegree~$1$ at each vertex. (Thus, each component of a digraph in~$\qc$ is a circuit.) \end{defn} \begin{lem} \label{parity-lemma} Given a digraph~$G$, suppose $H$~and~$H'$ belong to~$\qc$. Let $u_1$, $u_2$, and~$u_3$ be three vertices of~$H$, and let $v_i$ be the vertex that follows~$u_i$ in~$H$. Assume $H'$ has the same arcs as~$H$, except: \begin{itemize} \item instead of the arcs from~$u_1$ to~$v_1$, from~$u_2$ to~$v_2$, and from~$u_3$ to~$v_3$, \item there are arcs from~$u_1$ to~$v_2$, from~$u_2$ to~$v_3$, and from~$u_3$ to~$v_1$. \end{itemize} Then the number of components of~$H$ has the same parity as the number of components of~$H'$. \end{lem} \begin{proof} Let $\sigma$ be the permutation of~$\{1,2,3\}$ defined by: $u_{\sigma(i)}$ is the vertex that is encountered when~$H$ first reenters $\{u_1,u_2,u_3\}$ after~$u_i$. Thus, if $\sigma$ is the identity permutation, then $u_1,u_2,u_3$ lie on three different components of~$H$. On the other hand, if $\sigma$ is a $2$-cycle, then two of $u_1,u_2,u_3$ are on the same component, but the third is on a different component. Similarly, if $\sigma$ is a $3$-cycle, then all three of these vertices are on the same component. Thus, the parity of the number of components of~$H$ that intersect $\{u_1,u_2,u_3\}$ is precisely the opposite of the parity of the permutation~$\sigma$. There is a similar permutation~$\sigma'$ for~$H'$. From the definition of~$H'$, we see that $\sigma'$ is simply the product of~$\sigma$ with the $3$-cycle $(1,2,3)$, so $\sigma'$ has the same parity as~$\sigma$, because $3$-cycles are even permutations. Thus, the parity of the number of components of~$H$ that intersect $\{u_1,u_2,u_3\}$ is the same as the parity of the number of components of~$H'$ that intersect $\{u_1,u_2,u_3\}$. Because the components that do not intersect $\{u_1,u_2,u_3\}$ are exactly the same in~$H$ as in~$H'$, this implies that the number of components in~$H$ has the same parity as the number of components in~$H'$. \end{proof} \begin{defn} Let $G = \Cay(\integer_n; A)$, and suppose $H \in \qc$. For any $u \in \integer_n$ and $a \in A$, we say that \emph{$u$ travels by~$a$} in~$H$ if the arc from~$u$ to~$u+a$ is in~$H$. \end{defn} \section{A generator of order two} \label{n/2-section} \begin{theorem} \label{n/2-thm} If $a$ is divisible by~$6$, then $\Cay(\integer_{2a}; a,a+2,a+3)$ has no hamiltonian circuit. \end{theorem} \begin{proof} Suppose there is a hamiltonian circuit~$H_0$; let $r$~be the number of vertices that travel by~$a$, let $s$ be the number of vertices that travel by $a + 2$, and let $t$ be the number of vertices that travel by $a+3$. Since $a$~and~$a+2$ are both even, we have $\gcd(a,a+2,2a) \not=1$, so $t \not= 0$. Also, since $a$~is divisible by~$3$, we have $\gcd(a+3,2a) \not= 1$, so $t \not= 2a$. Therefore, $0 < t < 2a$. We must have $r+s+t = 2a$, and $ra + s(a+2) + t(a+3)$ must be divisible by~$2a$. Therefore, we have $$t = \bigl( ra + s(a+2) + t(a+3) \bigr) - (a+2)(r+s+t) + 2r \equiv 2r \pmod{2a} ,$$ and $$ s = (a+3)(r+s+t) - \bigl( ra + s(a+2) + t(a+3) \bigr) - 3r \equiv -3r \pmod{2a} .$$ Now $r \le a$, because the hamiltonian circuit can never have two consecutive $a$-arcs. Therefore, because $0 < t < 2a$, the congruence $t \equiv 2r$ implies that $$t = 2r .$$ Therefore, we have $2s + 3t = t + 2s + 2t = 2(r+s+t) = 2(2a) = 4a$. For each $i \in \integer_{2a}$, let \[B_i = \{ i, i+1, i+2, a+i, a+i+1, a+i+2 \} .\] We claim that \begin{center} for each~$i$, the subdigraph of~$H_0$ induced by~$B_i$ has exactly two arcs. \end{center} Consider the walk $\overline{W}$ in $\Cay(\integer_a;2,3)$ that results from reducing~$H$ modulo~$a$, and removing the loops. This walk may be lifted to a path~$W$ in $\Cay(\integer ;2,3)$ that begins at~$0$ and ends at~$4a$. Thus, for each~$j$, with $0 \le j < 4a$, there is exactly one arc $u_j \arcto v_j$ of~$W$ with $u_j \le j$ and $v_j > j$. Because $j < v_j \in \{u_j + 2, u_j + 3\}$, we have $u_j \ge j-2$, so the arc $u_j \arcto v_j$ starts in the set $\{j-2,j-1,j\}$ and ends outside this set. The corresponding arc $\overline{u}_j \arcto \overline{v}_j$ of~$H$ starts in~$B_{j-2}$ and ends outside~$B_{j-2}$. Because $B_{j-2} = B_i$ iff $j-2 \equiv i \pmod{a}$, we conclude that the hamiltonian circuit~$H_0$ has exactly~$4$ arcs that start in~$B_i$ and end outside~$B_i$. The claim follows. Let $\qd$ be the collection of all spanning subdigraphs~$H$ of~$\Cay(\integer_{2a};a,a+2,a+3)$, such that \begin{enumerate} \item every vertex of~$H$ has indegree~$1$ and outdegree~$1$ (that is, $H \in \qc$); \item $H$ has an odd number of components; \item we have $t = 2r$, where $t = t_H$ is the number of vertices that travel by~$a+3$ in~$H$, and $r = r_H$ is the number that travel by~$a$; and \item for each~$i$, the subdigraph of~$H$ induced by~$B_i$ has exactly two arcs. \end{enumerate} We know $\qd$ is nonempty, because the hamiltonian circuit~$H_0$ belongs to~$\qd$. Let $H$ be a digraph in~$\qd$, such that $r$ is minimal. We claim that some vertex travels by~$a$ in~$H$. For, otherwise, we have $r = r_H = 0$, which implies $t = 2r = 0$, so every vertex of~$H$ must travel by~$a+2$. Therefore, the number of components of~$H$ is precisely $\gcd(a+2, 2a)$. Because $a$~is even (indeed, it is divisible by~$6$), this implies that $H$ has an even number of components, which contradicts the definition of~$\qd$. \setcounter{case}{0} \begin{case} \label{consecutive} For some~$i$, the two consecutive vertices $i$ and~$i+1$ both travel by~$a$ in~$H$. \end{case} By vertex-transitivity, there is no harm in assuming $i = a+1$. Since the two arcs $(a+1)\arcto 1$ and $(a+2)\arcto 2$ must be the only arcs within the blocks $B_1$ and~$B_2$, we see that $0$, $a$, and~$1$ must all travel by~$a+3$. For the same reason, the vertex~$2$ cannot travel by~$a$. However, the vertex~$2$ cannot travel by~$a+2$, lest the vertex~$a+4$ have indegree two; so the vertex~$2$ must travel by~$a+3$. Then the vertex~$3$ must also travel by~$a+3$, lest either $a+3$ or $a+5$ have indegree~two. Continuing this argument, we see that $4$, $5$, $6$,\ldots\ must all travel by~$a+3$. So every vertex travels by~$a+3$, which contradicts the assumption that $i$~travels by~$a$. \begin{case} \label{everytwo} For every~$i$, if the vertex~$i$ travels by~$a$, then the vertex~$i-2$ also travels by~$a$. \end{case} Some vertex travels by~$a$, so, by vertex-transitivity, there is no harm in assuming that $0$ travels by~$a$. Hence, by repeated application of the hypothesis, we see that the vertex $2j$ travels by~$a$, for every~$j$. In particular, the vertices $0$, $2$, $a$, and~$a+2$ all travel by~$a$. This contradicts the fact that the subdigraph of~$H$ induced by the block~$B_0$ has only two arcs. \begin{case} The general case. \end{case} Some vertex travels by~$a$, so, by vertex-transitivity, there is no harm in assuming that $3$ travels by~$a$. From Case~\ref{everytwo}, we may assume that~$1$ does not travel by~$a$. However, the vertex~$1$ also does not travel by~$a+2$, lest the vertex~$a+3$ have indegree two; thus, the vertex $1$~must travel by~$a+3$. Now, from Case~\ref{consecutive}, we may assume that the vertex~$2$ does not travel by~$a$. However, it also does not travel by~$a+2$, lest the vertex~$a+4$ have indegree two; hence, the vertex~$2$ must travel by~$a+3$. Now, we construct another spanning subdigraph~$H'$ in which the vertices $1$, $2$, and~$3$ all travel by~$a+2$: $H'$ has the same arcs as~$H$, except: \begin{itemize} \item instead of the arcs from~$1$ to~$a+4$, from~$2$ to~$a+5$, and from~$3$ to~$a+3$, \item there are arcs from~$1$ to~$a+3$, from~$2$ to~$a+4$, and from~$3$ to~$a+5$. \end{itemize} Note that $t' = t-2$ and $r' = r-1$, so $t' = t-2 = 2r-2 = 2r'$. From Lemma~\ref{parity-lemma}, we know that the number of components of~$H$ has the same parity as the number of components of~$H'$. That is, the number of components of~$H'$ is odd. We conclude that $H' \in \qd$. But, because $r' = r-1$, this contradicts the minimality of~$H$. \end{proof} \section{Generators whose difference is the element of order two} \label{b+k-section} \begin{defn} Let $G = \Cay(\integer_{2k}; a, b, b+k )$. Let $\qf = \qf(G)$ be the set of all spanning subdigraphs of~$G$ with indegree~$1$ and outdegree~$1$ at each vertex, such that, in each coset of the subgroup $\{0,k\}$, exactly one vertex travels by~$a$, and the other by $b$~or~$b+k$. (Note that $\qf$ is a subset of the class~$\qc$ introduced in~\S\ref{parity-section}.) \end{defn} \begin{notation} For any subset~$A$ of a group~$\Gamma $, we use $\langle A \rangle$ to denote the subgroup of~$\Gamma$ generated by~$A$. For $A \subset \integer_n$, note that $\Cay(\Gamma ;A)$ is connected if and only if $\langle A \rangle =\integer_n$. \end{notation} \begin{defn} \label{H0-defn} Let $G = \Cay(\integer_{2k}; a, b, b+k )$, and assume $G$ is connected. We construct an element $H_0$ of~$\qf$. Let $d = 2k/\gcd(a,2k)$ be the order of the element~$a$ in the cyclic group~$\integer_{2k}$; the construction of our example depends on the parity of~$d$. \setcounter{case}{0} \begin{case} $d$ is odd. \end{case} In this case, $k \not\in \langle a\rangle$. Every vertex~$v$ in $\integer_{2k}$ can be uniquely written in the form $x_v a + y_v b + z_v k$ with $0 \le x_v < d$, $0\le y_v < k/d$, and $0 \le z_v < 2$. Let $H_0$ be the spanning subdigraph in which a vertex~$v \in \integer_{2k}$ \begin{itemize} \item travels by~$a$ if~$z_v = 0$; \item travels by~$b$ if $z_v = 1$ and $z_{v+b} = 1$; and \item travels by~$b+k$ otherwise. \end{itemize} (By construction, the vertices~$v$ that satisfy $z_v = 0$ are both entered and exited via an $a$-arc in~$H_0$; the other vertices are neither entered nor exited via an $a$-arc.) \begin{case} $d$ is even. \end{case} In this case, $k \in \langle a\rangle$, so every vertex~$v$ in $\integer_{2k}$ can be uniquely written in the form $x_v a + y_v b$ with $0 \le x_v < d$ and $0\le y_v < 2k/d$. Let $H_0$ be the spanning subdigraph in which a vertex~$v \in \integer_{2k}$ \begin{itemize} \item travels by~$a$ if~$x_v < d/2$; \item travels by~$b+k$ if $x_v \ge d/2$ and $1 \le x_{v+b} \le d/2$; and \item travels by~$b$ otherwise. \end{itemize} (By construction, the vertices~$v$ that satisfy $1 \le x_v \le d/2$ are precisely those that are entered via an $a$-arc in~$H_0$.) \end{defn} \begin{lem} \label{odd-components} Let $G = \Cay(\integer_{2k}; a, b, b+k )$, assume $G$ is connected, and let $H_0$ be the element of~$\qf$ constructed in Definition~\ref{H0-defn}. Then $H_0$ has an odd number of components if and only if either \begin{itemize} \item both of $a$~and~$k$ are even; or \item $a$ is odd, and either $b$~or~$k$ is odd. \end{itemize} \end{lem} \begin{proof} Let $d = 2k/\gcd(a,2k)$ be the order of the element~$a$ in the cyclic group~$\integer_{2k}$; the proof depends on the parity of~$d$. \setcounter{case}{0} \begin{case} $d$ is odd. \end{case} Because $ad$ is a multiple of~$2k$, we see, in this case, that $a$~must be even. Thus, we wish to show that the parity of the number of components of~$H_0$ is the opposite of the parity of~$k$. For $i \in \{0,1\}$, let $G_i = \{\, v \in \integer_{2k} \mid z_v = i \,\}$, so each of $G_0$ and~$G_1$ has exactly $k$~vertices. From the definition of~$H_0$, we see that each component of~$H_0$ is contained in either $G_0$ or~$G_1$. Each component in~$G_0$ is a circuit of length~$d$ (all $a$-arcs), so the number of components in~$G_0$ is $k/d$. Because $d$ is odd, this has the same parity as~$k$, so we wish to show that $G_1$ contains an odd number of components of~$H_0$. The number of components contained in~$G_1$ is equal to the order of the quotient group $\integer_{2k}/\langle b,k\rangle$. Because $\langle a,b,k\rangle = \integer_{2k}$, we know that $a$ generates this quotient group. Then, because $a$ has odd order, we conclude that the quotient group also has odd order, as desired. \begin{case} $d$ is even. \end{case} Let $xa + yb$ be a vertex that travels by~$a$ in~$H_0$. Then $v = (d/2)a + yb$ is in the same component (by following a sequence of $a$-arcs). Furthermore, if $y< (2k/d)-1$, then we see that $x_{v+b} = d/2$, so $v$~travels by~$b+k$; this means that $(y+1)b = v + b + k$ is also in the same component. By induction on~$y$, this implies that all the $a$-arcs of~$H_0$ are in the same component, and this component contains some $(b+k)$-arcs. Thus, the $a$-arcs are essentially irrelevant in counting components of~$H_0$: there is a natural one-to-one correspondence between the components of~$H_0$ and the components of $\Cay(\integer_k; b)$. Thus, the number of components is equal to the order of the quotient group $\integer_{k}/\langle b\rangle$. This quotient group has odd order if and only if either $b$~or~$k$ is odd. Therefore, $H_0$ has an odd number of components if and only if either $b$~or~$k$ is odd. Thus, we have the desired conclusion if $a$~is odd, so we may now assume $a$ is even. Since $2k/\gcd(2k,a) = d$ is even, this implies that $k$~is also even. So we wish to show that $H_0$ has an odd number of components. Because $\Cay(\integer_{2k};a,b,k)$ is connected, it cannot be the case that $a$, $b$, and~$k$ are all even, so we conclude that $b$~is odd. From the conclusion of the preceding paragraph, we see that $H_0$ has an odd number of components, as desired. \end{proof} The following result is a consequence of the proof of Lemma~\ref{parity-lemma}. \begin{lem} \label{amalgamate} Let $G = \Cay(\integer_{2k}; a,b,b+k)$, assume $H \in \qf$, and suppose $u$ is a vertex of~$H$ that travels by~$a$, such that $u$, $u+k$, and $u + a + k$ are on three different components of~$H$. Then there is an element~$H'$ of~$\qf$, with exactly the same arcs as~$H$, except the arcs leaving~$u$ and~$u+k$, and the arc entering~$u+a+k$, such that $u$, $u+k$, and~$u+a+k$ are all on the same component of~$H'$. \end{lem} \begin{theorem} \label{b+k-thm} The circulant digraph $\Cay(\integer_{2k}; a, b, b+k )$ has a hamiltonian circuit if and only if $\gcd(a,b,k) = 1$, and either \begin{itemize} \item $\gcd(a-b,k) \not= 1$; or \item $\gcd(a,2k) = 1$; or \item $\gcd(b,k) = 1$; or \item both of $a$~and~$k$ are even; or \item $a$ is odd, and either $b$~or~$k$ is odd. \end{itemize} \end{theorem} \begin{proof} ($\Rightarrow$) Because hamiltonian digraphs are connected, we know that $\gcd(a,b,k) = 1$. We may assume $\gcd(a-b,k) = 1$, $\gcd(a,2k) \not= 1$, and $\gcd(b,k) \not= 1$. Choose a hamiltonian circuit; let $r$~be the number of vertices that travel by~$a$, and let $s$ be the number of vertices that travel by $b$~or~$b+k$. We must have $r+s = 2k$, and $ra + sb$ must be divisible by~$k$. Therefore, we conclude that $r(a-b)$ is divisible by~$k$. Since $\gcd(a-b,k) = 1$, this implies $r$~is divisible by~$k$. Because $0 \le r \le 2k$, this implies $r \in \{0,k,2k\}$. Because $\gcd(a,2k) \not= 1$, we know $\langle a \rangle \not= \integer_{2k}$, so we cannot have $r = 2k$; because $\gcd(b,k) \not= 1$, we know $\langle b,k \rangle \not= \integer_{2k}$, so we cannot have $r = 0$. Therefore, we must have $r = k$. So exactly half of the vertices travel by~$a$, and the other half travel by $b$~or~$b+k$. Let us show that every hamiltonian circuit belongs to~$\qf$. That is, in each coset of the subgroup $\{0,k\}$, exactly one vertex travels by~$a$, and the other by $b$~or~$b+k$. If not, then, from the conclusion of the preceding paragraph, there must be some coset $i+\{0,k\}$ in which both vertices travel by $a$. Therefore, both vertices of $i+a+\{0,k\}$ are entered via~$a$, which means that neither of the vertices in $i+a-b+\{0,k\}$ travels by $b~$or~$b+k$, so they both must travel by~$a$. Repeating the argument, we see that both of the vertices in $i+j(a-b)+\{0,k\}$ travel by~$a$, for all~$j$. Because $\gcd(a-b,k) = 1$, every vertex in the digraph is of the form $i+j(a-b)$ or $i+j(a-b)+k$, so we see that every vertex travels by~$a$. This contradicts the conclusion of the preceding paragraph. Recall the digraph~$H_0$ of Definition~\ref{H0-defn}. It suffices to show, for every $H \in \qf$, that the number of components of~$H$ has the same parity as the number of components of~$H_0$. For then, because the preceding paragraph implies that $\qf$ contains a hamiltonian circuit, we conclude that $H_0$ has an odd number of components. Then Lemma~\ref{odd-components} provides the desired conclusion. Let $u_1$ be some vertex that travels by~$a$ in~$H$, and let $v_1 = u_1 + a$. Let $u_2 = u_1 + k$, and let $v_2 \in u_2 + \{b,b+k\}$ be the vertex that follows~$u_2$ in~$H$. Finally, let $v_3 = v_1 + k$, and let $u_3\in v_3 - \{b,b+k\}$ be the vertex that \emph{precedes}~$v_3$ in~$H$. We construct an element~$H'$ of~$\qf$ in which it is $u_2$ that travels by~$a$, instead of~$u_1$: $H'$ has the same arcs as~$H$, except: \begin{itemize} \item instead of the arcs from~$u_1$ to~$v_1$, from~$u_2$ to~$v_2$, and from~$u_3$ to~$v_3$, \item there are arcs from~$u_1$ to~$v_2$, from~$u_2$ to~$v_3$, and from~$u_3$ to~$v_1$. \end{itemize} Lemma~\ref{parity-lemma} implies that the number of components of~$H$ has the same parity as the number of components of~$H'$. Because $H$~and~$H_0$ both have the property that, in each coset of $\{0,k\}$, exactly one vertex travels by~$a$, and the other by $b$~or~$b+k$, we may transform $H$ into~$H_0$, by performing a sequence of transformations of the form $H \mapsto H'$. Thus, we may transform $H$ into~$H_0$, without changing the parity of the number of components, as desired. ($\Leftarrow$) Because $\gcd(a,b,k) = 1$, we know that $\langle a,b,k \rangle = \integer_{2k}$. \setcounter{case}{0} \begin{case} \label{gcd(a,2k)=1} We have $\gcd(a,2k) = 1$. \end{case} In this case, we have $\langle a \rangle = \integer_{2k}$, so there is an obvious hamiltonian circuit in the Cayley digraph (all $a$-arcs). \begin{case} \label{gcd(b,k)=1} We have $\gcd(b,k) = 1$ \end{case} In this case, either $\langle b \rangle = \integer_{2k}$ or $\langle b+k \rangle = \integer_{2k}$, so there is again an obvious hamiltonian circuit. \begin{case} We have $\gcd(a-b,k) \not= 1$. \end{case} In this case, we have $\langle a-b,k \rangle \not= \integer_{2k}$. There are many digraphs in~$\qc$ in which \begin{itemize} \item every vertex not in $\langle a-b,k \rangle$ travels by either $b$~or~$b+k$; and \item for each vertex $v \in \langle a-b,k \rangle$, one of $v$~and~$v+k$ travels by~$a$, and the other travels by either $b$ or~$b+k$. \end{itemize} Among all such digraphs, let $H$ be one in which the number of components is minimal. We claim that $H$ is a hamiltonian circuit. If not, then $H$ has more than one component. Because $\langle a,b,k \rangle = \integer_{2k}$, we know that $b$ generates the quotient group $\integer_{2k}/ \langle a-b,k \rangle$, so every component of~$H$ intersects $\langle a-b,k \rangle$, and hence either \begin{itemize} \item there is some vertex~$u$ in $\langle a-b,k \rangle$ such that $u$~and~$u+k$ are in different components of~$H$; or \item for all $v \in \langle a-b,k \rangle$, the vertices $v$~and~$v+k$ are in the same component of~$H$, but there is some vertex~$u$ in $\langle a-b,k \rangle$ such that $u$ and~$u+(a-b)$ are in different components of~$H$. \end{itemize} In either case, let $u_1$ be the one of $u$~and~$u+k$ that travels by~$a$. Let $v_1 = u_1 + a$. Let $u_2 = u_1 + k$, and let $v_2 \in u_2 + \{b,b+k\}$ be the vertex that follows~$u_2$ in~$H$. Finally, let $v_3 = v_1 + k$, and let $u_3\in v_3 - \{b,b+k\}$ be the vertex that \emph{precedes}~$v_3$ in~$H$. The choice of~$u_1$ implies that $u_1$, $u_2$ and~$u_3$ do not all belong to the same component of~$H$. Let $w_1$ and~$w_2$ be the vertices that \emph{precede} $u_1$ and~$u_2$, respectively, on~$H$. (So $w_1 = w_2 + k$.) Let $\sigma$ be the permutation of $\{1,2,3\}$ defined in the proof of Lemma~\ref{parity-lemma}. If $\sigma$ is an even permutation, let $H_1 = H$; if $\sigma$ is an odd permutation, let $H_1$ be the element of~$\qc$ that has the same arcs as~$H$, except: \begin{itemize} \item instead of the arcs from~$w_1$ to~$u_1$, and from~$w_2$ to~$u_2$, \item there are arcs from~$w_1$ to~$u_2$, and from~$w_2$ to~$u_1$. \end{itemize} In either case, the permutation $\sigma_1$ for~$H_1$ is even. Thus, $\sigma_1$ is either trivial or a $3$-cycle. If it is a $3$-cycle, then $u_1$, $u_2$ and~$u_3$ are all contained in a single component of~$H_1$, so $H_1$ has less components than~$H$, which contradicts the minimality of~$H$. Thus, $\sigma_1$ is trivial. Let $H'$ be the element of~$\qc$ that has the same arcs as~$H_1$, except: \begin{itemize} \item instead of the arcs from~$u_1$ to~$v_1$, from~$u_2$ to~$v_2$, and from~$u_3$ to~$v_3$, \item there are arcs from~$u_1$ to~$v_2$, from~$u_2$ to~$v_3$, and from~$u_3$ to~$v_1$. \end{itemize} Because $\sigma_1$ is trivial, we see that the permutation $\sigma '$ for~$H'$ is the $3$-cycle $(1,2,3)$. Hence, $u_1$, $u_2$ and~$u_3$ are all contained in a single component of~$H'$, so $H'$ has less components than~$H$, which contradicts the minimality of~$H$. \begin{case} Either both of $a$~and~$k$ are even; or $a$ is odd, and either $b$~or~$k$ is odd. \end{case} In this case, Lemma~\ref{odd-components} asserts that the digraph $H_0$ of Definition~\ref{H0-defn} has an odd number of components. We construct a hamiltonian circuit by amalgamating all of these components into one component. We start with the component containing~$0$, and use Lemma~\ref{amalgamate} to add the other components to it two at a time. Note that the assumption of the present case, together with the fact that $\gcd(a,b,k) = 1$, implies that $\gcd(b,k)$ is odd. Furthermore, we may assume that $\gcd(b,k)\not=1$, for, otherwise, Case~\ref{gcd(b,k)=1} applies. Thus, $\gcd(b,k) \ge 3$. Let $d = 2k/\gcd(a,2k)$ be the order of the element~$a$ in the cyclic group~$\integer_{2k}$; the proof depends on the parity of~$d$. \begin{subcase} $d$~is odd. \end{subcase} Note that two vertices $u$~and~$v$ are in the same component of~$H_0$ if and only if either \begin{itemize} \item $z_u = z_v = 0$ and $y_u = y_v$; or \item $z_u = z_v = 1$ and $x_u \equiv x_v \pmod{\gcd(b,k)}$. \end{itemize} Lemma~\ref{amalgamate} implies there is an element~$H_0'$ of~$\qf$, such that $0$, $k$, and~$a+k$ are all in the same component of~$H_0'$. (The other components of~$H_0'$ are components of~$H_0$.) Then Lemma~\ref{amalgamate} implies there is an element~$H_1 = (H_0')'$ of~$\qf$, such that $a+b$, $a+b+k$, and~$2a+b+k$ are all in the same component of~$H_1$. (The other components of~$H_1$ are components of~$H_0$.) With this as the base case of an inductive construction, we construct, for $1 \le i \le k/(2d)$, an element~$H_i$ of~$\qf$, such that \[ \{\, v \mid \text{$z_v = 0$ and $0 \le y_v \le 2i-1$}\,\} \cup \{\, v \mid \text{$z_v = 1$ and $x_v \equiv 0,1, \text{ or~$2$} \pmod {\gcd(b,k)}$} \,\} \] is a component of~$H_i$, and all other components of~$H_i$ are components of~$H_0$. Namely, $H_i$ has exactly the same arcs as $H_{i-1}$, except: \begin{itemize} \item instead of the arcs \[ \begin{array}{rrrrrrrrrrr} & &(2i-2)b & & &\arcto& a&+& (2i-2)b \\ & &(2i-2)b &+& k &\arcto& & & (2i-1)b &+& k \\ a&+&(2i-3)b &+& k &\arcto& a&+& (2i-2)b &+& k \\ \\ & &(2i-1)b & & &\arcto& a&+& (2i-1)b \\ & &(2i-1)b &+& k &\arcto& & & v\hfil \\ a&+&(2i-2)b &+& k &\arcto& a&+& (2i-1)b &+& k \\ \end{array} \] (where $v = (2i)b + k$ if $i 1$, for otherwise Case~\ref{gcd(a,2k)=1} applies. With $H_0$ as the base case of an inductive construction, we construct, for $0 \le i \le \bigl(\gcd(b,k) - 1\bigr)/2$, an element~$H_i$ of~$\qf$, such that \[ \{\, v \mid x_v < d/2 \,\} \cup \{ \, v \mid x_v \equiv 0,1, \ldots, \text{ or~$2i$} \pmod{\gcd(b,k)} \,\} \] is a component of~$H_i$, and all other components of~$H_i$ are components of~$H_0$. Namely, Lemma~\ref{amalgamate} implies there is an element~$H_i = H_{i-1}'$ of~$\qf$, such that $(2i-1)a$, $(2i-1)a+k$, and $(2i)a + k$ are all in the same component of~$H_i$. Then, for $i = \bigl(\gcd(b,k)-1\bigr)/2$, we see that a single component of~$H_i$ contains every vertex, so $H_i$ is a hamiltonian circuit. \end{proof} \section{outdegree at least four} \label{out-four-section} \begin{prop} \label{outdegree-four} Suppose $\Cay(\integer_n;A)$ has outdegree four or more, and assume there is a proper subset~$A'$ of~$A$, such that $\Cay(\integer_n;A')$ is connected and has outdegree three. If every non-hamiltonian, connected, circulant digraph that has outdegree three and exactly~$n$ vertices is described by either Corollary~\ref{n/2-cor} or Theorem~\ref{b+k-thmref}, then $\Cay(\integer_n;A)$ has a hamiltonian circuit. \end{prop} \begin{proof} Suppose the contrary. Then the spanning subdigraph $\Cay(\integer_n;A')$ also has no hamiltonian circuit. Therefore, by assumption, there are two cases to consider. \setcounter{case}{0} \begin{case} \label{case-n/2} $\Cay(\integer_n;A')$ is described by Corollary~\ref{n/2-cor}. \end{case} We have $n = 12k$, and there is no harm in assuming that $\Cay(\integer_n;A')$ is described by Theorem~\ref{n/2-thmref}, so $A' = \{6k,a,b\}$, where $a = 6k+2$ and $b= 6k+3$. Let $c$ be an element of~$A$ that is not in~$A'$. Because $6k \not\in \{a,b,c\}$, we know that $\Cay(\integer_n; a,b,c)$ is not described by Corollary~\ref{n/2-cor}, so it must be described by Theorem~\ref{b+k-thmref}. Thus, we must have $c \in \{a+6k,b+6k\}$. Because both of $a$~and~$6k$ are even, we see from Theorem~\ref{b+k-thm} that $\Cay(\integer_{12k};a,b,b+6k)$ has a hamiltonian circuit. Therefore, it must be the case that $c = a+6k \equiv 2 \pmod{n}$, so $\{2,6k,6k+2,6k+3\} \subset A$. Let $H$ be the spanning subdigraph of $\Cay(\integer_n;A)$ in which every vertex travels by~$2$, except: \begin{itemize} \item the vertex~$2$ travels by~$6k$; \item the vertex~$6k$ travels by~$6k+2$; and \item the vertices $0$ and~$6k+1$ travel by~$6k+3$. \end{itemize} Then $H$ is a hamiltonian circuit. \begin{case} $\Cay(\integer_n;A')$ is described by Theorem~\ref{b+k-thmref}. \end{case} Writing $n = 2k$, we have $A' = \{a,b,b+k\}$; let $c$ be an element of~$A$ that is not in~$A'$. By interchanging $b$~and~$b+k$ if necessary, we may assume $\Cay(\integer_n; a,b)$ is connected. Then we may assume $\Cay(\integer_n; a,b,c)$ is described by Theorem~\ref{b+k-thmref}, for otherwise Case~\ref{case-n/2} applies. Therefore, $c \in \{a+k,b+k\}$, so, because $c \not\in A'$, we must have $c = a+k$. Any Euler circuit in $\Cay(\integer_k;a,b)$ passes through each vertex exactly twice; any such circuit may be lifted to a hamiltonian circuit in $\Cay(\integer_{2k};a,a+k,b,b+k)$, which is a spanning subdigraph of $\Cay(\integer_n;A)$. \end{proof} \begin{cor} \label{<420vertices} Suppose $\Cay(\integer_n;A)$ is connected, and has outdegree four or more, and assume $n<420$. If every non-hamiltonian, connected, circulant digraph that has outdegree three and exactly~$n$ vertices is described by either Corollary~\ref{n/2-cor} or Theorem~\ref{b+k-thmref}, then $\Cay(\integer_n;A)$ has a hamiltonian circuit. \end{cor} \begin{proof} From the proposition, we may assume there is no $3$-element subset~$\{a,b,c\}$ of~$A$ with $\gcd(a,b,c,n) = 1$. This implies that $n$~has at least four distinct prime factors. Then, since $n < 420 = 2^2 \cdot 3 \cdot 5 \cdot 7$, we know that $n$~is square free. Therefore, because $n < 2310 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11$, this implies that $n$~is the product of four distinct primes. Hence, there are four elements $\{a,b,c,d\}$ of~$A$ with $\gcd(a,b,c,d,n) = 1$, so we may assume that $A$ has exactly four elements. These conditions imply that the hypotheses of Theorem~\ref{CW-thm} are satisfied, so $\Cay(\integer_n;A)$ has a hamiltonian circuit. \end{proof} \begin{remark} The proof of Corollary~\ref{<420vertices} is much simpler (namely, the first two sentences suffice) if $n < 2 \cdot 3 \cdot 5 \cdot 7 = 210$. \end{remark} \begin{acknowledgements} Witte was partially supported by a grant from the National Science Foundation. \end{acknowledgements} \begin{references} % should reformat these to JGT style ??? \bibitem{AlspachSurvey} B.~Alspach, The search for long paths and cycles in vertex-transitive graphs and digraphs, in: K.L. McAvaney, ed., \emph{Combinatorial Mathematics VIII}, Lecture Notes in Mathematics, Vol. 884 (Springer-Verlag, Berlin, 1981) 14--22. \bibitem{ChenQuimpo} C.C. Chen and N.F. Quimpo, On strongly hamiltonian abelian group graphs, in: K.L. McAvaney, ed., \emph{Combinatorial Mathematics VIII}, Lecture Notes in Mathematics, Vol. 884 (Springer-Verlag, Berlin, 1981) 23--34. \bibitem{CurranGallian} S.~J.~Curran and J.~A.~Gallian, Hamiltonian cycles and paths in Cayley graphs and digraphs --- a survey, \emph{Discrete Math.} 156 (1996) 1--18. \bibitem{CurranWitte} S.~J.~Curran and D.~Witte, Hamilton paths in cartesian products of directed cycles, \emph{Ann. Discrete Math.} 27 (1985) 35--74. \bibitem{Rankin} R.~A.~Rankin, A campanological problem in group theory, \emph{Proc. Camb. Phil. Soc.} 44 (1948) 17--25. \bibitem{WitteGallian} D.~Witte and J.~A.~Gallian, A survey: hamiltonian cycles in Cayley digraphs, \emph{Discrete Math.}, 51 (1984) 293--304. \end{references} %% Do not delete \end{article}! ===>>> \end{article} \end{document}