\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.22}{25(4)}{2018}




% Please remove all commands that change parameters such as
%    margins or page sizes.

% Packages amssymb and amsthm are already loaded. 
% We recommend these AMS packages:
\usepackage{amsmath,amssymb}
% We recommend the graphicx package for importing figures:
\usepackage{graphicx}
% Use this command to create hyperlinks (optional and recommended):
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% Theorem-like environments that are declared in the style file are:
% theorem, lemma, corollary, proposition, fact, observation, claim,
% definition, example, conjecture, open, problem, question, remark, note


\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\A}{\mathrm{Aut}}
\newcommand{\Cay}{\mathrm{Cay}}
\newcommand{\Sym}{\mathrm{Sym}}
\newcommand{\Syl}{\mathrm{Syl}}
\newcommand{\0}{\mathbf{0}}

\numberwithin{equation}{section}
\numberwithin{theorem}{section}



%%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Give the submission and acceptance dates in the format shown.
% The editors will insert the publication date in the third argument.
\dateline{Sep 7, 2017}{Sep 7, 2018}{Oct 19, 2018}

% Give one or more subject codes separated by commas.
% Codes are available from http://www.ams.org/mathscinet/freeTools.html
\MSC{ 05C63, 05C25, 20B27}

% Uncomment exactly one of the following copyright statements.  Alternatively,
% you can write your own copyright statement subject to the approval of the journal.
% See https://creativecommons.org/licenses/ for a full explanation of the 
% Creative Commons licenses.
%
% We strongly recommend CC BY-ND or CC BY. Both these licenses allow others
% to freely distribute your work while giving credit to you. The difference between
% them is that CC BY-ND only allows distribution unchanged and in whole, while
% CC BY also allows remixing, tweaking and building upon your work.  
%
%    One author:
%\Copyright{The author.}
%\Copyright{The author. Released under the CC BY license (International 4.0).}
%\Copyright{The author. Released under the CC BY-ND license (International 4.0).}
%    More than one author:
%\Copyright{The authors.}
%\Copyright{The authors. Released under the CC BY license (International 4.0).}
\Copyright{The author. Released under the CC BY-ND license (International 4.0).}



\title{Infinite Graphical Frobenius Representations}

\author{Mark E. Watkins\\
\small Department of Mathematics\\[-0.8ex]
\small Syracuse University\\[-0.8ex]
\small Syracuse, NY, U.S.A.\\
\small\tt mewatkin@syr.edu}


 
\begin{document}

\maketitle



\begin{abstract}

A {\em graphical Frobenius representation (GFR)} of a Frobenius (permutation) group $G$ is a graph $\Gamma$ whose automorphism group ${\mathrm{Aut}}(\Gamma)$ acts as a Frobenius permutation group on the vertex set of $\Gamma$, that is, ${\mathrm{Aut}}(\Gamma)$ acts vertex-transitively with the property that all nonidentity automorphisms fix either exactly one or zero vertices and there are some of each kind.  The set $K$ of all fixed-point-free automorphisms together with the identity is called the {\em kernel} of $G$.  Whenever $G$ is finite, $K$ is a regular normal subgroup of $G$ (F.\,G.\,Frobenius, 1901), in which case $\Gamma$ is a Cayley graph of $K$.  The same holds true for all the infinite instances presented here.  


Infinite, locally finite, vertex-transitive graphs can be classified with respect to (i) the cardinality of their set of {\em ends} and (ii) their {\em growth rate}.  We construct families of infinite GFRs for all possible combinations of these two properties.  There exist infinitely many GFRs with polynomial growth of degree $d$ for every positive integer $d$, and there exist infinite families of GFRs of exponential growth, both $1$-ended and infinitely-ended, that underlie infinite chiral planar maps.  There also exist GFRs of free products of finitely many finitely generated groups.  Graphs of connectivity 1 having a Frobenius automorphism group are characterized.
\end{abstract}




%%Section 1
\section{Introduction and Motivation}
\paragraph{}
Let $X$ be a nonempty set and let $G$ be a subgroup of the symmetric group $\Sym(X)$.  The permutation group $G$ is {\em transitive}  if, given any $x,y \in X$, there exists $\varphi \in G$ such that $\varphi (x) = y$.  The {\em stabilizer} of an element $x\in X$ is the subgroup $G_x = \{ \varphi \in  G : \varphi (x) = x \}$.  For distinct $x,y\in X$, the 2-{\em stabilizer} of $\{x, y\}$ is the subgroup $G_{\{x,y\}} = G_x\cap G_y$.  If $G$ is transitive, then all of its stabilizers are conjugate and hence isomorphic.  However, the 2-stabilizers in $G$ are not necessarily isomorphic unless $G$ is transitive on the 2-subsets of $X$.  A permutation group is {\em regular} if it is transitive and has trivial stabilizers; it is {\em Frobenius}  if it is transitive, has nontrivial stabilizers, and has trivial 2-stabilizers.

Much of the author's past work with finite graphs (through the 1970s, particularly \cite{ImWa76}, and recently in \cite{DoTuWa18}) pursued the question as to how smal the automorphism group $\A(\Gamma)$ of a graph $\Gamma$ can be, perhaps subject to certain conditions, but without sacrificing transitivity.  In the present work, we extend this pursuit to infinite, locally finite graphs, where ``smallness'' refers to the size of the vertex-stabilizers.  Clearly the minimal situation, as in the finite case, is when the vertex-stabilizers $\A_v(\Gamma)$ for $v\in V\Gamma$ are trivial.  In this case, the automorphism group $\A(\Gamma)$ of $\Gamma$ is regular, and hence $\Gamma$ must be a Cayley graph $\Cay(G,S)$ for some appropriate inverse-closed generating set $S$ of $G$ (see \cite{Sab58}).  When $\A(\Cay(G,S))\cong G$, then $\Gamma$ is a {\em graphical regular representation (GRR)} of the abstract group $G$. 

The question as to which abstract groups admit a GRR, known as {\em the GRR Problem}, has been resolved\footnote{The main contributors to the solution of the GRR Problem include (chronologically with some overlap) G.\,Sabidussi, W.\,Imrich, M.\,E.\,Watkins, L.\,A.\,Nowitz, D.\,Hetzel, C.\,D.\,Godsil, and L.\,Babai.  The only finitely generated groups {\em not} to admit a GRR are generalized dicyclic groups, Abelian groups other than elementary Abelian 2-groups, and thirteen miscellaneous groups of order $\leq32$.} for finitely generated groups since the early 1980s.  A natural sequel to the GRR Problem is the {\em GFR Problem}:  which abstract groups admit a {\em graphical Frobenius representation (GFR)}?  

In the GFR Problem, we allow -- in fact, we require -- the 1-point stabilizers to be nontrivial, but we require the 2-point stabilizers to be trivial.  For a first big step toward its solution for {\em finite} Frobenius groups, see \cite{DoTuWa18}.  Despite the apparent similarity in the statements of these two problems, the methods as well as their consequences are necessarily very different.  Whereas every abstract group can be represented as a {\em regular} permutation group on a set (namely on itself), vast classes of groups cannot act faithfully as {\em Frobenius} permutation groups on any set whatsoever.  As remarked in \cite{DoTuWa18}, the GFR Problem becomes in effect a two-stage problem:
\begin{enumerate}
\item  Given an abstract group $G$, is it isomorphic (abstractly) to some Frobenius permutation group?
\item Given a Frobenius permutation group $G$ on a set $V$, does there exist a graph $\Gamma$ with vertex set $V$ such that $\A(\Gamma)$ is isomorphic (as a permutation group) to $G$?
\end{enumerate}

There exists much work in the literature of group theory regarding Question 1.  Question 2 is the subject of \cite{DoTuWa18}, where as an application, all Frobenius groups of order at most 300 (except order 192) are categorized as to whether they admit a GFR.  The present paper turns the problem around.  Rather than ask which finitely generated Frobenius groups are realizable as automorphism groups of graphs, we demonstrate the existence of a wide range of infinite, locally finite graphs whose automorphism groups turn out to be Frobenius permutation groups.

In Section \ref{FrobGps}, we present some of the theory of Frobenius permutation groups needed in the ensuing sections and some basic facts about Cayley graphs.  The reader who is well-acquainted with these notions may prefer merely to skim this section.   

In Section \ref{GRs&Es} we review the notions of growth rates of infinite graphs and ends of a graph.  Similarly, the reader familiar with infinite graph theory may find little new in this section.

Section \ref{automorphisms} provides some technical lemmas needed to prove that the GFRs presented in Section \ref{Possibilities} are what they claim to be.

The main part of this article is Section \ref{Possibilities} consisting of five subsections:  (5.1) GFRs with linear growth rate; (5.2) GFRs with quadratic growth rate; (5.3) GFRs whose growth rate is polynomial of degree $\geq3$; (5.4) 1-ended GFRs with exponential growth; and (5.5) infinitely-ended GFRs.  In each subsection, a variety of infinite families of GFRs are characterized.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Section 2
\section{Frobenius Groups and Cayley Graphs}\label{FrobGps}


{\bf Definitions and Notation.}  
\begin{itemize}
\item A permutation $\varphi$ of a set $V$ is {\em fixed-point-free} if $\varphi(v)\neq v$ for all $v\in V$.
\item A nontrivial permutation group $G$ is {\em semiregular}, also called {\em fixed-point-free}, if all non-identity elements are fixed-point-free.  Equivalently, all orbits of $G$ have the same cardinality.  Thus $G$ is {\em regular} if it is transitive and semiregular.
\item  The identity of the group $G$ is denoted by $id$, and $\alpha$  denotes the function $\alpha:G\rightarrow G$ given by $x\mapsto x^{-1}$ for all $x\in G$.  Thus $\alpha$ is an automorphism of $G$ if and only if $G$ is Abelian.  When $G$ is an Abelian group, the operation in $G$ is denoted additively, the identity of $G$ is denoted by $\0$, and $\alpha$ is given by $x\mapsto-x$. 
\item The cyclic group of order $n$ is denoted by $C_n$.
\item A non-Abelian group $G$ is {\em generalized dicyclic} if it contains an Abelian subgroup $A$ of index 2 and an element $b\in G\setminus A$ such that $b^2\in A\setminus\{id\}$ and $b^{-1}aba=id$ for all $a\in A$; $G$ is {\em dicyclic} if $A=C_{2m}$ for some $m\geq2$, in which case $G$ admits the presentation
$$G=\langle a,b\mid a^{2m}=a^mb^2=b^{-1}aba=id\rangle.$$
When $m=2$, $G$ is the quaternion group. 
\item  Let the subset $S\subseteq G\setminus\{id\}$  generate $G$ and satisfy $S=S^{-1}$.   The {\em Cayley graph} $\Cay(G,S)$ has vertex set $G$ and edge set $\{[v,vs]:v\in G;s\in S\}$.  The set $S$ is the {\em connection set} of $\Cay(G,S)$.  For each $s\in S$, the  edges of the form $[v,vs^{\pm1}]$ are said to have {\em color} $s$.   
\item  The {\em kernel} $K$ of a Frobenius group $G$ is the set of fixed-point-free permutations in $G$ together with the identity permutation $id$.  The point-stabilizer $H$ is called the {\em complement.}  Thus $H\cap K=\{id\}$.
\end{itemize} 

We make the following observations:

\begin{proposition}\label{K}  If $K$ is the kernel of a Frobenius group $G$, then:
\begin{enumerate}
\item[a)] $gKg^{-1}=K$ for all $g\in G$;
\item[b)] The action of $H$ on $K\setminus\{id\}$ by conjugation is semi-regular. 
\end{enumerate}
 \end{proposition}

\begin{proof}
 For (a), we note that the property of a permutation having no fixed point is preserved by conjugation.  For (b), suppose that $hkh^{-1}=k$ for some $h\in H$ and $k \in K\setminus\{id\}$.  Then $h=khk^{-1}$, and so $h \in H \cap kHk^{-1}$.  Since $G$ has trivial 2-stabilizers, we have $h=id$.
 \end{proof}

That $K$ is actually a subgroup of $G$ in the finite case is a seminal result of Frobenius: 
 
\begin{theorem}\label{Frob}{\em (Frobenius \cite{Fr01} and Thompson \cite{Th59})}\label{F&T}   The kernel of a finite Frobenius group is a nilpotent normal subgroup of $G$.
\end{theorem}


{\bf Remark.} In the case of finite Frobenius groups, one can deduce from Theorem \ref{Frob} that the kernel $K$ is a regular permutation group such that $G=HK$.  Indeed, the proof in \cite{DoTuWa18} (Corollary 2.3) draws heavily upon the finiteness of $K$.    The fact that Theorem \ref{Frob} may fail for
infinite Frobenius groups is shown by constructions in \cite{Co90}.  (See also \cite{KeWe73}, pp. 50--54, for properties of infinite but locally finite Frobenius groups.)  Nonetheless, for all the examples $\Gamma$ of GFRs in the present work, it will hold that $\A(\Gamma)=HK$ and that $K$ acts regularly on $V\Gamma$.  

The following result, which was proved in \cite{DoTuWa18} specifically for finite groups, is shown here to hold in general.

\begin{proposition}\label{involution}  If $K$ is an Abelian group and $\varphi\in \A(K)$ is an involution that is fixed-point-free on $K\setminus\{\0\}$, then $\varphi=\alpha$. 
\end{proposition}

\begin{proof}  Let $\varphi$ be as stated, and let $k\in K\setminus\{\0\}$.  Since $\varphi$ is an involution and $K$ is Abelian, we have
$$\varphi(\varphi(k)+k)=\varphi^2(k)+\varphi(k)=k+\varphi(k)=\varphi(k)+k.$$
Thus $\varphi(k)+k$ is a fixed point of $\varphi$ and so, by our assumption, must equal $\0$.   Since $k$ was chosen arbitrarily, we have $\varphi=\alpha$.\end{proof}

The converse to Proposition \ref{involution} is false; an example below in subsection \ref{Linear} has $H=\langle\alpha\rangle$ but $K=D_\infty$, which is not Abelian.  

{\bf Henceforth in this work, all infinite graphs will be assumed to be locally finite, i.e., have finite valences.  Thus all Cayley graphs are graphs of finitely generated groups.}

We emphasize the close connection between Frobenius groups and Cayley graphs.  When the kernel $K$ of a Frobenius permutation group $G$ acting on a set $V$ is indeed a regular subgroup group of $G$, as in all examples in this work, then  the following classical result of Sabidussi comes into play:

\begin{theorem} {\em (Sabidussi \cite{Sab58})}  A necessary and sufficient condition for a graph $\Gamma$ to be a Cayley graph $\Cay(K,S)$ is that $\A(\Gamma)$ contain a subgroup $K'$ that acts regularly on the vertex set of $\Gamma$.  In that case, $K'\cong K$.
\end{theorem}


Thus, a necessary condition for given graph $\Gamma$ to be a GFR of a Frobenius group $G$ is that $\Gamma$ be a Cayley graph of the kernel of $G$.

\begin{corollary}\label{CyclicStab}  Let the (locally finite) graph $\Gamma=\Cay(K,S)$ be a GFR of an infinite Frobenius group $HK$ having an Abelian kernel $K$.  Then $|H|$ is finite and even, and $\alpha$ is the unique involution in $H$.
\end{corollary}

\begin{proof}  Because $\Gamma$ is locally finite, $S$ is finite.  By Proposition \ref{K}(b), $H$ acts semiregularly on $K\setminus\{\0\}$ and hence faithfully on $S$, because $S$ is a union of orbits of $H$.  Thus $H$ is finite.  Since $K$ is Abelian, we have $\alpha\in\A_{\0}(K)$.  Since $K$ is infinite and finitely generated, $K$ is not an elementary Abelian 2-group, and so $\alpha$ is not the identity.  Hence $\alpha$ has order 2, implying that $|H|$ is even.  By Proposition \ref{involution}, $\alpha$ is the unique involution in $\A_{\0}(K)=H$.  \end{proof}

Examples of finite groups whose automorphism group contains a unique involution include the cyclic groups of odd prime order and the dicyclic groups.  

\begin{proposition}\label{NoProduct} {\em (\cite {DoTuWa18}, Theorem 3.3)} Let $\Gamma$ and $\Delta$ be nontrivial vertex-transitive graphs.  Then $\Gamma\circ\Delta$ is not a GFR, where $\circ$ indicates any of the following graph products:  Cartesian, strong, categorical (Kronecker), or lexicographic or their graph-complements.
\end{proposition}

It follows that no group having a nontrivial factorization as a direct product can have a GFR.  Thus, other than cyclic groups, no Abelian group and no nilpotent group can admit a GFR.  This does not apply to the kernel of such a group (cf. Theorem \ref{F&T}), as will be seen in many of the examples to follow.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Section 3
\section{Growth Rates and Ends}\label{GRs&Es}

Infinite (locally finite) graphs can be classified with respect to (i) their number of {\em ends} and (ii) their {\em growth rate}.  For completeness, we briefly review these two notions.

Given a graph $\Gamma$, let ${\mathcal R}(\Gamma)$ denote the set of rays (i.e., one-way infinite paths) in $\Gamma$.  The rays  
$R_1,\,R_2\in{\mathcal R}(\Gamma)$ are {\it end-equivalent} if there exists a ray 
$ R_3\in{\mathcal R}(\Gamma)$ such that both $V( R_3\cap R_1)$ and $V( R_3\cap R_2)$ are infinite.  It is not hard to see that end-equivalence is indeed an equivalence relation on 
${\mathcal R}(\Gamma)$.  The equivalence classes with respect to end-equivalence are the {\em ends} of  $\Gamma$.  We denote by $\omega(\Gamma)$ the cardinality of the set of ends of $\Gamma$.  Thus two rays belong to different ends exactly when they contain subrays that can be separated by a finite set of vertices.  

When $\Gamma$ is locally finite, $\omega(\Gamma)$ has a convenient characterization:  it is the supremum of the number of infinite components of $\Gamma-F$ as $F$ ranges over all finite subsets of $V\Gamma$.  In particular, $\Gamma$ is $1$-{\em ended} if and only if $\Gamma-F$ has exactly one infinite component for any finite set $F$ of vertices. 
 
\begin{theorem}\label{Ha73_C15}{\em (Halin \cite{Ha73})}   If $\Gamma$ is a 
connected locally finite graph such that $\A(\Gamma)$ has finitely many orbits,  
then $\omega(\Gamma)=1,2$ or $2^{\aleph_0}$.  
\end{theorem}

In order to describe growth, we let $d(\underline{\ },\underline{\ })$ denote the standard distance metric\footnote{If $u$ and $v$ are vertices of the same component of $\Gamma$, then $d(u,v)$ is the length of a shortest path having terminal vertices $u$ and $v$.  Otherwise, define $d(u,v)=\infty$.} for graphs.  For each vertex $v\in V\Gamma$ and each integer $n\geq0$, let
\begin{align*}S_n(v):&=\{w\in V\Gamma:d(v,w)=n\};\\
B_n(v):&=\{w\in V\Gamma:d(v,w)\leq n\};\\
f(n,v):&=|B_n(v)|.
\end{align*}
We call $S_n(v)$ the $n$-{\em sphere} and $B_n(v)$ the $n$-{\em ball}, respectively, about $v$.  The function $f(n,v)$ is the {\em growth function} of $\Gamma$ with respect to the vertex $v$.  If $\Gamma$ is infinite and connected, then $f(n,v)$ is a strictly increasing function of $n$.  Clearly the growth functions with respect to vertices in the same orbit of $\A(\Gamma)$ are identical, and if $\Gamma$ is vertex-transitive, then we suppress the 
vertex $v$ altogether.  

If $\lim_{n\to\infty}f(n)/c^n>0$ holds for some constant $c>1$, then $\Gamma$ has 
{\em exponential growth rate}; otherwise, $\Gamma$ has {\em subexponential growth rate}.  As a 
particular case of subexponential growth rate, $\Gamma$ has {\em polynomial growth rate} and its 
{\em growth degree} is $\delta$ if $\delta=\inf\{d:f(n)\leq cn^{d}\text{ for all }n\in\N\}$ for some positive constant $c$.  A graph 
with {\em linear} growth rate has growth degree 1; if the growth degree is 2, then its  
growth rate is {\em quadratic}. 

\begin{example}\label{LatticePoints}   The $d$-{\em dimensional lattice} $\Lambda_d$ has vertex set $\Z^d$.  Two vertices are adjacent if and only if, in exactly one coordinate, the entries differ by exactly 1.  Let $s_{n,d}$ denote the number of vertices in the $n$-sphere about the origin of $\Lambda_d$.  One can prove inductively that
$$s_{n,d}=s_{n,d-1}+2\sum_{j=1}^{n-1}s_{j,d-1}+2$$
is a polynomial in $n$ of degree $d-1$, and so the size of the $n$-ball about the origin of $\Lambda_d$ is a polynomial of degree $d$.  Hence $\Lambda_d$ has polynomial growth rate of degree $d$.
\end{example}

That growth degree $\delta$ is always an integer follows from a result of Gromov \cite{Gr81}.  Graphs with subexponential growth rate that exceeds any polynomial have 
{\em intermediate growth rate}.  These descriptive words for rates of growth of graphs 
derive from similar usage for rates of growth of groups defined as follows.  Given a group $G$ and an inverse-closed subset $S\subseteq G\setminus\{id\}$ that generates $G$, let $g(n)$ denote the number of elements of $G$ that can be expressed as a word in $S$ of length at most $n$.  Then substitute $g(n)$ for $f(n,v)$ in the above definitions for graphs.  It is immediate that the growth rate of a group $G$ generated by a finite, inverse-closed subset $S$ is the same as the growth rate of the Cayley graph $\Cay(G,S)$.  Finitely generated Abelian groups, and hence their Cayley graphs, have polynomial growth, but not conversely.

For connected, vertex-transitive, locally finite graphs, the two notions of ends and growth rates come together with exactly the following possibilities:
\begin{itemize}
\item Linear growth:\qquad$\omega=2.$
\item Polynomial growth of degree $\geq2$:\quad$\omega=1.$
\item Intermediate growth:\qquad$\omega=1.$
\item Exponential growth:\qquad$\omega=1$ or $2^{\aleph_0}.$
\end{itemize}
The automorphism groups of graphs of intermediate growth, while finitely generated, are not finitely presentable; they will not be discussed here.  Families of examples of all the other possibilities are presented respectfully in the five subsections of Section \ref{Possibilities}.  


%%%%%%%%%%%%%%%%%%%%%%Section 4
\section{Automorphisms of Cayley graphs}\label{automorphisms}

Given a group $G$ and an inverse-closed generating set $S\subseteq G\setminus\{id\}$, one must distinguish between automorphisms of the group $G$ that leave the set $S$ invariant ({\em group}-automorphisms) and automorphisms of the Cayley graph $\Cay(G,S)$ that fix the vertex labeled by the identity element of $G$ ({\em graph}-automorphisms).  Although every such graph-automorphism $\varphi$ also leaves the set $S$ invariant, $\varphi$ need not always respect the group operation of $G$, i.e., with respect to that operation, the equation $\varphi(xy)=\varphi(x)\varphi(y)$ need not always hold.  The next result says that all group-automorphisms of $G$ are also graph-automorphisms of any Cayley graph of $G$.

\begin{proposition}\label{autos} {\em (\cite{Wa71}, Lemma 3).}  Given any Cayley graph $\Cay(G,S)$, the set of group-automorphisms of $G$ that fix $S$ setwise is a subgroup of the stabilizer in $\A(\Cay(G,S))$ of the vertex labeled as the identity.
\end{proposition}

Although the converse of this proposition is generally false, the group structure does somewhat constrain graph-automorphisms, as seen by the following pair of results from \cite{ImWa76}.

\begin{proposition}\label{stabilizers}{\em (\cite{ImWa76} Proposition 2.11)}  Given a Cayley graph $\Gamma=\Cay(G,S)$, let $U$ be any inverse-closed subset of $G\setminus\{id\}$, and suppose that $\A_u(\Gamma)=\A_{id}(\Gamma)$ holds for all $u\in U$.  Then $\A_u(\Gamma)=\A_{id}(\Gamma)$ holds for all $u$ in the subgroup $\langle U\rangle$ of $G$ generated by $U$.  In particular, if $\langle U\rangle=G$ holds, then $\A_{id}(\Gamma)$ is trivial and $\Gamma$ is a GRR of $G$.
\end{proposition}

For Abelian groups, we have the following two narrower results.

\begin{proposition}\label{ImWat_tool}{\em (\cite{ImWa76} Proposition 2.12)}   Let $\Gamma$ be a Cayley graph of an Abelian group $A$, and let $a\in L\subseteq A\setminus\{\0\}$.  Suppose that for all $\varphi$ in the stabilizer $\A_\0(\Gamma)$ it holds that
$$\varphi(a)\in\{a,-a\}{\text{\quad and\quad}}\bigl[\varphi(a)=a\Rightarrow\varphi_{\big|L}=id_{\big|L}\bigr].$$
Then for all $\varphi\in \A_{\0}(\Gamma)$, 
$$\bigl[\varphi(a)=a\Rightarrow \varphi_{\big|\langle L\rangle}=id_{\big|\langle L\rangle}\bigr]{\text{\quad and\quad}}\bigl[\varphi(a)=-a\Rightarrow\varphi_{\big|\langle L\rangle}=\alpha_{\big|\langle L\rangle}\bigr].$$
\end{proposition}

{\bf Definition.}  The term {\em geodesic} designates a {\it unique} shortest path, if one exists, between two given vertices of a graph.  (Clearly graph-automorphisms map geodesics onto geodesics, and subpaths of geodesics are geodesics.)

When the Abelian group in question is $\Z^n$, we have the following limited but useful tool.

\begin{lemma}\label{linear} Let $\Gamma=\Cay(\Z^n,S)$ and let $\varphi\in\A_\0(\Gamma)$.  Suppose that if $s\in S$, then $2s\notin S$, and suppose further that for all distinct  $s,t\in S$, all differences $s-t$ are distinct.  Then:
\begin{enumerate}
\item[(a)]  For all $s,t\in S$, no element of $S$ has the form $2s+t$; and
\item[(b)]  For all $m,n\in\Z$, we have
\begin{equation}\label{LinEq}
\varphi(ms+nt)=m\varphi(s)+n\varphi(t).
\end{equation}
\end{enumerate}
\end{lemma}


\begin{proof}  (a)  If some element of $S$ had the form $2s+t$ for some $s,t\in S$, then one would have $(2s+t)-s=s-(-t)$, contrary to hypothesis.  

(b)  Let $s\in S$, and so $\varphi(s)\in S$, and let $m\in\Z$.  We claim that there exists a geodesic joining $ms$ and $(m+2)s$.  Since $2s\notin S$, there exists a shortest path $\Pi$ of length 2 through $(m+1)s$ joining $ms$ and $(m+2)s$.  If $u\neq (m+1)s$ were also a common neighbor of $ms$ and $(m+2)s$, then there would exist $s',t'\in S$ such that $u=ms+s'=(m+2)s+t'$.  But then $2s+t'=s'\in S$, a contradiction.  Hence $\Pi$ is a geodesic.

If $w$ is any other vertex adjacent to $(m+1)s$, then there are two distinct paths of length 2 joining $ms$ and $w$:  one (of course) through $(m+1)s$, but also one through $ms+v=w-s$, where $v=w-(m+1)s\in S$, and so these two paths are not geodesics.  Thus there are exactly two geodesics of length 2 that contain the edge $[ms,(m+1)s]$; one includes the vertex $(m-1)s$ and the other includes $(m+2)s$.  For any vertex $x$, the function
 $v\mapsto v+x$ for all $v\in\Z^n$ is a graph-automorphism and hence maps geodesics to geodesics.  We conclude that {\em a path of length 2 is a geodesic if and only if it is of the form $[x,x+s, x+2s]$ for some $x\in\Z^n$ and $s\in S$.}

If we set $m=-1$ in the above argument, we have that $-s$ is the only vertex joined to $s$ by a geodesic of length 2 through $\0$.  Since $\varphi$ fixes $\0$, we have $\varphi(-s)=-\varphi(s)$.   If we set $m=0$, then the only neighbor of $s$ joined to $\0$ by a geodesic of length $2$ is $2s$.  Hence $\varphi(\pm2s)=\pm2\varphi(s)$.

Continuing the inductive argument, we assume for some $m\geq2$ that $\varphi(js)=j\varphi(s)$ for $|j|\leq m$.  
There are exactly two geodesics of length 2 containing the edge $[(m-1)s,ms]$.  One of them includes $(m+1)s$, and so $\varphi((m+1)s)=(m+1)\varphi(s)$, completing the induction.

Now let $t\in S$ and assume $t\neq\pm s$.  Then $s+t$ is the unique non-$\0$ common neighbor of $s$ and $t$.  For if $u$ were any other common neighbor, then $u=s+t'=t+s'$ for some $s',t'\in S$.  But then one has $s-t=s'-t'$, contrary to assumption.  Hence $\varphi(s+t)$ is the only common neighbor other than $\0$ of $\varphi(s)$ and $\varphi(t)$.  More generally, $\varphi(\pm s\pm t)$ is the only common neighbor other than $\0$ of $\varphi(\pm s)$ and $\varphi(\pm t)$, and so $\varphi(s+t)=\varphi(s)+\varphi(t)$.  Thus Equation (\ref{LinEq}) holds whenever $ms+nt$ lies within the 2-ball $B_2(\0)$.  It is now straightforward to complete the proof by induction on $|m|+|n|$. \end{proof}



%%%%%%%%%%%%%%%%%%%%%%%
\section{Classes of Infinite GFRs}\label{Possibilities}

For several of the infinite families of GFRs presented in this section, the Frobenius kernel $K$ is an infinite free Abelian group, namely $\Z^d$, which we treat as a vector space.  Our convention for Abelian groups, as stated in Section \ref{FrobGps},  is that the operation in $K$ is denoted additively, the identity of $K$ is denoted by $\0$, and the inversion function is $\alpha:k \mapsto -k$ for all $k \in K$.  In this context, the Frobenius complement $H$ may be identified with a linear transformation of $K$, that is, as a $(d\times d)$-matrix with entries in $\Z$.    We have thus far encountered no infinite example wherein $H$ is not cyclic.  (We invite the reader to find one!)


%%Subsection 5.1

\subsection{GFRs with linear growth rate}\label{Linear}

The double ray (i.e. two-way infinite path) is a Cayley graph of the infinite cyclic group $C_\infty$, and hence is a GFR for the infinite dihedral group $D_\infty=\langle\alpha\rangle C_\infty$, admitting the presentation
\begin{equation}\label{D_inf} 
D_\infty=\langle a,b\mid b^2=(ba)^2=id\rangle.
\end{equation}
Another 2-ended example (see Figure \ref{D_infty}) is the graph $\Cay(D_\infty, S)$, where $S=\{a, a^{-1},b, ba\}$; it is a GFR of the group $\langle\varphi\rangle D_\infty$, with $\varphi\in\A(D_\infty)$ given by:
$$\varphi(a)=a^{-1}\quad{\text{and}}\quad \phi(b)=ba.$$
With $C_\infty=\langle x\rangle$ and $S=\{x^{\pm1},x^{\pm2}\}$, a different labeling of the vertices turns this same graph into a GFR of the group $\langle\alpha\rangle C_\infty\cong D_\infty$.  

\begin{figure}[htb]
\begin{center}
\includegraphics[width=15cm]{2ends.pdf}
\caption{A 2-ended graph labeled as a Cayley graph of $D_\infty$.}\label{D_infty}
\end{center}
\end{figure}

The following theorem produces an infinite family of 2-ended GFRs.  Here we treat the infinite cyclic group additively and write $\Z$ instead of $C_\infty$.

\begin{theorem} \samepage
Let $a$ and $b$ be relatively prime positive integers.  Let $S=\{\pm a,\pm b\}$.  Then $\Cay(\Z,S)$ is a GFR of $D_\infty$.
\end{theorem}


\begin{proof}  Since $a$ and $b$ are relatively prime, $S$ generates $\Z$, and so $\Cay(\Z,S)$ is connected.  Clearly $\alpha: n\mapsto -n$ and $\tau:n\mapsto n+1$ for $n\in\Z$ are automorphisms of $\Cay(\Z,S)$ that satisfy $\alpha^2=(\alpha\tau)^2=id$ and hence generate $D_\infty$.  By Proposition \ref{ImWat_tool}, it suffices to show that if $\varphi\in\A_\0(\Cay(\Z,S))$, then $\varphi_{|S}=id_{|S}$ or $\alpha_{|S}$.  For suppose $\varphi(a)=b$ and, without loss of generality, that $\varphi(b)=a$.  (If $\varphi(a)=-b$, then replace $\varphi$ with $\alpha\varphi$.)  By Lemma \ref{linear}, $\varphi$ must swap $ka$ with $kb$ for small values of $k$ and hence either fix or invert $ab$.  Without loss of generality, suppose $a<b$.  There is a unique geodesic joining $\0$ with $ab$ and a unique geodesic joining $\0$ with $-ab$; each geodesic has length $a$ and passes through vertices  labeled as multiples of $b$, but the path starting at $\0$ through multiples of $a$ has length $b>a$, and hence is not a geodesic.  Therefore $\varphi$ fixes $S$ pointwise, and we apply Proposition \ref{stabilizers}. \end{proof}

The GFRs characterized here are quotient graphs of the 2-dimensional lattice $\Lambda_2$ (cf. Example \ref{LatticePoints}), coordinatized in the standard $xy$-fashion, modulo the line with equation  $ay=bx$.  One can readily visualize them embedded nicely  on an infinite cylinder.



%%Subsection 5.2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{GFRs with quadratic growth rate}\label{QuadGrowth}

In this subsection we present three infinite families of GFRs and one particular GFR, all of quadratic growth.  It was shown in \cite{SeTr97} that the automorphism group of an almost transitive\footnote{An infinite graph is {\em almost transitive} if its automorphism group has only finitely many orbits.} graph of quadratic growth contains an almost-transitive subgroup isomorphic to $\Z^2$.  The examples in the first two families contain as a spanning subgraph the rectangular integer lattice $\Lambda_2$ with vertex set $\Z^2$.  The graphs in the third family and the graph in the free-standing example are built on the regular hexagonal tessellation of the Euclidean plane.    


{\bf Notation.}  For the current subsection, we fix the presentation of the group $\Z^2$ as 
$$\{x,y\mid x+y=y+x\}.$$
To reduce repetition, we fix the names of the following column vectors in $\Z^2$:
$$x=\Bigl[\begin{matrix}
1\\
0
\end{matrix} \Bigr];\quad y=\Bigl
[\begin{matrix}
0\\
1
\end{matrix}\Bigr];\quad z=\Bigl
[\begin{matrix}
a\\
b
\end{matrix}\Bigr],
$$  
where $a$ and $b$ are {\em distinct} positive integers.

%Therem 5.2
\begin{theorem}\label{C_2Z^2}  Let $H$ acting on $\Z^2$ be represented by the matrix 
$\bigl[\begin{smallmatrix}
-1 & 0\\
0 & -1
\end{smallmatrix} \bigr]$.  
Let $S=Hx\cup Hy\cup Hz$.  Then $\Cay(\Z^2,S)$ is a 6-valent GFR of $\langle\alpha\rangle\Z^2$ if and only if $a,b\geq2$.
\end{theorem}



\begin{proof}  We may assume without loss of generality that $a>b$.
If $b=1$, let $\varphi$ be represented by the matrix $\bigl[\begin{smallmatrix}1 & -a\\ 0 & -1\end{smallmatrix}\bigr]$.  This action fixes pointwise the subgroup $\langle x\rangle$ while swapping $\pm y$ with $\mp z$.  Thus $S$ is preserved, and so $\varphi\in\A_\0(\Cay(\Z^2,S))$ holds by Proposition \ref{autos}.  Since $\varphi$ does not act semiregularly on $\Z^2\setminus\{\0\}$, the Cayley graph $\Cay(\Z^2,S)$ is not a  GFR.  (If $b>a=1$, then use $\bigl[\begin{smallmatrix}-1& 0 \\ -b &1\end{smallmatrix}\bigr]$, which fixes $y$ while swapping $\pm x$ with~$\mp z$.)
\begin{figure}[htb]
\begin{center}
\includegraphics[width=15cm]{FigC_2.pdf}
\caption{Theorem \ref{C_2Z^2} with $a>b>1$.}\label{FigC_2}
\end{center}
\end{figure}

Conversely, assume $b\geq2$.  We observe that the vertex $\pm ax$ is joined to $\pm z$ by a geodesic of length $b$.  (See Figure \ref{FigC_2}.)  Because $a>b\geq2$, there is no other instance, for $s,t\in S$, that $as$ is joined to $t$ by a geodesic of length $b$.  Since $\pm z\in S$ while $\pm  ax\notin S$, any graph-automorphism $\varphi\in\A_\0(\Cay(\Z^2,S))$ either fixes each of $ax$ and $z$ or inverts each of them.  By Lemma \ref{linear}(b), we have $a\varphi(x)=\varphi(ax)=\pm ax$, which implies $\varphi(x)=\pm x$.  Thus $\varphi(z)=z$ if and only if $\varphi(x)=x$.  Since $\varphi(S)=S$, we have $\varphi(y)=\pm y$.  If $\varphi$ fixes $z$ but inverts $y$, then Lemma \ref{linear}(b) yields $z=\varphi(ax+by)=ax-by\notin S$, a contradiction.  Since either $\varphi$ fixes or $\varphi$ inverts all of $S$ pointwise, we have $H=\langle\alpha\rangle$ by Proposition~\ref{ImWat_tool}. \end{proof}


Two more infinite families of GFRs with quadratic growth are presented via the following pair of theorems.

%Theorem 5.3
\begin{theorem}\label{quadratic} 
Let $H$ acting on $\Z^2$ be represented by the matrix 
$\bigl[\begin{smallmatrix}
0 & -1\\
1 & 0
\end{smallmatrix} \bigr]$.  (Thus $H\cong C_4$.)  Then $\Cay(\Z^2,S)$ with $S=Hx\cup Hz$ is an 8-valent GFR of $H\Z^2$.
\end{theorem}

%Theorem 5.4
\begin{theorem}\label{hexagonal}
Let $H$ acting on $\Z^2$ be represented by the matrix $\bigl[\begin{smallmatrix}
0 & -1\\
1 & 1
\end{smallmatrix} \bigr]$.  (Thus $H\cong C_6$.)  Then $\Cay(\Z^2,S)$ with $S=Hx\cup Hz$ is a 12-valent GFR of $H\Z^2$. 
\end{theorem}

\begin{proof}[Proof of Theorem \ref{quadratic}.]   One may assume without loss of generality that $a>b\geq1$.   The connection set $S$ comprises two $H$-orbits, which in cyclic order are $Hx=(x,y,-x,-y)$ and $Hz=(z,-bx+ay,-z,bx-ay)$.  Suppose that $\varphi\in\A_\0(\Cay(\Z^2,S))$.

First suppose $z=2x+y$ (and so the hypothesis of Lemma \ref{linear} is not satisfied).  Let $w$ be a vertex in the 2-sphere $S_2(\0)$.  If $w$ is in the orbit $H(2z)$, then there exists a geodesic of length 2 joining $\0$ and $w$.  We claim that no other vertices in the 2-sphere have this property.  If, for example, $w\in H(2x)$, say $w=2x$, then there are two distinct paths of length 2 joining $\0$ and $w$:  one through $x$ and one through $z$.  If $w=s+t$ for any $s,t\in S$ where $t\neq\pm s$, then again there exist two distinct paths of length 2 joining $\0$ and $w$:  one through $s$ and one through $t$.  We conclude that each of the two $H$-orbits comprising $S$ is invariant under $\A_\0(\Cay(\Z^2,S))$.  Since $x$ and $z$ share three common neighbors (namely $2x, x+y$ and $3x+y$), while $x$ shares fewer common neighbors with other vertices in $Hz$, it holds that, if $\varphi$ fixes one of $x$ and $z$, then $\varphi$ also fixes the other.


Now suppose that $a\geq3$, and so Lemma \ref{linear}(b) is at our disposal.  If $b\geq2$, the only instances of two elements of $S$ being joined by a geodesic of length $b$ are the four pairs $\{h^i(ax),h^i(z)\}$ for $i=0,1,2,3$.  The remainder of the proof in this subcase is so similar to the proof of Theorem \ref{C_2Z^2} that we leave the details to the reader. 
\begin{figure}[htb]
\begin{center}
\includegraphics[width=13cm]{FigC_4.pdf}
\caption{Proof of Theorem \ref{quadratic} when $z=ax+y$ and $a\geq3$.}\label{FigC_4}
\end{center}
\end{figure}

Finally, assume $z=ax+y$ and $a\geq3$.   Suppose that for some distinct elements of $Hx$, we have that $\varphi$ fixes only one of them.  By composition with $h^i$ for some $i$, we may assume that $\varphi$ fixes $x$ but not $y$.  By Lemma \ref{linear}(b), $\varphi$ fixes $ax$, whose two neighbors in $S$ are $-y$ and $z$.  (See Figure \ref{FigC_4}.)  Hence $\varphi(y)=-z$.  By Lemma \ref{linear}(b), $\varphi(ay)=-az$.  But $ay$ is adjacent to an element of $S$ (namely $h(z)=-x+ay$), while $-az$ is adjacent to no element of $S$.  We conclude that the two $H$-orbits in $S$ are invariant.  Clearly, if $\varphi$ fixes $x$, then $\varphi$ fixes $ax$ and hence also $z$ and $-y$.  Since $\{x,-y\}$ generates $\Z^2$, the theorem follows from Lemma~\ref{linear}(b). \end{proof}
\medskip

\begin{proof}[Proof of Theorem \ref{hexagonal}.]  The 1-sphere about $id$ induces two disjoint hexagons; one hexagon is induced by $Hx$ and the other by $Hz$.  (See Figure \ref{FigC_6}.)  By hypothesis, $\A_\0(\Cay(\Z^2,S))$ contains a ``rotation'' $\rho$ such that $\rho^3=\alpha$; we must show that $\rho$ alone generates $\A_\0(\Cay(\Z^2,S))$.  To do so, one must prove that no graph-automorphism $\varphi\in\A_\0(\Cay(\Z^2,S))$ acts in any of the following ways:
\begin{itemize}
\item (1) reflects a hexagon onto itself;
\item (2) fixes pointwise exactly one of the two hexagons;  or 
\item (3) maps each hexagon onto the other hexagon.
\end{itemize}
\begin{figure}[htb]
\begin{center}
\includegraphics[width=13cm]{FigC_6.pdf}
\caption{Labeled vertices are cited in the proof of Theorem \ref{hexagonal}.  Dark segments indicate edges induced by $S$.}\label{FigC_6}
\end{center}
\end{figure}
Assume without loss of generality that $a>b\geq1$ holds.  We first dispose of the case where $z$ has the form $2s+t$ for some $s,t\in S\setminus\{\pm z\}$, and in particular, let $z=2x+y$, the argument being symmetrical for the other possibilities. Suppose that $\varphi$ is a reflection of the hexagon induced by $Hx$; say, $\varphi$ interchanges $x$ and $y$.  Then $\varphi$ fixes their only non-$\0$ common neighbor $x+y$.  The vertex $2x$ is the only vertex in the 2-sphere $S_2(\0)$ adjacent to both $x$ and $x+y$, while $2y$ is the only such vertex adjacent to $y$ and $x+y$.  Hence $\varphi$ swaps $2x$ and $2y$.  Since $z$ is adjacent to $2x$ and $x+y$, its image $\varphi(z)$ must be adjacent to $2y$ and $x+y$.  However, no element of $Hz$ has that property.  Hence $\varphi$ does not reflect $Hx$ onto itself.  We next show that (2) cannot occur, from which it will follow that the hexagon induced by $Hz$ also cannot be reflected.  Observe that $x$ and $z$ share four common neighbors (namely $\0, x+y, x+z$, and $2x$), while $y$ and $z$ share only three common neighbors ($\0, x+y$, and $y+z$).  Thus, $\varphi$ moves $x$ if and only if $\varphi$ moves $z$.  


Now suppose that $z$ does not have the form $2s+t$, and so $a\geq3$.  If $\varphi$ interchanges $x$ and $y$, then by Lemma \ref{linear}(b):
$$\varphi(z)=a\varphi(x)+b\varphi(y)=ay+bx.$$
Since $a\neq b$, we have $\varphi(z)\notin S$, and so $\varphi$ does not reflect $Hx$ onto itself.   Hence, if $\varphi$ fixes $x$, then $\varphi$ also fixes $y$ and hence also fixes $z=ax+by$ by Lemma \ref{linear}(b).  We have proved that neither (1) nor (2) can occur.   


Finally, suppose that $\varphi$ interchanges the orbits $Hx$ and $Hz$.  (We remark that $\varphi$ would then be a graph-automorphism that is not a group-automorphism, because $Hx$ generates $\Z^2$ while $Hz$ does not.)  Thanks to action by $\rho$, we may assume that $\varphi(x)=z$.  As there are no reflections, we have $\varphi(y)=\rho(z)=-bx+(a+b)y$.  Then by Lemma \ref{linear}(b), we have
$$\varphi(z)=a\varphi(x)+b\varphi(y)=a(ax+by)+b(-bx+(a+b)y)=(a^2-b^2)x+(2ab+b^2)y.$$
Since $a\neq b$, the coefficient of $x$ is too large for $\varphi(z)$ to be in $Hx$, a contradiction, proving (3).  We conclude that the only automorphisms in $\A_\0(\Cay(\Z^2,S))$ are the rotations induced by $H=\langle\rho\rangle$.
\end{proof}

The final example of this subsection is a GFR of a group $G=HK$ of quadratic growth wherein the complement $H$ is of odd order, and hence, by Corollary \ref{CyclicStab}, the Frobenius kernel $K$ must be non-Abelian.  A spanning subgraph is the hexagonal tessellation of the Euclidean plane, which is representable as a Cayley graph of the non-Abelian group 
\begin{equation}\label{HexTess}
K=\langle x,y,z\mid x^2=y^2=z^2=(xyz)^2=id\rangle.
\end{equation}



\begin{theorem}\label{Hex}  Let $K$ be the group presented in (\ref{HexTess}).  Let $H=\langle h\rangle$, where $h$ is the group-automorphism of $K$ of order $3$ that maps $x\mapsto y\mapsto z\mapsto x$, and let $S=Hx\cup H(xyx)$.  Then~$\Cay(K,S)$ is a 6-valent GFR of the Frobenius group $HK$.  
\end{theorem}

\begin{proof} 
Every orbit of $H$ in $K\setminus\{id\}$ has size 3, and each $j$-sphere $S_j(id)$ for $j>0$ is a union of such orbits.  We prove that if $\varphi\in\A_{id}(\Cay(K,S))$ fixes any one vertex in $Hx=\{x,y,z\}$, then $\varphi$ fixes the other two and hence each vertex in the orbit $H(xyx)$.  As the spanning hexagonal tessellation is a planar map, it follows that $\varphi$ must be the identity automorphism, as required.  This is accomplished via the following steps.  (See Figure \ref{FigC_3K}.) 
\begin{figure}[htb]
\begin{center} \includegraphics[width=9cm]{FigC_3K.pdf}
\caption{The subgraph $\Theta$ in the proof of Theorem \ref{Hex}.}\label{FigC_3K}
\end{center}
\end{figure}
%\vspace{-0.5cm}
\begin{enumerate}
\item   For $j=2,3$, let $S_j'$ denote the set of vertices in the $j$-sphere $S_j(id)$ that are adjacent to at least two vertices in $S_{j-1}'$.  The set $S_2'$ is a union of two $H$-orbits, and $S_3'$ is a single $H$-orbit.   
\item   The subgraph $\Theta$ spanned by $\{id\}\cup S_1(id)\cup S_2'\cup S_3'$ is therefore invariant under $\A_{id}(\Cay(K,S))$, and $id$ is fixed under $\A(\Theta)$ as the only 6-valent vertex in $\Theta$. 
\item In the subgraph $\Theta$, the vertices in the $H$-orbit $Hx$ are 4-valent while those in $H(xyx)$ are 2-valent.  Hence each of these orbits is invariant under $\A(\Theta)$.
\item Without loss of generality, suppose that $\varphi$ fixes $x$ but interchanges $y$ with $z$.
\item Of the three neighbors of $x$ in $S_2'$, only $xy$ is adjacent to neither $y$ nor $z$, while $xz$ is adjacent to $z$ but not to $y$, and $yx$ is adjacent to $y$ but not to $z$.  Hence $\varphi$ fixes $xy$ while interchanging $xz$ with $yx$.
\item Of the three vertices in $S_3'$, only $xyz$ is adjacent to neither $xz$ nor $yx$, while $yzx$ is adjacent to $xz$ but not $yx$, and $zxy$ is adjacent to $yx$ but not to $xz$.  Hence $\varphi$ interchanges $yzx$ with $zxy$.
\item The vertex $yzx$ is adjacent to $xy$ (which is fixed by Step 5) while $zxy$ is not adjacent to $xy$, contrary to Step 6.
\item $\varphi$ must fix each of $x,\,y$, and $z$ as well as each vertex in $S'_2\cup S'_3$.
\item Proceeding inductively outward from $id$, one straightforwardly shows that $\varphi$ extends to the identity automorphism. \qedhere
\end{enumerate}
\end{proof}



%Subsection 5.3
\subsection{GFRs whose growth rate is  polynomial of degree $\geq3$}\label{CubicPlus}

In this subsection we obtain for each integer $d\geq3$ an infinite family of GFRs having polynomial growth rate of degree $d$ by extending the construction in Theorem \ref{C_2Z^2}.  Let $u_i\in\Z^d$ denote the $d$-tuple with $1$ as the $i^{\text{th}}$ coordinate and all others $0$.  Let the $d$-tuple $w=(a_1,\ldots,a_d)$ have integer terms of distinct absolute values all $\geq2$. Reading subscripts in this subsection modulo $d$, let $z_i=a_i  u_i+a_{i+1} u_{i+1}$.

\begin{theorem}  For $d\geq3$, the Cayley graph $\Cay(\Z^d,S)$ with
$$S=\{\pm u_i : i=1,\ldots d\}\cup\{\pm z_i:1\leq i\leq d\}\cup\{\pm w\}$$
is a GFR of  the group $\langle\alpha\rangle\Z^d$ with polynomial growth of degree $d$.
\end{theorem}


\begin{proof}  Let $\Gamma=\Cay(\Z^d,S)$ and let $\mathbb{P}_i$ denote the 2-dimensional subspace of $\Z^d$ spanned by $\{ u_i, u_{i+1}\}$.  Observe that $z_i\in\mathbb{P}_j$ if and only if $i=j$, while $w\notin\mathbb{P}_i$ for all $i=1,\ldots,d$.  Let $\varphi\in\A_\0(\Gamma)$.  Because the integers $a_1,\ldots,a_d$ have distinct nonzero absolute values, it is not difficult to see that $\varphi$ leaves invariant each of the subspaces $\mathbb{P}_i$ while $\varphi(w)\in\{w,-w\}$.  Since $|a_i|\geq2$ for all $i$, it follows by Theorem \ref{C_2Z^2} that the restriction of $\varphi$ to any given 2-dimensional subspace $\mathbb{P}_i$ is either the identity on $\mathbb{P}_i$ or $\alpha_{\big|\mathbb{P}_i}$.  But $\varphi_{\big|\mathbb{P}_i}=\alpha_{\big|\mathbb{P}_i}$ for some (and hence all) $i$ if and only if $\varphi(w)=-w$.  Since $\{ u_1,\ldots, u_d\}$ is a basis for $\Z^d$, Proposition \ref{ImWat_tool} yields that $\varphi$ equals either $id$ or $\alpha$.   \end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%Subsection 5.4
\subsection{1-Ended GFRs with exponential growth}\label{Exponential}

If a Frobenius group $G=HK$ admits a GFR $\Cay(K,S)$ with exponential growth, then, since $H$ is finite, the kernel $K$ itself has exponential growth.  Hence $K$ must be non-Abelian.  The family of GFRs to be presented in this section consists of bipartite chiral planar maps of valence at least 6.  Since all faces have even covalence at least 4, these maps accrue faces too fast to admit uniformly bounded faces in the Euclidean metric (see \cite{GrWa18}); they have vertex-homogeneous embeddings in the hyperbolic plane and their growth is exponential.  

For any integer $r\geq3$, let $\sigma=(e_1,\ldots,e_r)$, be a cyclic $r$-sequence of even integers $\geq4$ that is invariant under rotation and reflection, i.e., for all $i=2,\ldots,r$, the $r$-tuple $(e_1,\ldots,e_r)$ equals neither $(e_i,\ldots,e_r,e_1,\ldots,e_{i-1})$ nor $(e_r,\ldots,e_1)$.    For $\ell\geq2$ consider the group $K_{\sigma,\ell}$ with generating set $S_{\sigma,\ell}:=\{x_{i,j}:i=1,\ldots,r;\ j=1,\ldots,\ell\}$, where each $x_{i,j}$ is an involution, together with additional relations
\begin{equation}\label{relations}
(x_{i,j}x_{i+1,j})^{e_i/2}=1;\quad (i=1,\ldots,r-1;\ j=1,\ldots,\ell)
\end{equation}
and
\begin{equation}\label{endcap}
(x_{r,j}x_{1,j+1})^{e_r/2}=1;\quad (j=1,\ldots,\ell),
\end{equation}
where subscripts $i$ and $j$ are read modulo $r$ and $\ell$, respectively.  Then  $\Gamma_{\sigma,\ell}=\Cay(K_{\sigma,\ell}.S_{\sigma,\ell})$ is the underlying graph of a map in the plane having valence $r\ell$.  The underlying graph is bipartite; the rotational order of the connection set about each vertex $v$ is 
\begin{equation}\label{RotOrder}
(x_{1,1},\ldots,x_{r,1},\ x_{1,2},\ldots,x_{r,2},\ \ldots,\ x_{1,\ell},\ldots,x_{r,\ell})
\end{equation}
in the clockwise direction if $v$ is in one of the two parts of the bipartition and in the counterclockwise direction if $v$ is in the other part.  The cyclic $r\ell$-sequence (\ref{RotOrder}) corresponds to another cyclic $r\ell$-sequence
\begin{equation}\label{CovalenceSeq}
(e_1,\ldots,e_r,e_1,\ldots,e_r,\ \ldots\ ,e_1,\ldots,e_r)
\end{equation}
of even integers $\geq4$ that are the covalences of the faces in cyclic order about any given vertex.  This cyclic sequence (\ref{CovalenceSeq}) admits no reflection but admits a rotation of order $\ell$.

Because $\Gamma_{\sigma,\ell}$ underlies an $r\ell$-valent planar map, each vertex-stabilizer is a subgroup of the dihedral group $D_{r\ell}$.  In this case that subgroup is the cyclic group $C_\ell$ having a generator that, intuitively speaking, rotates the map about the vertex $id$ by $2\pi/\ell$ radians.  The automorphism group of the map is a Frobenius group with kernel $K_{\sigma,\ell}$ and complement $C_\ell$.  In summary,

\begin{theorem}\label{ExpoGrowth}  For any $r\geq3$ and $\ell\geq2$, let the group $K_{\sigma,\ell}$ be generated by the set $S_{\sigma,\ell}=\{x_{i,j}: 1\leq i\leq r; 1\leq j\leq\ell\}$ of involutions that also satisfy relations (\ref{relations}) and (\ref{endcap}).  Then the graph $\Cay(K_{\sigma,\ell},S_{\sigma,\ell})$ is a GFR of a Frobenius group with kernel $K_{\sigma,\ell}$ and complement~$C_\ell$.
\end{theorem} 

\subsection*{Remarks}%{\bf Remarks.}  
\begin{itemize}
\item If $\ell$ had been allowed to equal 1, then the vertex-stabilizers would be trivial, and so $\Gamma_{\sigma,1}$ would instead be a GRR.
\item If $r$ had been allowed to equal 2, then reflections would abound.
\item The sum of the covalences of the faces about any vertex is $\sum_{i=1}^r(\ell/2e_i)$, which is less than $\frac12(r\ell-2)$, as required for the growth rate to be exponential.
\end{itemize}

\begin{figure}[htb]
\begin{center} \includegraphics[width=14cm]{Ex(4,6,8).pdf}
\caption{The 1-sphere $S_1(id)$ and part of the 2-sphere in Example \ref{(4,6,8)}.}\label{Ex(4,6,8)}
\end{center}
\end{figure}
\begin{example}\label{(4,6,8)}  Among the GFRs described in Theorem \ref{ExpoGrowth}, here is the one having the fewest and smallest possible values of the parameters.
 Let $\sigma=(4,6,8)$ and consider the group
\begin{align*}
K_{\sigma,2}=\big\langle x_1,y_1,z_1,x_2,y_2,z_2& \mid x_i^2=y_i^2=z_i^2\\
&=(x_iy_i)^2=(y_iz_i)^3 =(z_1x_2)^4=(z_2x_1)^4=id\quad(i=1,2)\big\rangle.
\end{align*}
Let $S_{\sigma,2}=\{x_1,y_1,z_1,x_2,y_2,z_2\}$.  Then $\Gamma_{\sigma,2}=\Cay(K_{\sigma,2},S_{\sigma,2})$ is a 6-valent, bipartite graph underlying a planar map where the clockwise cyclic order of the connection set about each vertex in one part is $(x_1,y_1,z_1,x_2,y_2,z_2)$ with the reverse order for vertices in the other part.  Thus, twice about each vertex lie a 4-gon, a 6-gon, then an 8-gon.  (See Figure \ref{Ex(4,6,8)}.)  The only nonidentity element of the stabilizer of the identity of $\Gamma_{\sigma,2}$ is the involution induced by $\rho: x_1\leftrightarrow x_2,\ y_1\leftrightarrow y_2,\ z_1\leftrightarrow z_2$; and so $G_{\sigma,2}=\A(\Gamma_{\sigma.2})$ is an extension of $K_{\sigma,2}$ by $C_2$.  Geometrically, $\rho$ may be regarded as a $180^\circ$ rotation about the vertex labeled $id$, which makes evident that $\rho$ fixes no other vertex.  Observe that since $K$ is not Abelian, the involution $\rho$ is not equal to $\alpha$ (cf. Proposition \ref{involution}).
\end{example}


%%%%%%%%%%%%%%%%Subsection5.5
\subsection{Infinitely-ended GFRs}

It was shown in \cite{Ha64} (Satz 2) that every  almost transitive, infinitely-ended graph $\Gamma$ contains a subdivision $T$ of the infinite dyadic tree such that distinct ends of $T$ lie in distinct ends of $\Gamma$. Since $T$ has uncountably many ends,  so then must $\Gamma$.  Since $\Gamma$ is almost transitive, the distances between ``nearest'' end-separating subgraphs are bounded.  Thus $\Gamma$ has exponential growth.  In this subsection, we first characterize GFRs of connectivity 1.   We then present two very different families of infinitely-ended GFRs, the first of which has connectivity 1. 

Infinite, almost transitive graphs of connectivity 1 other than the double ray (which was discussed in Subsection \ref{Linear}) have precisely this tree-like structure.  When such graphs are vertex-transitive, every vertex is a cut-vertex incident either with at least three lobes\footnote{Following O.\,Ore \cite{Or62}, a {\em lobe} is a subgraph graph that either consists of a cut-edge with its two incident vertices or is a maximal biconnected subgraph.    We eschew the word ``block'' for this role, as it leads to ambiguity when discussing imprimitivity.} or with at least two lobes of which at least one is biconnected.  As their automorphism groups must likewise have exponential growth, we might rightly expect our GFRs to be graphical representations involving free products of groups.

In \cite{JuWa77}, H.\,A.\,Jung and the author characterized infinite graphs of connectivity 1 whose automorphism groups act on their vertex sets as (respectively) transitive, primitive, and regular permutation groups.  In \cite{Wa78} the author went on to characterize Cayley graphs of connectivity 1.  Although GFRs also are Cayley graphs, this last characterization requires more machinery than is needed to characterize GFRs of connectivity 1.  

It is useful to recall the characterization of vertex-transitive graphs $\Gamma$ having connectivity 1.
Let $\mathcal{L}_1,\mathcal{L}_2,\ldots$ be the list of 
equivalence classes of isomorphic lobes of $\Gamma$.  For each $i$, if $\Lambda\in\mathcal{L}_i$, let $\Lambda^{(j)}$ denote the $j^{\text{th}}$ orbit of $\A(\Lambda)$.  Finally, for each vertex $v\in V\Gamma$ and for each $i$ and $j$, let 
\begin{equation}\label{mu}
\mu_i^{(j)}(v)=|\{\Lambda\in\mathcal{L}_i:v\in\Lambda^{(j)}\}|.
\end{equation}
\begin{proposition}\label{JW}  {\em (\cite{JuWa77} Lemma 3.1 and Theorem 3.2)}  Let $\Gamma$ be an infinite graph of connectivity 1.  A necessary and sufficient condition for $\Gamma$ to be vertex-transitive is that, for all $i$ and $j$,  the functions $\mu_i^{(j)}$ as defined in Equation (\ref{mu}) are constant and positive on $V\Gamma$.  Furthermore, any automorphism of the union of the lobes incident with a common vertex is extendable to an automorphism of $\Gamma$.
\end{proposition} 

We now characterize graphs of connectivity 1, other than the double ray, whose automorphism groups are Frobenius groups. 

\begin{theorem}\label{1-conn}  Let $\Gamma$ be an infinitely-ended graph having connectivity 1.  A necessary and sufficient condition for $\A(\Gamma)$ to be a Frobenius group is that the following three conditions hold:  (1) Every vertex of $\Gamma$ is incident with exactly two lobes; (2) all lobes are pairwise isomorphic; (3) the lobes are GRRs.  In this case, the Frobenius complement of $\A(\Gamma)$ has order 2.
\end{theorem}
{\em Proof of sufficiency.}   Suppose that $\Gamma$ satisfies all three conditions.  In terms of the function 
$\mu_i^{(j)}$ of Equation (\ref{mu}), there is only one value of $i$, one value of $j$, and $\mu_i^{(j)}(v)=2$ for all $v\in V\Gamma$.  By Proposition \ref{JW}, $\Gamma$ is vertex-transitive.

Let $v\in V\Gamma$ be given, let $\varphi\in\A_v(\Gamma)$, and let $\Lambda_1$ and $\Lambda_2$ be the two lobes incident with $v$.  Then $\varphi$ either fixes or swaps $\Lambda_1$ and $\Lambda_2$.  In the former case, since these lobes are GRRs, $\varphi$ behaves as the identity on each lobe, and by Proposition \ref{JW} is the identity on $\Gamma$.  Otherwise, $\varphi$ interchanges $\Lambda_1$ and $\Lambda_2$.  If $\vartheta\in\A(\Gamma)$ also has this property, then $\vartheta^{-1}\varphi$ fixes these lobes, and so $\vartheta=\varphi$.  Hence the stabilizer of $v$ has order 2.  Furthermore, if $w$ is any vertex other than $v$ and if $\varphi$ is not the identity, then any path joining $w$ and $\varphi(w)$ must pass through $v$, and so $\varphi(w)\neq w$.  We conclude that $\varphi$ fixes no vertex other than $v$.  Hence $\Gamma$ is a GFR with complement of order 2.

{\em Proof of necessity.}  Assume that $\Gamma$ is a GFR.  Hence $\Gamma$  is vertex-transitive, and so the functions $\mu_i^{(j)}$ are constant and positive on $V\Gamma$ by Proposition \ref{JW}.  We first dispose of the case where $\Gamma$ is the infinite $r$-valent tree, and so all lobes are copies of $K_2$.  When $r=2$, the three conditions are met and $\Gamma$ is the double ray discussed in Subsection \ref{Linear}.  When $r >2$, then condition (1) fails and $\Gamma$ is easily seen not to be a GFR.  Hence we may assume that every vertex is incident with at least one lobe having at least three vertices.

Let $v\in V\Gamma$ and let $\Lambda_1,\Lambda_2$, and $\Lambda_3$ be some three lobes incident with $v$ with $|V\Lambda_1|\geq3$.  If there were to exist an automorphism $\zeta\in \A_v(\Gamma)$ that maps $\Lambda_2$ to $\Lambda_3$ while fixing a second vertex of $\Lambda_1$, then $\zeta$ would fix at least two vertices, a contradiction.  The argument would be similar were $\zeta$ to swap two vertices of $\Lambda_1$ while fixing any other vertex.  It follows that the automorphism group of every lobe is semiregular and that every vertex is incident with exactly two lobes.   That is, $v$ is incident only with $\Lambda_1$ and $\Lambda_2$.  If no element of $\A_v(\Gamma)$ were to swap these two lobes, then $\A_v(\Gamma)$ would be trivial, contrary to the definition of a GFR.  This would occur only if either the two lobes were not isomorphic or they were isomorphic but $v$ belongs to different orbits in each lobe.  Hence $\Lambda_1$ and $\Lambda_2$ are indeed isomorphic and the vertex set of each lobe consists of but a single orbit.  That is to say, each lobe is a GRR.  
If there were two automorphisms $\varphi, \vartheta\in\A_v(\Gamma)$ that swap $\Lambda_1$ and $\Lambda_2$, then we would have $\vartheta^{-1}\varphi\in\A_v(\Gamma)$ fixing $\Lambda_1$.  But $\A_v(\Lambda_1)$ is trivial.  Hence $\varphi^2=id$ and $A_v(\Gamma)=\langle\varphi\rangle$.  \hfill $\qed$
\medskip

The {\em rank} of a group $G$  is the least cardinality of a generating subset of $G$.  In an earlier work \cite{Wa76}, the author showed that every free product of $\leq\aleph_0$ groups, each of rank at most $\aleph_0$, admits a GRR.  Moreover, if the sum of the ranks of the groups involved is finite, then there exists a locally finite GRR.  We pursue an analogous result for locally finite GFRs.
  
For $\ell\geq2$, let $\{L_1,\ldots,L_{\ell}\}$ be a sequence of finitely generated groups, perhaps isomorphic, and denote their free product by $K=\coprod_{j=1}^\ell L_j$.  (The operation of free product is well known to be associative and commutative up to isomorphism.)  For each $j=1,\ldots,\ell$, let $S_j$ be an inverse-closed generating subset of $L_j$ not containing the identity, and let $S=\bigcup_{j=1}^\ell S_j$.   Denote by $\Gamma_j$ the Cayley graph $\Cay(L_j,S_j)$, and let $\Gamma=\Cay(K,S)$.  Thus $\Gamma$ is an uncountably-ended graph of connectivity 1 whose lobes are copies of $\Gamma_1,\ldots,\Gamma_\ell$, and every vertex is a cut-vertex incident with a fixed (positive) number of copies of each of these lobes. When $\ell=2$, we denote by $L_1\ast L_2$ the free product of $L_1$ by $L_2$.    With this notation, Theorem \ref{1-conn} immediately translates to the following characterization of GFRs of connectivity~1 and of their possible automorphism groups:

\begin{corollary}\label{1-conn-free}  If a Frobenius group $G$ whose kernel is a free product $\coprod_{j=1}^\ell L_j$ admits a GFR of connectivity 1, then  $\ell=2, L_1\cong L_2$, the group $L_1$ admits a GRR, and the Frobenius complement of $G$ has order 2.  
Conversely, if a graph $\Gamma$ has the property that every vertex is incident with exactly two lobes and the lobes are all isomorphic copies of a GRR of a group $L$, then $\Gamma$ is a GFR of connectivity 1 of a group of the form $C_2(L\ast L)$.
\end{corollary}

As an application, we continue the notation from Theorem \ref{ExpoGrowth}.  Let $K'_{\sigma',\ell}$ denote the group obtained from $K_{\sigma,\ell}$  by suppressing the relations (\ref{endcap}), let $\sigma'=(e_1,\ldots,e_{r-1})$, and let 
$$S'_{\sigma',\ell}=S_{\sigma,\ell}\setminus\{x_{r,j}:j=1,\ldots,\ell\}.$$
In the Cayley graph $\Omega_{\sigma',\ell}=\Cay(K'_{\sigma',\ell},S'_{\sigma',\ell})$, every vertex becomes a cut-vertex incident with exactly $\ell$ isomorphic infinite lobes.  In effect, $\sigma$ behaves as $(e_1,\ldots,e_{r-1},\infty)$.  One sees that these lobes are semiregular provided that $\sigma'$ is not {\em palindromic}, i.e., $(e_1,\ldots,e_{r-1})\neq(e_{r-1},\ldots,e_1)$.  For if $\sigma'$ were palindromic, then a permutation of the generators of $K'_{\sigma',\ell}$ of the form $x_{i,j}\leftrightarrow x_{r-i,j}$ ($j=1,\ldots,\ell$) would respect the relations (\ref{relations}) and hence induce a group-automorphism of $\Omega_{\sigma',\ell}$.  Observe that there exists a vertex-covering monomorphism from $\Omega_{\sigma',\ell}$ onto   $\Gamma_{\sigma,\ell}$ and hence $\Omega_{\sigma',\ell}$ also has exponential growth.  If $\ell=2$, then $\Omega_{\sigma',\ell}$ is a GFR.  We summarize as follows:

\begin{corollary}    The graph $\Omega_{\sigma',\ell}$ is a GFR of the group $C_\ell K_{\sigma',\ell}$ if and only if $\ell=2$ and $\sigma'$ is not palindromic.  In this case, $C_2=\langle\rho\rangle$, and $\rho$ acts on $K_{\sigma',\ell}$ by interchanging the generators $x_{i,1}$ with $x_{i,2}$ for all $i=1,\ldots,r-1$.
\end{corollary}


\begin{example} This is a continuation of Example \ref{(4,6,8)}.  From $\sigma=(4,6,8)$, we have $\sigma'=(4,6)$.  For $j=1,2$, we consider the two isomorphic groups and generating sets 
$$K'_j=\langle x_j,y_j,z_j\mid x_j^2=y_j^2=z_j^2=(x_jy_j)^2=(y_jz_j)^3=id\rangle;\quad S_j=\{x_j,y_j,z_j\}.$$
Each tree-like graph $\Cay(K'_j,S_j)$ is a GRR of $K'_j$ consisting of denumerably many 4-cycles and 6-cycles; each 4-cycle shares alternate edges (colored $y$) with a different 6-cycle, and vice versa.  Observe that $z_jx_j$ has infinite order in $K_j$.  The graph $\Omega_{\sigma',2}=\Cay(K'_1\ast K'_2,S_1\cup S_2)$ is a GFR of the group $C_2(K'_1\ast K'_2)$ of connectivity 1 and valency 6, where the generator of $C_2$ is given by $x_1\leftrightarrow x_2,\,y_1\leftrightarrow y_2,\,z_1\leftrightarrow z_2$.
\end{example}

Having determined that the kernels of the only groups that admit GFRs of connectivity 1 are free products with themselves of a group that admits a GRR, one is led to inquire about free products of groups that do {\em not} generally admit GRRs, such as Abelian groups.  Of course, such GFRs are biconnected.  We conclude the present work by taking a small step in this direction; we present GFRs whose kernels are free products of a pair of cyclic groups.  

\begin{theorem}\label{free_cycles}  Let the group $C_m\ast C_n$ be given by $\langle x, y\mid x^m=y^n=id\rangle$.  Let $S=\{x^{\pm1},y^{\pm1},(xy)^{\pm1}\}$, and let $\Gamma=\Cay(C_m\ast C_n,S)$.  If $m=n$, then $\Gamma$ is a GFR of  $C_2(C_m\ast C_m)$.  If $m\neq n$, then $\Gamma$ is a GRR of $C_m\ast C_n$.
\end{theorem}
\begin{proof}  If  $m=n=2$, then $C_2\ast C_2$ is isomorphic to the group $D_\infty$ as presented by Equation (\ref{D_inf}) obtained by setting $x=b$ and $y=ba$.  The graph $\Cay(C_2\ast C_2,S)$ is isomorphic to the graph shown in Figure \ref{D_infty} and so is a GFR of $D_\infty$.

Now assume that at least one of $m$ and $n$ is at least 3.  Edges having color $xy$ lie on exactly one 3-cycle $[v, vx, vxy,v]$ and on {\em no other chordless cycle}.  Edges having color $x$ or color $y$ lie on exactly two 3-cycles if $m=2$ or $3$ and lie on a chordless $m$-cycle if $m\geq4$.  Thus the set of edges of color $xy$ is invariant under $\A(\Gamma)$.  

Let $\varphi\in\A_{id}(\Gamma)$.  We next dispose of the special case when (without loss of generality) $m=2$ and $n=3$ (see Figure \ref{FigC_2astC_3}).  Here the 1-sphere $S_1(id)$ induces a path $[xy,x,y,y^2,(xy)^{-1}]$ of length 4.  Hence $y$, being the middle vertex, is fixed by $\A_{id}(\Gamma)$.  If $\varphi$ were to swap $x$ and $y^2$, then the edge $[x,y]$, which has color $xy$, would be mapped onto the edge $[y^2,y]$, which is not of color $xy$, a contradiction.  Hence by Lemma \ref{stabilizers}, $\A_v(\Gamma)$ is trivial and $\Gamma$ is a GRR of $C_m\ast C_n$.
\begin{figure}[htb]
\begin{center}
\includegraphics[width=14cm]{FigC_2astC_3.pdf}
\caption{Theorem \ref{free_cycles}, the case where $m=2$ and $n=3$.}\label{FigC_2astC_3}
\end{center}
\end{figure}

Now assume $m,n\geq3$.  Observe that the vertex $x$ is adjacent to the vertex $xy$ but $x^{-1}$ is adjacent to neither $xy$ nor $(xy)^{-1}$.  Hence $\varphi(x)\neq x^{-1}$, since the set of edges colored $xy$ is invariant.   

If $m\neq n$, then edges of color $x$ and edges of color $y$ lie on chordless cycles of different lengths, and so the edge $[id,x]$ cannot be mapped onto $[id,y]$.  Thus $\varphi(x)$ fixes $x$ and so also fixes $x^{-1}$.  Since $y$ is adjacent to $x^{-1}$ while $y^{-1}$ is not, $\varphi$ also fixes $y$.  Again, $\A_v(\Gamma)$ is trivial and $\Gamma$ is a GRR.

Finally, suppose $m=n$.  Then $C_m\ast C_m$ admits a group-automorphism $\beta$ given by $\beta(x)=y^{-1}$ and $\beta(y)=x^{-1}$.  Observe that $\beta^2=id$.  Since $\beta(xy)=(xy)^{-1}$, we have $\beta(S)=S$, and so by Proposition \ref{autos}, $\beta\in\A_{id}(\Gamma)$.  If $\vartheta$ were a different nonidentity element of $\A_v(\Gamma)$, then $\vartheta(x)=y$ would hold, and so $\beta\vartheta(x)=x^{-1}$, a contradiction.  Thus $\A_{id}(\Gamma)=\langle\beta\rangle$.  \end{proof}

\subsection*{Exercises.}

\begin{enumerate}
\item[(1)] Consider the Cayley graph with connection set $\{x^{\pm1},y^{\pm1},z^{\pm1}, (xyz)^{\pm1}\}$ of the free product 
$$C_p\ast C_q\ast C_r=\langle x,y,z\mid x^p=y^q=z^r=id\rangle.$$
When is this graph a GFR or a GRR?
\item[(2)] Construct a 3-connected GFR of $C_m\ast C_m$.  Does there exist a planar example?
\item[(3)] Is it the case that, if $m\neq n$, then no GFR of $C_m\ast C_n$ exists, or did we just make an unfortunate choice for the connection set in Theorem \ref{free_cycles}?
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Acknowledgement}  The author was partially supported by a Simons Foundation Collaborative Research Grant (\#209803 to Mark E. Watkins).  The author thanks T. W. Tucker for the proof of Proposition \ref{involution} used here.   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{thebibliography}{99} 
\bibitem{Co90} M. J. Collins.  Some infinite Frobenius groups. {\em J. Algebra}, 131: 161--165, 1990.
\bibitem{DoTuWa18}  J. K. Doyle, W. T. Tucker, and M. E. Watkins. Graphical Frobenius Representations.  {\em J. Algebr. Comb.}, 2018. 
\url{https://doi.org/10.1007/s10801-018-0814-6}.
\bibitem{Fr01} F. G. Frobenius. \"Uber aufl\"osbare Gruppen. IV.  {\em Berliner Sitz.}, 1216-1230, 1901.
\bibitem{GrWa18} S. J. Graves and M. E. Watkins. Growth of face-homogeneous tessellations. {\em Ars Math. Contemporanea}, 14(2):285-318, 2018. 
\bibitem{Gr81}  M. Gromov. Groups of polynomial growth and expanding maps.  {\em Inst. Hautes \'{E}tudes Sci. Publ. Math.}, 53:53--78, 1981.
\bibitem{Ha64} R. Halin. \"{U}ber unendliche Wege in Graphen. {\em Math. Annalen}, 157:125--137, 1964.
\bibitem{Ha73} R. Halin.  Automorphisms and endomorphisms of infinite locally finite graphs {\em Abh. Math. Sem. Univ. Hamburg}, 39:251--283, 1973.
\bibitem{ImWa76} W. Imrich and M. E. Watkins. On automorphism groups of Cayley graphs. {\em Per. Math. Hungar.}, 7(3--4):243--258, 1976.
\bibitem{JuWa77} H. A. Jung and M. E. Watkins. On the structure of infinite vertex-transitive graphs.  {\em Discrete Math.}, 18(1):45--53, 1977.
\bibitem{KeWe73} O. H. Kegel and B. A. F.\,Wehrfritz.  Locally Finite Groups.  North Holland Publishing Company, Amsterdam, 1973.
\bibitem{Or62} O. Ore. Theory of Graphs.  American Mathematical Society, Providence RI, 1962.
\bibitem{Sab58} G. Sabidussi. On a class of fixed-point free graphs.  {\em Proc. Amer. Math. Soc.} 9:800-804, 1958.
\bibitem{SeTr97} N. Seifter and V. I. Trofimov. Automorphism groups of graphs with quadratic growth. {\em J. Combinatorial Theory, Ser B}, 71:205--210, 1997.
\bibitem{Th59} J. G. Thompson. Finite groups with fixed-point-free automorphisms of prime order. {\em Proc. Nat. Acad. Sci. U. S. A.}.  45:578-581, 1959.
\bibitem{Wa71} M. E. Watkins. On the action of non-Abelian groups on graphs.  {\em J. Combinatorial Theory}, 11(2): 95--104, 1971.
\bibitem{Wa76} M. E. Watkins. Graphical regular representations of free products of groups.  {\em J. Combinatorial Theory, Ser. B}, 21(1):47--66, 1976.
\bibitem{Wa78} M. E. Watkins, Les graphes de Cayley de connectivit\'{e} un.  In  {\em Probl\`{e}mes Combinatoires et Th\'{e}orie des Graphes, Proc. International Colloquium on Graph Theory, Orsay, France, July 1976}, pages  419--422,  CNRS, Paris, 1978.
\end{thebibliography}
\end{document}