# On Free products of graphs

Max Carter  ,  Stephan Tornier  and  George Willis  The University of
Newcastle, School of Mathematical and Physical Sciences, 2308 Callaghan NSW,
Australia.

###### Abstract.

We define a free product of connected simple graphs that is equivalent to
several existing definitions when the graphs are vertex-transitive but differs
otherwise. The new definition is designed for the automorphism group of the
free product to be as large as possible, and we give sufficient criteria for
it to be non-discrete. Finally, we transfer Tits’ classification of
automorphisms of trees and simplicity criterion to free products of graphs.

##  1\. Introduction

Every locally compact (l.c.) group $G$ is an extension of its connected
component, $G_{0}$, by the totally disconnected (t.d.) quotient $G/G_{0}$:

$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{G_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{G\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{G/G_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1.}$

As connected l.c. groups have been seen to be inverse limits of Lie groups in
fundamental work by Gleason [9], Montgomery-Zippin [21] and Yamabe [28],
totally disconnected ones are now the focus in the structure theory of l.c.
groups.

Every t.d.l.c. group can be viewed as a directed union of compactly generated
(c.g.) open subgroups. Among c.g.t.d.l.c. groups, those acting on (regular)
graphs stand out due to the Cayley-Abels graph construction [16]: Every
c.g.t.d.l.c. group $G$ acts vertex-transitively on a connected regular graph
$\Gamma$ of finite degree with compact open vertex-stabilisers. Conversely,
the automorphism group of every connected locally finite graph is t.d.l.c. and
has compact open vertex-stabilisers, see Section 2.

Groups acting on graphs are studied extensively [3] [1] [25] and play a
significant role when studying the scale of a t.d.l.c. group [27], see e.g.
[2], [19] and [4]. It remains a frequently appearing and difficult question to
determine when the automorphism group of a given (infinite) graph is non-
discrete.

In this article, we define a free product
$\Gamma=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$
of connected simple graphs $\Gamma_{1},\ldots,\Gamma_{n}$
$(n\in\operatorname{\mathbb{N}})$, which may be (locally) infinite. This
product is associative and commutative with unit a single vertex. It realises
the Cayley graph of a free product of finitely generated groups as the free
product of the Cayley graphs of the factors. We compare our definition with
several existing ones and see that all are equivalent when
$\Gamma_{1},\ldots,\Gamma_{n}$ are vertex-transitive. The vertices and edges
of $\Gamma$ are defined directly, rather than by gluing copies of
$\Gamma_{1},\ldots,\Gamma_{n}$ as done in the other definitions, which
facilitates computation in the graphs and also, when the graphs are not
vertex-transitive, yields a free product with a larger automorphism group. We
give sufficient criteria for $\operatorname{Aut}(\Gamma)$ to be non-discrete:
Corollary 6.7 states that $\operatorname{Aut}(\Gamma)$ is non-discrete as soon
as one of $\Gamma_{1},\ldots,\Gamma_{n}$ $(n\geq 2)$ has some non-trivial
vertex-stabiliser, and Proposition 6.8 states that
$\operatorname{Aut}(\Gamma)$ is non-discrete whenever two of the factors
$\Gamma_{1},\ldots,\Gamma_{n}$ $(n\geq 3)$ are isomorphic.

Finally, we consider the subgroup
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$ of
$\operatorname{Aut}(\Gamma)$ which preserves the sheet structure of $\Gamma$
induced by its factors. It acts on a _structure tree_ , akin to a block-cut
tree, and thus lends itself for the transfer of Tits’ classification of
automorphisms of trees and simplicity theorem [24], see Theorem 7.6 and
Proposition 7.8.

##  2\. Preliminaries

A _graph_ $\Gamma$ is a tuple $(V,E)$ consisting of a _vertex set_ $V$ and an
_edge set_ $E\subseteq V^{|2|}$, where $V^{|2|}:=\\{\\{x,y\\}\mid x,y\in V,\
x\neq y\\}$. The _order_ of $\Gamma$ is $|V|$. For $x\in V$, we let
$N_{\Gamma}(x)$ denote the set $\\{y\in V\mid\\{x,y\\}\in E\\}$ of _neighbours
of $x\in V$_ and $E_{\Gamma}(x)$ the set $\\{e\in E\mid x\in e\\}$ of edges
incident with $x\in V$. The _valency_ , or _degree_ , of $x\in V$ is
$|N_{\Gamma}(x)|$. The graph $\Gamma$ is _locally finite_ if $|N_{\Gamma}(x)|$
is finite for every $x\in V$. It is _regular of degree $d$_ if
$|N_{\Gamma}(x)|=d$ for every $x\in V$.

A _path of length $k$_, where $k\in\operatorname{\mathbb{N}}$, in $\Gamma$ is
a sequence $(e_{1},\dots,e_{k})$ of edges with $e_{i}\cap e_{i+1}=\\{x_{i}\\}$
a singleton for each $i\in\\{1,\dots,k-1\\}$. The path may thus also be
described by the sequence $(x_{0},\dots,x_{k})$ of vertices, where
$e_{i}=\\{x_{i-1},x_{i}\\}$ for $i\in\\{1,\ldots,k\\}$, and $x_{i}\neq
x_{i+2}$ for all $i\in\\{0,\ldots,k-2\\}$. The graph $\Gamma$ is _connected_
if for all $x,y\in V$ there is a path $(x=x_{0},x_{1},\ldots,x_{k}=y)$ from
$x$ to $y$. It is a _forest_ if it does not contain paths from a vertex to
itself. A _tree_ is a connected forest. We denote the regular tree of degree
$d\in\operatorname{\mathbb{N}}$ by $T_{d}$. Note that $T_{1}$ consists of a
single edge. Given a subset $S\subseteq V$, the _span of $S$ in $\Gamma$_ is
the graph $\mathrm{span}_{\Gamma}(S):=(S,E\cap S^{|2|})$.

Let $\Gamma=(V,E)$ be a connected graph. A vertex $x\in V$ is a _cut vertex_
if the graph $(V\backslash\\{x\\},E\backslash E_{\Gamma}(x))$, which arises
from $\Gamma$ by removing $x\in V$ and all edges incident with $v$, is not
connected. A graph without cut-vertices is _$2$ -connected_.

Existing definitions of free products involve repeatedly joining together
copies of the graphs at specified, or root, vertices. Rooted graphs
$\Gamma_{1}=(V_{1},E_{1},v_{1})$ and $\Gamma_{2}=(V_{2},E_{2},v_{2})$ are
joined at $v_{1}$ and $v_{2}$ to obtain the _connected sum_
$(\Gamma_{1},v_{1})\\#(\Gamma_{2},v_{2})$, which is the graph obtained from
$\Gamma_{1}\sqcup\Gamma_{2}=(V_{1}\sqcup V_{2},E_{1}\sqcup E_{2})$ by
identifying $v_{1}$ and $v_{2}$.

Let $\Gamma_{1}=(V_{1},E_{1})$ and $\Gamma_{2}=(V_{2},E_{2})$ be graphs. A
_morphism_ $\varphi:\Gamma_{1}\to\Gamma_{2}$ is a map $\varphi:V_{1}\to V_{2}$
such that $\varphi(\\{x,y\\})\in E_{2}$ for every edge $\\{x,y\\}\in E_{1}$.

######  Lemma 2.1.

Let $\Gamma\\!=\\!(V,E)$ and $\Gamma^{\prime}\\!=\\!(V^{\prime},E^{\prime})$
be graphs and $\varphi:\\!\Gamma\to\Gamma^{\prime}$ a morphism. If
$\Gamma^{\prime}$ is connected and
$\varphi(N_{\Gamma}(x))=N_{\Gamma^{\prime}}(\varphi(x))$ for every $x\in V$
then $\varphi$ is surjective.

###### Proof.

Let $x\in V$ and $x_{0}:=\varphi(x)\in V^{\prime}$. Given $y\in V^{\prime}$
let $(x_{0},x_{1},\ldots,x_{k}=y)$ be a path from $x_{0}$ to $y$. Since
$\varphi(N_{\Gamma}(x))=N_{\Gamma^{\prime}}(\varphi(x))=N_{\Gamma^{\prime}}(x_{0})$
we conclude that $x_{1}\in\varphi(N_{\Gamma}(x))$, say
$x_{1}=\varphi(x^{\prime})$. Iterate. ∎

Let $\Gamma=(V,E)$ be a connected graph. We equip the set
$\operatorname{Aut}(\Gamma)$ of automorphisms of $\Gamma$ with the permutation
topology for its action on $V$, see [19, Section 1.2]. This turns
$\operatorname{Aut}(\Gamma)$ into a Hausdorff totally disconnected group that
is locally compact when $\Gamma$ is locally finite. Given a subgroup
$H\leq\operatorname{Aut}(\Gamma)$ and a subgraph
$\Gamma^{\prime}\subseteq\Gamma$, the _pointwise stabiliser_ of
$\Gamma^{\prime}$ in $H$ is denoted by $H_{\Gamma^{\prime}}$. Similarly, the
_setwise stabiliser_ of $\Gamma^{\prime}$ in $H$ is
$H_{\\{\Gamma^{\prime}\\}}$. Finally, the _rigid stabiliser_ of
$\Gamma^{\prime}$ in $H$ is the set
$\mathrm{rist}_{H}(\Gamma^{\prime}):=H_{\Gamma\backslash\Gamma^{\prime}}$ of
elements which pointwise stabilise the complement of $\Gamma^{\prime}$ in
$\Gamma$.

##  3\. Definition

In Sections 3.2, 3.3 and 3.4 below we recall several existing definitions of
free products of graphs found in the literature, all of which are in the
spirit of [12, Section 31.2]. The new definition given in Section 3.1 has the
advantage that it lends itself to computations and the analysis of the free
product’s automorphism group. A comparison between these four definitions made
in Section 5 illuminates all of them and shows that they are equivalent in the
case of vertex-transitive graphs.

###  3.1. A new definition

Let $\Gamma_{1}=(V_{1},E_{1}),\ldots,\Gamma_{n}=(V_{n},E_{n})$ be connected
graphs. The _free product_ of $\Gamma_{1},\ldots,\Gamma_{n}$, denoted
$\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$,
is the following graph $\Gamma=(V,E)$. Its vertex set consists of _admissible_
words in the alphabet $V_{1}\sqcup\cdots\sqcup V_{n}$ and its edge set is
defined in terms of the last vertices in such admissible words.

#### Vertices

The set of admissible words of length $l$ is denoted by $V^{(l)}$ and defined
by induction on $l$. Its definition involves an _update function_
$\mathbf{u}:V\to V_{1}\times\dots\times V_{n}$ defined inductively alongside
$V^{(l)}$. Choose $(u_{1},\ldots,u_{n})\in V_{1}\times\dots\times V_{n}$ and
set

(1) $V^{(0)}:=\\{\emptyset\\}\mbox{ and
}\mathbf{u}(\emptyset):=(u_{1},\dots,u_{n})\in V_{1}\times\dots\times V_{n}.$

Assume that $V^{(k)}$ and $\mathbf{u}|_{V^{(k)}}$ are defined for
$k\in\\{0,\dots,l\\}$. For $\tilde{v}=v_{1}\ldots v_{k}\in V^{(k)}$, let
$\mathbf{u}(\tilde{v})=\left(u_{1}(\tilde{v}),\dots,u_{n}(\tilde{v})\right)$.
Then $V^{(l+1)}$ consists of all words of the form $\tilde{v}v_{l+1}$ where
$\tilde{v}=v_{1}\ldots v_{l}\in V^{(l)}$ and, supposing that $v_{l}\in V_{i}$
and $v_{l+1}\in V_{j}$, we have

(2) $j\neq i\mbox{ and }v_{l+1}\neq u_{j}(\tilde{v}).$

The update function is defined on $V^{(l+1)}$ by

(3) $u_{h}(\tilde{v}v_{l+1}):=\begin{cases}u_{h}(\tilde{v})&\mbox{ if }h\neq
j\\\ v_{l+1}&\mbox{ if }h=j\end{cases}.$

#### Edges

The edge set $E$ consists of pairs of admissible words
$\\{\tilde{v},\tilde{v}v_{l+1}\\}$ as follows. The edges incident on the empty
word are

(4) $\\{\emptyset,v_{1}\\}\mbox{ where }\\{u_{i}(\emptyset),v_{1}\\}\in
E_{i}\mbox{ for some }i\in\\{1,\dots,n\\}.$

The edges incident on the non-empty word $\tilde{v}=v_{1}\dots v_{l-1}v_{l}$,
with $v_{l}\in V_{i}$, are

(5) $\displaystyle\\{v_{1}\dots v_{l-1}v_{l},v_{1}\dots
v_{l-1}v^{\prime}_{l}\\}\mbox{ for all }\\{v_{l},v_{l}^{\prime}\\}\in E_{i}$
(6) and $\displaystyle\\{\tilde{v},\tilde{v}v_{l+1}\\}\mbox{ for all
}\\{u_{j}(\tilde{v}),v_{l+1}\\}\in E_{j}\mbox{ and }j\neq i.$

######  Remark 3.1.

While the definition above depends on the choice of $\mathbf{u}(\emptyset)$,
it will be seen in Corollary 4.7 that two graphs defined using different
choices are isomorphic. The following observations further illuminate the
definition of $\Gamma$.

  1. (i)

By Definition 3.1 (2), we have $v_{1}\dots v_{l}\\!\in\\!V$ if and only if
$v_{k}$ and $v_{k+1}$ are vertices in distinct graphs for each
$k\\!\in\\!\\{1,\dots,l-1\\}$, and $v_{k+1}\\!\neq\\!u_{j}(v_{1}\dots v_{k})$,
assuming $v_{k+1}\in V(\Gamma_{j})$.

  2. (ii)

By Definition 3.1 (4), (5) and (6) the vertex $\tilde{v}\in V$ has one
neighbour for each neighbour of $u_{i}(\tilde{v})$ ($i\in\\{1,\dots,n\\}$).
Hence
$|N_{\Gamma}(\tilde{v})|=\sum_{i=1}^{n}|N_{\Gamma_{i}}(u_{i}(\tilde{v}))|$.

Definitions 3.1 (5) and (6) imply that, for $\tilde{v}=v_{1}\ldots v_{l}\in V$
with $v_{l}\in V_{i}$ and $j\neq i$, the set of vertices
$\left\\{\tilde{v}\right\\}\cup\left\\{\tilde{v}v_{l+1}\mid v_{l+1}\in
V_{j}\setminus\\{u_{j}(\tilde{v})\\}\right\\}$ spans a subgraph
$S_{(\tilde{v},j)}$ of $\Gamma$ isomorphic to $\Gamma_{j}$, termed the
_$\Gamma_{j}$ -sheet at $\tilde{v}$_. Similarly, the subgraph
$S_{(\tilde{v},i)}$ spanned by $\\{v_{1}\dots v_{l-1}\\}\cup\left\\{v_{1}\dots
v_{l-1}v^{\prime}_{l}\mid v^{\prime}_{l}\in V_{i}\setminus\\{u_{i}(v_{1}\dots
v_{l-1})\\}\right\\}$ is the _$\Gamma_{i}$ -sheet at $\tilde{v}$_. Elements of
the set $\operatorname{\mathcal{S}}:=\\{S_{(\tilde{v},i)}\mid\tilde{v}\in
V(\Gamma),\ i\in\\{1,\ldots,n\\}\\}$ are _sheets_ of $\Gamma$.

  1. (iii)

Every vertex of $\Gamma$ belongs to a unique $\Gamma_{j}$-sheet for every
$j\in\\{1,\ldots,n\\}$. Belonging to the same $\Gamma_{j}$-sheet is an
equivalence relation on $V$.

  2. (iv)

Every edge of $\Gamma$ belongs to a unique $\Gamma_{j}$-sheet for a unique
$j\in\\{1,\ldots,n\\}$. The associated map $c:E\to\\{1,\dots,n\\}$ defines a
colouring of $\Gamma$ which is constant on sheets. Part ii states that the
number of edges adjacent to $\tilde{v}\in V$ with colour $i$ is
$|N_{\Gamma_{i}}(\tilde{v})|$.

  3. (v)

Sheets of different graphs intersect either trivially or at a single vertex.

  4. (vi)

If $\tilde{v},\tilde{w}\in V$ belong to the same $\Gamma_{i}$-sheet, then
$u_{j}(\tilde{v})=u_{j}(\tilde{w})$ for all $j\neq i$.

######  Example 3.2.

This example illustrates the genesis of the free product $\Gamma$ of the
graphs in Figure 1.

$\Gamma_{1}:=$$a_{0}$$a_{1}$and

$\Gamma_{2}:=$$b_{0}$$b_{2}.$$b_{1}$

Figure 1. The graphs $\Gamma_{1}$ and $\Gamma_{2}$.

Starting from $\\{\emptyset\\}=V^{(0)}\subset V(\Gamma)$ and
$\mathbf{u}(\emptyset)=(a_{0},b_{0})$, we obtain Figure 2

$b_{1}$$b_{2}$$\emptyset$$a_{1}$and

$b_{1}$$b_{2}$$\emptyset$$a_{1}$

Figure 2. The first two steps in the genesis of $\Gamma_{1}\ast\Gamma_{2}$.

by first adding in $V^{(1)}$ and edges incident on $\emptyset\in V(\Gamma)$,
and then edges of type (5). Here,
$\textbf{u}(a_{1})=({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a_{1}},b_{0})$,
$\textbf{u}(b_{1})=(a_{0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}b_{1}})$
and
$\textbf{u}(b_{2})=(a_{0},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}b_{2}})$.
After adding in $V^{(2)}$ and edges of type (6) for vertices in $V^{(1)}$ we
have the graph of Figure 3.

$b_{1}$$b_{2}$$\emptyset$$a_{1}$$a_{1}b_{2}$$a_{1}b_{1}$$b_{2}a_{1}$$b_{1}a_{1}$
Figure 3. Another step in the genesis of $\Gamma_{1}\ast\Gamma_{2}$.

Now,
$\textbf{u}(a_{1}b_{1})\\!=\\!(a_{1},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}b_{1}})$,
$\textbf{u}(a_{1}b_{2})\\!=\\!(a_{1},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}b_{2}})$,
$\textbf{u}(b_{1}a_{1})\\!=\\!({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a_{1}},b_{1})$
and
$\textbf{u}(b_{2}a_{1})\\!=\\!({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a_{1}},b_{2})$.

######  Example 3.3.

Part ii of this example can be seen as motivating the definition of free
products of graphs.

  1. (i)

Let
$\Gamma_{i}=\pspicture(-2.84526pt,-2.13394pt)(31.298pt,0.0pt){\psdots(0.0pt,0.0pt)(28.45274pt,0.0pt)}{\psline(0.0pt,0.0pt)(28.45274pt,0.0pt)}\rput(14.22636pt,4.2679pt){\scriptsize{$i$}}\endpspicture$,
$i\in\\{1,\dots,n\\}$. Then
$\Gamma=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$
is a tree with regular valency $n$ and the map of Remark 3.1iv defines a legal
labelling of the tree in the sense of Burger–Mozes, see [3, Section 3.2]. More
generally, if $\Gamma_{i}$ is a regular tree of valency $d_{i}$, then $\Gamma$
is a regular tree of valency $\sum_{i=1}^{n}d_{i}$ and each vertex is adjacent
to $d_{i}$ edges coloured $i$.

  2. (ii)

For finitely generated groups $(G_{1},S_{1})$ and $(G_{2},S_{2})$, the free
product of the Cayley graphs of $G_{1}$ and $G_{2}$ is isomorphic to the
Cayley graph of $G_{1}\\!\ast\\!G_{2}$:

$\hbox
to0.0pt{\hfil}\Gamma(G_{1},S_{1})\ast\Gamma(G_{2},S_{2})\cong\Gamma(G_{1}\ast
G_{2},S_{1}\sqcup S_{2}).$

Indeed, apply the definition by Pisanski–Tucker in Section 3.3 to
$\Gamma(G_{1},S_{1})$ and $\Gamma(G_{2},S_{2})$, rooted at the identity
elements $e_{1}\in G_{1}$ and $e_{2}\in G_{2}$. In both
$\Gamma(G_{1},S_{1})\ast\Gamma(G_{2},S_{2})$ and $\Gamma(G_{1}\ast
G_{2},S_{1}\sqcup S_{2})$, the vertices are alternating words $w$ in
$G_{1}\backslash\\{e_{1}\\}\sqcup G_{2}\backslash\\{e_{2}\\}$, and,
considering multiplication with reduction in $G_{1}\ast G_{2}$, edges are
precisely given by $\\{w,ws\\}$ for $s\in S_{1}\sqcup S_{2}$.

######  Proposition 3.4.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs. Then
$\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$
is connected.

###### Proof.

Let
$(V,E):=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$.
We show by induction on $l\geq 0$ that there is a path from $\emptyset\in V$
to $\tilde{v}=v_{1}\ldots v_{l}\in V$. If $l=0$ then $\tilde{v}=\emptyset$ and
the statement holds. Now consider $\tilde{v}v_{l+1}\in V$. By the induction
hypothesis, there is a path from $\emptyset$ to $v_{1}\ldots v_{l}$. Now, let
$j\in\\{1,\ldots,n\\}$ be such that $v_{l+1}\in V(\Gamma_{j})$. Then both
$\tilde{v}$ and $\tilde{v}v_{l+1}$ belong to the $\Gamma_{j}$-sheet
$S_{(\tilde{v},j)}$. Since $\Gamma_{j}$ is connected there is a path from
$\tilde{v}$ to $\tilde{v}v_{l+1}$ within that sheet. Concatenation yields the
desired path from $\emptyset$ to $\tilde{v}v_{l+1}$. ∎

Note that the free product construction is commutative with unit a single
vertex. Thus, _we shall henceforth assume that no factor of a free product is
a single vertex_. We show in Corollary 4.8 that it is also associative.
However, while the graphs

$(\Gamma_{1}\ast\Gamma_{2})\ast\Gamma_{3},\
\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{3}\Gamma_{i}\text{
and }\Gamma_{1}\ast(\Gamma_{2}\ast\Gamma_{3})$

are pairwise isomorphic, the sheet structure of a free product does depend on
the bracketing, or whether no bracketing is specified: The graph
$\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{3}\Gamma_{i}$
has sheets of types $\Gamma_{1}$, $\Gamma_{2}$ and $\Gamma_{3}$ whereas
$\Gamma_{1}\ast(\Gamma_{2}\ast\Gamma_{3})$ has sheets of type $\Gamma_{1}$ and
$\Gamma_{2}\ast\Gamma_{3}$, and $(\Gamma_{1}\ast\Gamma_{2})\ast\Gamma_{3}$ has
sheets of type $\Gamma_{1}\ast\Gamma_{2}$ and $\Gamma_{3}$. This is most
relevant in Section 7.

###  3.2. Möller-Seifter-Woess-Zemljic

In [20], Möller et al. define a free product of connected, vertex-transitive
graphs. Let $\Gamma_{1}=(V_{1},E_{1})$ and $\Gamma_{2}=(V_{2},E_{2})$ be
connected, vertex-transitive graphs of order $m$ and $n$ respectively.

The free product is a connected sum of copies of $\Gamma_{1}$ and
$\Gamma_{2}$. The copies are indexed by the vertices of the $(m,n)$-biregular
tree $T_{m,n}$: bipartition $V(T_{m,n})=V_{m}\sqcup V_{n}$ into vertices of
degree $m$ and $n$ respectively and assign a copy, $\smash{\Gamma_{1}^{(v)}}$,
of $\Gamma_{1}$ for every $v\in V_{m}$ and a copy, $\smash{\Gamma_{2}^{(w)}}$,
of $\Gamma_{2}$ for every $w\in V_{n}$. The sum is indexed by the edges of
$T_{m,n}$: choosing bijections $\psi_{v}:V^{(v)}_{1}\to E_{T_{m,n}}(v)$, for
every $v\in V_{m}$, and $\psi_{w}:V^{(w)}_{2}\to E_{T_{m,n}}(w)$, for every
$w\in V_{n}$, associates a unique vertices in $V^{(v)}_{1}$ and $V^{(w)}_{2}$
to each edge $\\{v,w\\}\in E(T_{m,n})$. Then $\Gamma_{1}\ast\Gamma_{2}$ is the
graph $\Gamma=(V,E)$

(7) $\underset{\\{v,w\\}\in
E(T_{m,n})}{\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\\#$}}}}\left(\Gamma_{1}^{(v)},\psi_{v}^{-1}(\\{v,w\\})\right)\\#\left(\Gamma_{2}^{(w)},\psi_{w}^{-1}(\\{v,w\\})\right).$

The connected sum construction implies that $V(\Gamma)$ is in bijection with
$E(T_{m,n})$ with $x\in V(\Gamma)$ corresponding to $\\{v,w\\}\in E(T_{m,n})$,
which is formed by identifying $\psi_{v}^{-1}(\\{v,w\\})\in\Gamma_{1}^{(v)}$
with $\psi_{w}^{-1}(\\{v,w\\})\in\Gamma_{2}^{(w)}$. There is thus a $2$-$1$
map from the disjoint union of the graphs $\smash{\Gamma_{1}^{(v)}}$ and
$\smash{\Gamma_{2}^{(w)}}$ to $V(\Gamma)$, and $V(\smash{\Gamma_{1}^{(v)}})$
and $V(\smash{\Gamma_{2}^{(w)}})$ will hence be regarded as being subsets of
$V(\Gamma)$. The neighbours of $x$ are the edges $\psi_{v}(p)\in
E_{T_{m,n}}(v)$, with $p\in V(\Gamma_{1}^{(v)})$ a neighbour of
$\psi_{v}^{-1}(\\{v,w\\})$ and $\psi_{w}(q)\in E_{T_{m,n}}(w)$, with $q\in
V(\Gamma_{2}^{(w)})$ a neighbour of $\psi_{w}^{-1}(\\{v,w\\})$.

In a similar spirit, Mohar [18, Section 2] defines a free product of graphs
with amalgamation, in which maps analogous to the maps $\psi$ above are used
to amalgamate given subsets of $V(\Gamma_{1})$ and $V(\Gamma_{2})$.

###  3.3. Pisanski-Tucker

In [22], Pisanski-Tucker define a free product of rooted graphs. Let
$\Gamma_{1}=(V_{1},E_{1},v_{1})$ and $\Gamma_{2}=(V_{2},E_{2},v_{2})$ be
rooted graphs. The free product $\Gamma_{1}\ast\Gamma_{2}$ is the graph
$\Gamma=(V,E)$ with vertex set all finite words in the alphabet
$V_{1}\backslash\\{v_{1}\\}\cup V_{2}\backslash\\{v_{2}\\}$ whose letters
alternate between $V_{1}\backslash\\{v_{1}\\}$ and
$V_{2}\backslash\\{v_{2}\\}$. Two vertices $w$ and $w^{\prime}$ are adjacent
if either $w^{\prime}=wx$ for a neighbour $x$ of the respective root, or
$w=ux$ and $w^{\prime}=uy$ for adjacent $x,y$ in $\Gamma_{1}$ or $\Gamma_{2}$.

Thus multiple copies of $\Gamma_{1}$ and $\Gamma_{2}$ are connected by
identifying each vertex in a copy of $\Gamma_{1}$ with the root in a copy of
$\Gamma_{2}$, and each vertex in a copy of $\Gamma_{2}$ with the root in a
copy of $\Gamma_{1}$.

###  3.4. Quenell

In [23], Quenell defines a free product of rooted graphs. Let
$\Gamma_{1}=(V_{1},E_{1},v_{1}),\ldots,\Gamma_{n}=(V_{n},E_{n},v_{n})$ be
rooted graphs. Recursively define graphs $B_{i}$ for $i\in\\{1,\ldots,n\\}$ by
setting

$B_{i}=\underset{v\in
V_{i}\backslash\\{v_{i}\\}}{\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\\#$}}}}(\Gamma_{i},v)\\#(B_{2},v_{2})\\#\cdots\\#\widehat{(B_{i},v_{i})}\\#\cdots\\#(B_{n},v_{n}),$

where $\widehat{(B_{i},v_{i})}$ means that $(B_{i},v_{i})$ is omitted from the
connected sum. Finally, set
$\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}:=(B_{1},v_{1})\\#\cdots\\#(B_{n},v_{n})$.

When $n=2$, the graph $B_{1}$ in the Quenell construction corresponds to those
words in the Pisanski-Tucker construction that are empty or begin with a
letter in $V_{1}\backslash\\{v_{1}\\}$, and $B_{2}$ corresponds to those words
that are empty or begin with a letter in $V_{2}\backslash\\{v_{2}\\}$. The
Quenell construction connects $B_{1}$ and $B_{2}$ at their respective vertices
corresponding to the empty word.

##  4\. Uniqueness and Quotients

Based on Remark 3.1 we define the following class of quotients of the free
product
$\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$.
It includes the free product itself as well as the cartesian product
$\prod_{i=1}^{n}\Gamma_{i}$.

######  Definition 4.1.

Let $\Gamma_{1}$, …, $\Gamma_{n}$ be graphs. A _mashup_ of $\Gamma_{1}$, …,
$\Gamma_{n}$ is a connected graph $M\\!=\\!(V,E)$ with embeddings
$\varphi_{(x,i)}:\Gamma_{i}\to M$ ($x\\!\in\\!V,\ i\\!\in\\!\\{1,\ldots,n\\}$)
such that

  1. (a)

$x\in\varphi_{(x,i)}(\Gamma_{i})$, the _$\Gamma_{i}$ -sheet at $x$_,

  2. (b)

$E=\bigcup\left\\{\varphi_{(x,i)}(E(\Gamma_{i}))\mid i\in\\{1,\dots,n\\},\
x\in V\right\\}$,

  3. (c)

for all $i,j\in\\{1,\dots,n\\}$ and $x,y\in V$ the subgraphs
$\varphi_{(x,i)}(\Gamma_{i})$ and $\varphi_{(y,j)}(\Gamma_{j})$ are either
identical and $i=j$, have empty intersection, or intersect at a single vertex
and $i\neq j$; and

  4. (d)

for all $i,\,j\in\\{1,\dots,n\\}$ with $i\neq j$, $x\in V$ and $y\in
V(\varphi_{(x,i)}(\Gamma_{i}))$ the maps

$\displaystyle\Gamma_{i}\to M\to\Gamma_{i}:$ $\displaystyle\
v\mapsto\varphi_{(x,i)}(v)\mapsto\varphi^{-1}_{(y,i)}(\varphi_{(x,i)}(v))$
$\displaystyle\hbox to0.0pt{\hfil}\Gamma_{i}\to M\to\Gamma_{j}:$
$\displaystyle\
v\mapsto\varphi_{(x,i)}(v)\mapsto\varphi^{-1}_{(\varphi_{(x,i)}(v),j)}(\varphi_{(x,i)}(v))$

are constant.

######  Remark 4.2.

Retain the notation of Definition 4.1.

  1. (1)

Conditions a and d imply that every vertex of $M$ belongs to a unique
$\Gamma_{i}$-sheet for every $i\in\\{1,\ldots,n\\}$.

  2. (2)

Conditions b and c imply that every edge of $M$ belongs to a unique
$\Gamma_{i}$-sheet for a unique $i\in\\{1,\ldots,n\\}$.

  3. (3)

Conditions a and d provide a map $\mathbf{u}:V\to
V(\Gamma_{1})\times\dots\times V(\Gamma_{n})$ defined by
$\smash{\mathbf{u}(x)=(\varphi^{-1}_{(x,1)}(x),\dots,\varphi^{-1}_{(x,n)}(x))}$
such that all coordinates $u_{j}$ of $\mathbf{u}$ except the $i$-th one are
constant on $\varphi_{(x,i)}(\Gamma_{i})$.

  4. (4)

By conditions b,c and d, every $x\in V$ has $|N_{\Gamma_{i}}(u_{i}(x))|$
neighbours in its $\Gamma_{i}$-sheet. The valency of $x$ in $M$ is therefore
given as in Remark3.1(ii).

  5. (5)

Conditions a and d imply c.

######  Example 4.3.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs. Examples of mashups
are:

  1. (i)

The free product
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$.
For $x\in V(\Gamma)$ and $i\in\\{1,\ldots,n\\}$ define the map
$\varphi_{(x,i)}:\Gamma_{i}\to\Gamma$ using the sheet structure of $\Gamma$
given in Remark 3.1.

  2. (ii)

The cartesian product $\Gamma:=\prod_{i=1}^{n}\Gamma_{i}$. Recall that
$V(\Gamma)=\prod_{i=1}^{n}V(\Gamma_{i})$. For $x=(x_{1},\ldots,x_{n})\in
V(\Gamma)$ and $i\in\\{1,\ldots,n\\}$, define the map
$\varphi_{(x,i)}:\Gamma_{i}\to\Gamma$ by
$\varphi_{(x,i)}(y):=(x_{1},\ldots,x_{i-1},y,x_{i+1},\ldots,x_{n})\in
V(\Gamma)$ for every $y\in V(\Gamma_{i})$. In particular,
$\mathbf{u}=\operatorname{id}$ in this case.

  3. (iii)

Parts i and ii can be combined via the following construction which resembles
that of right-angled Artin groups, see e.g. [6]. Let $B$ be a non-empty,
finite graph with vertex set $V(B)=\\{1,\ldots,n\\}$ and let
$\Gamma_{i}=(V_{i},E_{i})$ be a connected graph for every $i\in V(B)$. We
outline the construction of a mash-up $M_{B}=(V,E)$ of the $\Gamma_{i}$ $(i\in
V(B))$ such that
$M_{B}=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i\in
V(B)}\Gamma_{i}$ when $B$ has no edges, and $M_{B}=\prod_{i\in
V(B)}\Gamma_{i}$ when $B$ is complete. The vertex set of $M_{B}$ consists of
certain admissible words in the alphabet $V_{1}\sqcup\cdots\sqcup V_{n}$,
forming a strict subset of those defined in Section 3.1.

_Vertices_. The set of admissible words of length $l$ is denoted by $V^{(l)}$
and defined by induction on $l$. It involves an update function
$\mathbf{u}\\!:V\\!\to V_{1}\times\cdots\times V_{n}$ defined inductively
alongside $V^{(l)}$. Choose $(u_{1},\ldots,u_{n})\in V_{1}\times\cdots\times
V_{n}$. Set

$\hbox to0.0pt{\hfil}V^{(0)}:=\\{\emptyset\\}\text{ and
}\mathbf{u}(\emptyset):=(u_{1},\ldots,u_{n})\in V_{1}\times\cdots\times
V_{n}.$

Now, assume that $V^{(k)}$ and $\mathbf{u}|_{V^{(k)}}$ are defined for
$k\in\\{0,\ldots,l\\}$. Given a vertex $\tilde{v}=v_{1}\ldots v_{k}\in
V^{(k)}$, let
$\mathbf{u}(\tilde{v})=(u_{1}(\tilde{v}),\ldots,u_{n}(\tilde{v}))$. The set
$V^{(l+1)}$ consists of all words of the form $\tilde{v}v_{l+1}$ where
$\tilde{v}=v_{1}\ldots v_{l}\in V^{(l)}$ and, supposing that $v_{l}\in V_{i}$
and $v_{l+1}\in V_{j}$ we have

$\hbox to0.0pt{\hfil}j\neq i,\ v_{l+1}\neq u_{j}(\tilde{v})\text{ and
}j>i\text{ whenever }\\{i,j\\}\in E(B).$

The update function is defined on $V^{(l+1)}$ by

$\hbox
to0.0pt{\hfil}u_{h}(\tilde{v}v_{l+1}):=\begin{cases}u_{h}(\tilde{v})&\text{if
}h\neq j\\\ v_{l+1}&\text{if }h=j\end{cases}.$

_Sheets_. To define the edges of $M_{B}$ and show that it is a mash-up of the
$\Gamma_{i}$ $(i\in V(B))$, we define its sheets: For $\tilde{v}=v_{1}\ldots
v_{l}\in V$ with $v_{l}\in V_{i}$ and $j\in\\{1,\ldots,n\\}$, the
$\Gamma_{j}$-sheet at $\tilde{v}$ has the following vertex set $S\subseteq V$,
which is naturally turned into a copy of $\Gamma_{j}$.

    1. $\bullet$

If $j=i$, let $S:=\\{v_{1}\dots v_{l-1}\\}\cup\left\\{v_{1}\dots
v_{l-1}v^{\prime}_{l}\mid v^{\prime}_{l}\in V_{j}\setminus\\{u_{j}(v_{1}\dots
v_{l-1})\\}\right\\}$.

    2. $\bullet$

If $j>i$ and $\\{i,j\\}\in E(B)$, or $\\{i,j\\}\not\in E(B)$, set

$\hbox to0.0pt{\hfil}S:=\\{\tilde{v}\\}\cup\\{\tilde{v}v_{l+1}\mid v_{l+1}\in
V_{j}\backslash\\{u_{j}(\tilde{v})\\}\\}.$

    3. $\bullet$

If $j<i$ and $\\{i,j\\}\in E(B)$, define $\iota(v_{m})\in\\{1,\ldots,n\\}$
$(m\in\\{1,\ldots,l\\})$ as the unique index such that
$v_{m}\in\Gamma_{\iota(v_{m})}$. Now, let $k\in\\{1,\ldots,l\\}$ be minimal
such that $\iota(v_{k})\geq j$ and $\\{\iota(v_{r}),j\\}\in E(B)$ for all
$r\\!\in\\!\\{k,\ldots,l-1\\}$. If $\iota(v_{k})=j$, then $k\neq l$ and we set

$\hbox to0.0pt{\hfil}S:=\\{\tilde{v}\\}\cup\\{v_{1}\ldots
v_{k-1}v^{\prime}v_{k+1}\ldots v_{l}\mid v^{\prime}\in
V_{j}\backslash\\{u_{j}(\tilde{v})=v_{k}\\}\\}.$

Otherwise, if $\iota(v_{k})>j$, then $k\leq l$ and we set

$\hbox to0.0pt{\hfil}S:=\\{\tilde{v}\\}\cup\\{v_{1}\ldots
v_{k-1}v^{\prime}v_{k}\ldots v_{l}\mid v^{\prime}\in
V_{j}\backslash\\{u_{j}(\tilde{v})\\}\\}.$

In each of the above cases, the set $S$ is in natural bijection with $V_{j}$.
The edges of the $\Gamma_{j}$-sheet at $\tilde{v}$ are then defined using
$E_{j}$ via said bijection.

For example, one can see that the Cayley graph of the right-angled Artin group
$A:=\\{s_{1},\ldots,s_{n}\mid\\{[s_{i},s_{j}]\mid\\{i,j\\}\in E(B)\\}\\}$
defined via the base graph $B$ is isomorphic to $M_{B}$ where
$\Gamma_{i}=T_{2}$ for all $i\in\\{1,\ldots,n\\}$.

Now, let $M$ be a mashup of $\Gamma_{1},\ldots,\Gamma_{n}$ and let
$\gamma=(e_{1},\ldots,e_{k})$ be a path in $M$. By Remark 4.2(2), there is a
unique index $c(e_{m})\in\\{1,\ldots,n\\}$ for every edge $e_{m}$ in $\gamma$
such that $e_{m}$ belongs to a $\Gamma_{c(e_{m})}$-sheet of $M$. Write
$e_{m}=\\{x_{m-1},x_{m}\\}\in E(\Gamma_{c(e_{m})})$. We say that $\gamma$
_transitions from $\Gamma_{i}$ to $\Gamma_{j}$ at $m$_ if $c(e_{m})=i$,
$c(e_{m+1})=j$ and $i\neq j$. Then $x_{m}$ is a _transition point in $M$_ and
$\smash{\varphi_{(x_{m},i)}^{-1}(x_{m})}$ is a _transition point in
$\Gamma_{i}$_.

In the case
$\smash{M=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}}$,
there is a path from the empty word $\emptyset$ to $\tilde{v}=v_{1}\dots
v_{l}$ with transitition points $v_{k}$ ($k\in\\{1,\dots,l-1\\}$). If
$v_{k}\in V(\Gamma_{i_{k}})$, then the path goes from $v_{1}\dots v_{k-1}$ to
$v_{1}\dots v_{k}$ in a $\Gamma_{i_{k}}$-sheet and transitions into a
$\Gamma_{i_{k+1}}$-sheet at $v_{1}\ldots v_{k}$. Denote $v_{1}\dots v_{k}$ by
$x_{k}$. The length of the shortest path from $\emptyset$ to $\tilde{v}$ now
is

$d(\emptyset,\tilde{v})=\sum_{k=1}^{l}d_{\Gamma_{i_{k}}}(\varphi^{-1}_{(x_{k},i_{k})}(x_{k-1}),\varphi^{-1}_{(x_{k},i_{k})}(x_{k}))=\sum_{k=1}^{l}d_{\Gamma_{i_{k}}}(u_{i_{k}}(x_{k-1}),u_{i_{k}}(x_{k})),$

where, it may be recalled, $u_{i_{k}}(x_{k})=v_{k}$. Moreover, we have the
following.

######  Lemma 4.4.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs,
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$,
and $\tilde{v},\tilde{w}\in V(\Gamma)$. Then all paths of minimal length from
$\tilde{v}$ to $\tilde{w}$ have the same transition points.

###### Proof.

If $\gamma$ transitions at $m$ then $\tilde{x}_{m}$ is a cut vertex and
deleting $\tilde{x}_{m}$ disconnects $\Gamma$ so that $\tilde{v}$ lies in one
component and $\tilde{w}$ in the other. Indeed, if $\tilde{w}$ lay in the same
component as $\tilde{v}$, then $\gamma$ would return to that component through
$\tilde{x}_{m}$ and could be shortened. Every path from $\tilde{v}$ to
$\tilde{w}$ must therefore pass through $\tilde{x}_{m}$. ∎

The following proposition states in particular that every mashup is a quotient
of its associated free product.

######  Proposition 4.5.

Let $M$ be a mashup of $\Gamma_{1}$, …, $\Gamma_{n}$. Further, let $x_{0}\in
V(M)$ and $\smash{u_{i}:=\varphi^{-1}_{(x_{0},i)}(x_{0})}$
($i\in\\{1,\dots,n\\}$). Initialise
$\Gamma:=\smash{\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}}$
by $\mathbf{u}(\emptyset)=(u_{1},\dots,u_{n})$. Then there is a surjective
graph homomorphism $\smash{\psi:\Gamma\to M}$ with $\psi(\emptyset)=x_{0}$ and
$\mathbf{u}(\psi(\tilde{v}))=\mathbf{u}(\tilde{v})$ for all $\tilde{v}\in
V(\Gamma)$.

###### Proof.

We argue by induction on the natural number $l$ in
$V(\Gamma)=\bigcup_{l\in\operatorname{\mathbb{N}}_{0}}V^{(l)}$. Define
$\psi(\emptyset)=x_{0}$ and extend $\psi$ to $V^{(1)}$ by setting

(8) $\psi(v_{1}):=\varphi_{(x_{0},i)}(v_{1})\mbox{ if
}v_{1}\in\Gamma_{i}\setminus\\{u_{i}=\varphi^{-1}_{(x_{0},i)}(x_{0})\\}.$

Then $\psi$ is a morphism from $\mathrm{span}_{\Gamma}(V^{(0)}\cup V^{(1)})$
to $M$ since $\psi(\emptyset)=x_{0}=\varphi_{(x_{0},i)}(u_{i})$, by Definition
3.1 (4) of the neighbours of $\emptyset\in V(\Gamma)$, and since
$\varphi_{(x_{0},i)}$ is a morphism.

By Definition 4.1d, the map $\smash{y\mapsto\varphi^{-1}_{(y,j)}(y)}$ is
constant on $\psi(S_{(\emptyset,i)})=\varphi_{(x_{0},i)}(\Gamma_{i})$ for any
$j\in\\{1,\ldots,n\\}\backslash\\{i\\}$. The definition of the initial value
of $\mathbf{u}$ implies that this constant is equal to
$\smash{\varphi^{-1}_{(x_{0},j)}(x_{0})=u_{j}=u_{j}(\emptyset)}$.

Now, suppose $\psi$ is defined on
$\mathrm{span}_{\Gamma}(\bigcup_{k=0}^{l}V^{(k)})$ and for $y=\psi(v_{1}\dots
v_{k})$ satisfies

(9) $\varphi^{-1}_{(y,i)}(y)=\begin{cases}v_{k}&\mbox{ if }v_{k}\in
V(\Gamma_{i})\\\ u_{i}(v_{1}\dots v_{k})&\mbox{ if }v_{k}\in V(\Gamma_{j}),\
j\neq i\end{cases},\qquad(k\in\\{1,\dots,l\\}).$

This holds for $l=1$ by the above. Now, consider $\tilde{v}v_{l+1}=v_{1}\dots
v_{l}v_{l+1}\in V^{(l+1)}$, where $v_{l}\in V_{i}$, $v_{l+1}\in V_{j}$ and
$i\neq j$. In particular, $v_{l+1}\neq u_{j}(\tilde{v})$. Set
$y:=\psi(\tilde{v})$ and

$\psi(\tilde{v}v_{l+1}):=\varphi_{(y,j)}(v_{l+1}).$

Since (9) implies that $\varphi_{(y,j)}(u_{j}(\tilde{v}))=y$, it follows that
$\psi$ is a morphism from $S_{(\tilde{v},j)}$ to the $\Gamma_{j}$-sheet of $M$
containing $y$. By (6) of $E(\Gamma)$, this extension of $\psi$ is a morphism
$\mathrm{span}_{\Gamma}(\smash{\bigcup_{k=0}^{l+1}V^{(k)})\to M}$. To see that
(9) extends to the case $k=l+1$, observe that
$\smash{\varphi^{-1}_{(z,j)}(z)=v_{l+1}}$ for $z=\psi(\tilde{v}v_{l+1})$ by
definition and, for $h\neq j$,

$\varphi^{-1}_{(z,h)}(z)=\varphi^{-1}_{(y,h)}(y)=\begin{cases}v_{l}=u_{i}(\tilde{v})&\mbox{
if }h=i\\\ u_{h}(\tilde{v})&\mbox{ if }h\neq i\end{cases},$

where the first equality holds by Definition 4.1d and the second row of the
second equality holds by (9) with $k=l$. Since
$u_{h}(\tilde{v}v_{l+1})=u_{h}(\tilde{v})$ for $h\neq j$, (9) extends.

Continuing recursively produces the claimed morphism $\psi$, which is
surjective by Lemma 2.1, the connectedness of $M$, and conditions a and b in
Definition 4.1. ∎

Using Example 4.3ii, the following is a consequence of Proposition 4.5.

######  Corollary 4.6.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs. Then
$\mathbf{u}:\\!\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}\\!\to\\!\Gamma_{1}\times\dots\times\Gamma_{n}$
is a graph homomorphism. ∎

We now show that the isomorphism class of a free product is independent of the
initialisation of its update function.

######  Corollary 4.7.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs and let $\Gamma$ and
$\Gamma^{\prime}$ be the free products of $\Gamma_{1},\ldots,\Gamma_{n}$ with
respect to $(u_{1},\dots,u_{n})$ and $(u_{1}^{\prime},\dots,u_{n}^{\prime})$
in $\prod_{i=1}^{n}V(\Gamma_{i})$. Then $\Gamma$ and $\Gamma^{\prime}$ are
isomorphic.

###### Proof.

Let $\mathbf{u}$ and $\mathbf{u}^{\prime}$ denote the update functions on
$\Gamma$ and $\Gamma^{\prime}$ respectively. Choose $\tilde{v}_{0}\in
V(\Gamma^{\prime})$ such that
$\mathbf{u}^{\prime}(\tilde{v}_{0})=(u_{1},\dots,u_{n})$. Since
$\Gamma^{\prime}$ is a mashup of $\Gamma_{1}$, …, $\Gamma_{n}$, there is, by
Proposition 4.5, a surjective homomorphism $\psi:\Gamma\to\Gamma^{\prime}$
with $\psi(\emptyset)=\tilde{v}_{0}$.

To see that $\psi$ is injective, we construct a left inverse: Interchanging
the roles of $\Gamma$ and $\Gamma^{\prime}$, Proposition 4.5 also yields a
surjective homomorphism $\psi^{\prime}:\Gamma^{\prime}\to\Gamma$. Since
$\psi^{\prime}$ is surjective, there is $\tilde{v}^{\prime}_{0}\in
V(\Gamma^{\prime})$ such that
$\psi^{\prime}(\tilde{v}^{\prime}_{0})=\emptyset\in V(\Gamma)$. Proposition
4.5 ensures that
$\mathbf{u}^{\prime}(\tilde{v}^{\prime}_{0})=\mathbf{u}(\psi^{\prime}(\tilde{v}_{0}^{\prime}))=\mathbf{u}(\emptyset)=(u_{1},\dots,u_{n})$.
Hence $\tilde{v}_{0}$ from the previous paragraph may be chosen to be
$\tilde{v}^{\prime}_{0}$. Then the composition
$\psi^{\prime}\circ\psi:\Gamma\to\Gamma$ is surjective and satisfies
$\psi^{\prime}\circ\psi(\emptyset)=\emptyset$ as well as
$\mathbf{u}(\psi^{\prime}\circ\psi(\tilde{v}))=\mathbf{u}(\tilde{v})$ for
every $\tilde{v}\in V(\Gamma)$.

It remains to show that $\psi^{\prime}\circ\psi$ is the identity homomorphism.
We argue by induction on the distance of a vertex from the empty word, given
that $\psi^{\prime}\circ\psi(\emptyset)=\emptyset$. Suppose
$\psi^{\prime}\circ\psi(\tilde{v})=\tilde{v}$ for every $\tilde{v}$ with
$d(\emptyset,\tilde{v})\leq d$. Consider $\tilde{w}$ with
$d(\emptyset,\tilde{w})=d+1$. Then there is a neighbour, $\tilde{v}$ of
$\tilde{w}$ with $d(\emptyset,\tilde{v})=d$ and a unique $i\in\\{1,\dots,n\\}$
such that $\\{\tilde{v},\tilde{w}\\}$ belongs to $S_{(\tilde{v},i)}$. Since
$\psi^{\prime}\circ\psi(\tilde{v})=\tilde{v}$ and
$u_{i}(\psi^{\prime}\circ\psi(\tilde{w}))=u_{i}(\tilde{w})$, it follows that
$\psi^{\prime}\circ\psi(\tilde{w})$ equals $\tilde{w}$. ∎

The proof of Corollary 4.7 entails that if $\tilde{v}\in
V(\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i})$
satisfies $\mathbf{u}(\tilde{v})=\mathbf{u}(\emptyset)$, then there is an
automorphism
$\alpha\in\operatorname{Aut}(\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i})$
such that $\alpha(\emptyset)=\tilde{v}$ and

(10) $\mathbf{u}(\alpha(\tilde{w}))=\mathbf{u}(\tilde{w})\mbox{ for every
}\tilde{w}\in
V(\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}).$

######  Corollary 4.8.

Let $\Gamma_{1},\Gamma_{2},\Gamma_{3}$ be connected graphs and
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{3}\Gamma_{i}$.
Then

$(\Gamma_{1}\ast\Gamma_{2})\ast\Gamma_{3}\cong\Gamma\cong\Gamma_{1}\ast(\Gamma_{2}\ast\Gamma_{3}).$

###### Proof.

The graph $\Gamma^{\prime}:=(\Gamma_{1}\ast\Gamma_{2})\ast\Gamma_{3}$ is
naturally a mashup of the graphs $\Gamma_{1},\Gamma_{2},\Gamma_{3}$, where the
embeddings $\varphi_{(x,i)}:\Gamma_{i}\to\Gamma^{\prime}$ ($x\in
V(\Gamma^{\prime})$, $i\in\\{1,2,3\\}$) come from the structure of
$\Gamma^{\prime}$ as a free product of $\Gamma_{1}\ast\Gamma_{2}$ and
$\Gamma_{3}$, and the structure of $\Gamma_{1}\ast\Gamma_{2}$ as a free
product of $\Gamma_{1}$ and $\Gamma_{2}$. Hence, by Proposition 4.5, there is
a surjective graph homomorphism $\psi:\Gamma\to\Gamma^{\prime}$ intertwining
the update functions. As a consequence, $\psi$ is completely determined, and
in particular injective, on balls of arbitrary radius around $\emptyset\in
V(\Gamma)$ by induction. Hence it is injective overall. Proceed analogously in
the case of $\Gamma_{1}\ast(\Gamma_{2}\ast\Gamma_{3})$. ∎

##  5\. Comparison of definitions of the free product

Here, we show that the definitions presented in Sections 3.1 to 3.4, which we
will denote, respectively, by $\ast_{1}$ up to $\ast_{4}$ in this section, are
equivalent when the graphs are vertex-transitive. First, we highlight the
obvious differences, namely: $\ast_{2}$ is defined only for pairs of graphs
that are vertex-transitive; and $\ast_{3}$ and $\ast_{4}$ are defined only for
rooted graphs and produce rooted graphs. The equivalence of $\ast_{3}$ and
$\ast_{4}$ with $\ast_{1}$ arises because all choices of root vertex are
equivalent when a graph is vertex-transitive.

We now turn to the various constructions. In all cases, vertex-transitivity of
the factors is required to account for the fact that in the genesis of all
graphs, new sheets are attached to the existing part at different vertices.

######  Proposition 5.1.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be connected, vertex-transitive graphs. Then
the graphs $\Gamma_{1}\ast_{1}\Gamma_{2}$ and $\Gamma_{1}\ast_{2}\Gamma_{2}$
are isomorphic.

###### Proof.

Let $\Gamma^{\prime}:=\Gamma_{1}\ast_{2}\Gamma_{2}$. Recall that there is a
bijection $V(\Gamma^{\prime})\to E(T_{m,n})$ with the vertex $x\in
V(\Gamma^{\prime})$, corresponding to $\\{v,w\\}\in E(T_{m,n})$, being defined
by identifying $\psi^{-1}_{v}(\\{v,w\\})\in V(\Gamma^{(v)})$ with
$\psi^{-1}_{w}(\\{v,w\\})\in V(\Gamma^{(w)})$. Pick $x_{0}\in
V(\Gamma^{\prime})$ corresponding to $\\{v_{0},w_{0}\\}\in E(T_{m,n})$ and
initialise $\Gamma:=\Gamma_{1}\ast_{1}\Gamma_{2}$ with

$\smash{\mathbf{u}(\emptyset)=(\psi^{-1}_{v_{0}}(\\{v_{0},w_{0}\\}),\psi^{-1}_{w_{0}}(\\{v_{0},w_{0}\\}))}.$

Recall that $V^{(l)}$ denotes the set of admissible words of length $l$ in
$V(\Gamma)$ and define $\varphi:\Gamma\to\Gamma^{\prime}$ inductively on $l$
as follows. Set $\varphi(\emptyset)=x_{0}$. Next, $\smash{p\in V^{(1)}}$ lies
on either the $\Gamma_{1}$-sheet or the $\Gamma_{2}$-sheet at $\emptyset$,
that is, either $p\in
V(\Gamma_{1})\setminus\\{\psi^{-1}_{v_{0}}(\\{v_{0},w_{0}\\})\\}$ or $p\in
V(\Gamma_{2})\setminus\\{\psi^{-1}_{w_{0}}(\\{v_{0},w_{0}\\})\\}$. Define
$\varphi(p)=p\in V(\Gamma^{(v_{0})})\subset V(\Gamma^{\prime})$ in the first
case and $\varphi(p)=p\in V(\Gamma^{(w_{0})})\subset V(\Gamma^{\prime})$ in
the second. Then $\varphi$ is an isomorphism

$\mathrm{span}_{\Gamma}(V^{(0)}\cup
V^{(1)})\to\bigl{(}\Gamma^{(v_{0})},\psi^{-1}_{v_{0}}(\\{v_{0},w_{0}\\})\bigr{)}\\#\bigl{(}\Gamma^{(w_{0})},\psi^{-1}_{w_{0}}(\\{v_{0},w_{0}\\})\bigr{)}$

Now suppose that $\varphi$ has been defined on words up to length
$l\in\operatorname{\mathbb{N}}_{\geq 1}$ and consider $\tilde{p}=p_{1}\ldots
p_{l}\in V^{(l)}$. Without loss of generality, assume that $p_{l}\in
V(\Gamma_{1})$. Then the $\Gamma_{2}$-sheet of $\Gamma$ at $\tilde{p}$ is
attached at $u_{2}(\tilde{p})$, while, if $\varphi(\tilde{p})\in
V(\Gamma^{\prime})$ corresponds to $\\{v,w\\}\in E(T_{m,n})$, then
$\varphi(\tilde{p})$ is identified with $\psi^{-1}_{w}(\\{v,w\\})\in
V(\Gamma^{(w)})$. Since $\Gamma_{2}$ is vertex-transitive, there is
$\alpha_{\tilde{p}}\in\operatorname{Aut}(\Gamma_{2})$ such that
$\smash{\alpha_{\tilde{p}}(u_{2}(\tilde{p}))}=\psi^{-1}_{w}(\\{v,w\\})$.
Choose such $\alpha_{\tilde{p}}$ for each ${\tilde{p}}\in V^{(l)}$ and extend
the definition of $\varphi$ to ${\tilde{p}}p_{l+1}\in V^{(l+1)}$ by

$\varphi(\tilde{p}p_{l+1}):=\begin{cases}\alpha_{\tilde{p}}(p_{l+1})\in
V(\Gamma^{(w)})\setminus\\{\psi^{-1}_{w}(\\{v,w\\})\\},&\mbox{ if }p_{l}\in
V(\Gamma_{1})\\\ \alpha_{\tilde{p}}(p_{l+1})\in
V(\Gamma^{(v)})\setminus\\{\psi^{-1}_{v}(\\{v,w\\})\\},&\mbox{ if }p_{l}\in
V(\Gamma_{2})\end{cases}.$

Since $\alpha_{\tilde{p}}$ is an automorphism for each ${\tilde{p}}\in
V^{(l)}$, it follows that $\varphi$ is a graph isomorphism. ∎

As an immediate consequence of Corollary 4.7 and Proposition 5.1 we see that
the definition of $\ast_{2}$ does not depend on the choice of the bijections
involved.

######  Corollary 5.2.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be connected, vertex-transitive graphs. Then
the isomorphism type of $\Gamma_{1}\ast_{2}\Gamma_{2}$ is well-defined.

As to the definition of Pisanski–Tucker in Section 3.3, we have the following.

######  Proposition 5.3.

Let $(\Gamma_{1},r_{1})$ and $(\Gamma_{2},r_{2})$ be connected, vertex-
transitive, rooted graphs. Then the graphs $\Gamma_{1}\ast_{1}\Gamma_{2}$ and
$\Gamma_{1}\ast_{3}\Gamma_{2}$ are isomorphic.

###### Proof.

Let $\Gamma^{\prime}:=\Gamma_{1}\ast_{3}\Gamma_{2}$. Initialise
$\Gamma:=\Gamma_{1}\ast_{1}\Gamma_{2}$ with $u(\emptyset)=(r_{1},r_{2})$. Now
define $\varphi:\Gamma\to\Gamma^{\prime}$ as follows: Set
$\varphi(\emptyset)=\varepsilon$, where $\varepsilon\in V(\Gamma^{\prime})$ is
the empty string, and assume that $\varphi$ has been defined on words up to
length $l\in\operatorname{\mathbb{N}}_{0}$. Consider $\tilde{v}=v_{1}\ldots
v_{l}\in V(\Gamma)$ and suppose $\tilde{v}v_{l+1}\in V(\Gamma)$, where
$v_{l+1}\in V(\Gamma_{i})$. Since $\Gamma_{i}$ is vertex-transitive, there is
$\alpha\in\operatorname{Aut}(\Gamma_{i})$ such that
$\alpha(u_{i}(\tilde{v}))=r_{i}$. Define
$\varphi(\tilde{v}v_{l+1})=\varphi(\tilde{v})\alpha(v_{l+1})$. Since all the
maps $\alpha$ are automorphisms, it follows that $\varphi$ is a graph
isomorphism. ∎

A similar argument applies in the case of Quenell’s definition from Section
3.4.

######  Proposition 5.4.

Let $(\Gamma_{1},r_{1})$ and $(\Gamma_{2},r_{2})$ be connected, vertex-
transitive, rooted graphs. Then the graphs $\Gamma_{1}\ast_{1}\Gamma_{2}$ and
$\Gamma_{1}\ast_{4}\Gamma_{2}$ are isomorphic. ∎

##  6\. Automorphisms of Free Product Graphs

It was seen in Equation 10 that free product graphs admit many automorphisms
which preserve the update function. Three additional types of automorphisms of
free product graphs are described in this section.

The first proposition shows that further automorphisms arise from
automorphisms of the free product’s factors.

######  Proposition 6.1.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs and initialise
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$
with
$\mathbf{u}(\emptyset)=(u_{1},\dots,u_{n})\in\prod_{i=1}^{n}V(\Gamma_{i})$.
Given $j\\!\in\\!\\{1,\ldots,n\\}$ and
$\alpha\\!\in\\!\operatorname{Aut}(\Gamma_{j})$ define

$\tilde{\alpha}:\bigsqcup_{i=1}^{n}V(\Gamma_{i})\to\bigsqcup_{i=1}^{n}V(\Gamma_{i}),\
v\mapsto\begin{cases}v&\text{if }v\in V(\Gamma_{i}),\ i\neq j\\\
\alpha(v)&\text{if }v\in V(\Gamma_{j})\end{cases}.$

Let $\tilde{v}\\!=\\!v_{1}\ldots v_{l}\in V(\Gamma)$. When
$\alpha(u_{j})\\!=\\!u_{j}$, let
$\hat{\alpha}(\tilde{v})\\!:=\\!\tilde{\alpha}(v_{1})\dots\tilde{\alpha}(v_{l})$.
Otherwise, set

$\hat{\alpha}(\tilde{v}):=\begin{cases}\alpha(u_{j})\tilde{\alpha}(v_{1})\dots\tilde{\alpha}(v_{l})&\text{if
}v_{1}\not\in\Gamma_{j}\mbox{ or }l=0\\\
\tilde{\alpha}(v_{2})\dots\tilde{\alpha}(v_{l})&\text{if
}v_{1}\in\Gamma_{j}\mbox{ and }\alpha(v_{1})=u_{j}\\\
\tilde{\alpha}(v_{1})\dots\tilde{\alpha}(v_{l})&\text{otherwise}\end{cases}.$

Then $\hat{\alpha}\\!\in\\!\operatorname{Aut}(\Gamma)$ and the map
$\operatorname{Aut}(\Gamma_{j})\\!\to\\!\operatorname{Aut}(\Gamma),\
\alpha\mapsto\hat{\alpha}$ is a group monomorphism. Moreover,
$\mathbf{u}\circ\hat{\alpha}=\overline{\alpha}\circ\mathbf{u}$, where
$\overline{\alpha}=\operatorname{id}\times\dots\times\alpha\times\dots\times\operatorname{id}\in\operatorname{Aut}(\prod_{i=1}^{n}\Gamma_{i})$.

###### Proof.

We first show that $\hat{\alpha}(\tilde{v})\\!\in\\!V(\Gamma)$. Since
$\tilde{\alpha}$ preserves $V(\Gamma_{i})$ for all
$i\\!\in\\!\\{1,\ldots,n\\}$, any two consecutive letters in the word
$\hat{\alpha}(\tilde{v})$ belong to distinct graphs. As to the other half of
Equation (2), note that only the $j$-th component of $\mathbf{u}$ is affected
by $\hat{\alpha}$. Let $k_{1}<\cdots<k_{r}\in\\{1,\ldots,l\\}$ be the indices
for which $v_{k_{s}}\in V(\Gamma_{j})$ ($s\in\\{1,\ldots,r\\}$).

First, consider the case when $\alpha(u_{j})=u_{j}$. Since $\tilde{v}\in
V(\Gamma)$, we have $v_{k_{1}}\neq u_{j}$ and $v_{k_{s+1}}\neq v_{k_{s}}$ for
$s\geq 1$. Then $\alpha(v_{k_{1}})\neq u_{j}$ and
$\alpha(v_{k_{s+1}})\neq\alpha(v_{k_{s}})$ for $s\geq 1$ because
$\alpha(u_{j})=u_{j}$ and $\alpha$ is a bijection. Hence
$\hat{\alpha}(\tilde{v})\in V(\Gamma)$. The assertion
$\mathbf{u}\circ\hat{\alpha}=\overline{\alpha}\circ\mathbf{u}$ is immediate
from the definition of $\hat{\alpha}$.

Now suppose $\alpha(u_{j})\neq u_{j}$. There are several cases to consider: If
$l=0$ or $v_{1}\not\in\Gamma_{j}$, then the first letter of
$\hat{\alpha}(\tilde{v})$ is $\alpha(u_{j})$, which belongs to $\Gamma_{j}$
and is not equal to $u_{j}$. The remaining letters from $\Gamma_{j}$ are
$\alpha(v_{k_{s}})$ ($s\geq 1$) and satisfy
$\alpha(v_{k_{1}})\neq\alpha(u_{j})$ and
$\alpha(v_{k_{s+1}})\neq\alpha(v_{k_{s}})$ ($s\geq 1$) because $\alpha$ is a
bijection. If $v_{1}\in\Gamma_{j}$ and $\alpha(v_{1})=u_{j}$, then the letters
from $\Gamma_{j}$ are $\alpha(v_{k_{s}})$ ($s\geq 2$) and satisfy
$\alpha(v_{k_{2}})\neq u_{j}$ and $\alpha(v_{k_{s+1}})\neq\alpha(v_{k_{s}})$
($s\geq 2$) because $v_{k_{2}}\neq v_{1}$ and $\alpha$ is a bijection.
Finally, if $v_{1}\in\Gamma_{j}$ and $\alpha(v_{1})\neq u_{j}$, then $k_{1}=1$
and we have that $\alpha(v_{k_{1}})\neq u_{j}$ and
$\alpha(v_{k_{s+1}})\neq\alpha(v_{k_{s}})$ ($s\geq 1$). Again, we conclude
$\mathbf{u}\circ\hat{\alpha}=\overline{\alpha}\circ\mathbf{u}$.

To see that $\hat{\alpha}\in\operatorname{Aut}(\Gamma)$, recall that every
edge of $\Gamma$ belongs to a unique sheet. Since $\hat{\alpha}$ preserves
$\Gamma_{j}$-sheets and acts like $\alpha$ on every such sheet, edge relations
within $\Gamma_{j}$-sheets are preserved. Furthermore, $\hat{\alpha}$ permutes
the $\Gamma_{i}$-sheets attached to a given $\Gamma_{j}$-sheet and acts like
the identity on every such $\Gamma_{i}$-sheet. Hence edge-relations in
$\Gamma_{i}$-sheets ($i\neq j$) are preserved as well. We conclude that
$\hat{\alpha}\in\operatorname{Aut}(\Gamma)$.

The fact that $\hat{\alpha}$ preserves $\Gamma_{j}$-sheets and acts like
$\alpha$ on every such sheet implies that the map
$\operatorname{Aut}(\Gamma_{i})\to\operatorname{Aut}(\Gamma)$,
$\alpha\mapsto\hat{\alpha}$ is an injective homomorphism. ∎

######  Remark 6.2.

Retain the notation of Proposition 6.1. In the context of cartesian products,
images of distinct embeddings
$\operatorname{Aut}(\Gamma_{j})\\!\to\\!\operatorname{Aut}(\prod_{i=1}^{n}\Gamma_{i})$,
$\alpha\mapsto\overline{\alpha}$ commute, whereas commutators of automorphisms
in distinct images under the embeddings
$\operatorname{Aut}(\Gamma_{j})\to\operatorname{Aut}(\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i})$,
$\alpha\mapsto\hat{\alpha}$ yield automorphisms of the type in Equation (10).

######  Example 6.3.

Consider the free product $\Gamma:=T_{1}\ast T_{1}\cong T_{2}$. Here,
$\operatorname{Aut}(T_{1})\cong C_{2}$ and the two embedded automorphism
groups of Proposition 6.1 generate the infinite dihedral group $C_{2}\ast
C_{2}\cong D_{\infty}=\operatorname{Aut}(T_{2})$. In particular, they do not
commute.

Retain the notation of Proposition 6.1. Even if we choose groups
$G_{i}\leq\operatorname{Aut}(\Gamma_{i})$ $i\in\\{1,\ldots,n\\}$ with finitely
many vertex-orbits on the respective $\Gamma_{i}$, the induced group
$\smash{G:=\langle\widehat{G}_{1},\dots,\widehat{G}_{n}\rangle\leq\operatorname{Aut}(\Gamma)}$
need not have finitely many vertex-orbits on $\Gamma$: For example, let
$\Gamma_{i}$ $(i\in\\{1,\ldots,n\\})$ be finite and choose $G_{i}$ to be
trivial. Then the free product is infinite but $G$ is trivial. However, we
have the following result.

######  Corollary 6.4.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected, vertex-transitive graphs.
Then the free product
$\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$
is vertex-transitive as well.

###### Proof.

Set
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$.
Let $\tilde{v},\tilde{w}\in V(\Gamma)$ and let $\gamma=(e_{1},\ldots,e_{k})$
be a path from $\tilde{v}$ to $\tilde{w}$ with transition points
$x_{1},\ldots,x_{l}\in V(\Gamma)$. By choosing the base points
$x_{0}:=\tilde{v},x_{1},\ldots,x_{l},x_{l+1}:=\tilde{w}$ for $\Gamma$,
Proposition 6.1 and vertex-transitivity of the $\Gamma_{i}$
($i\in\\{1,\ldots,n\\}$) yield automorphisms
$\alpha_{1},\ldots,\alpha_{l+1}\in\operatorname{Aut}(\Gamma)$ such that
$\alpha_{i}(x_{i-1})\\!=\\!x_{i}$ ($i\in\\{1,\ldots,l+1\\}$). Then
$\alpha_{l+1}\circ\cdots\circ\alpha_{1}$ maps $\tilde{v}$ to $\tilde{w}$. ∎

The maps $\operatorname{Aut}(\Gamma_{j})\to\operatorname{Aut}(\Gamma)$ of
Proposition 6.1 are topological embeddings.

######  Proposition 6.5.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs and initialise
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$
with
$\mathbf{u}(\emptyset)=(u_{1},\dots,u_{n})\in\prod_{i=1}^{n}V(\Gamma_{i})$.
For every $j\in\\{1,\ldots,n\\}$, the injective homomorphism
$\varphi_{j}:\operatorname{Aut}(\Gamma_{j})\to\operatorname{Aut}(\Gamma)$,
$\alpha\mapsto\hat{\alpha}$ is a topological embedding.

###### Proof.

Consider the identity neighbourhood bases
$U_{n}:=\operatorname{Aut}(\Gamma)_{B_{\Gamma}(\emptyset,n)}$
$(n\in\operatorname{\mathbb{N}})$ and
$\smash{V_{n}:=\operatorname{Aut}(\Gamma_{j})_{B_{\Gamma_{j}}(u_{j},n)}}$
($n\in\operatorname{\mathbb{N}}$) for $\operatorname{Aut}(\Gamma)$ and
$\operatorname{Aut}(\Gamma_{j})$ respectively. We have
$\smash{\varphi_{j}^{-1}(U_{n})=V_{n}}$: On the one hand,
$\smash{\varphi_{j}^{-1}(U_{n})\subseteq V_{n}}$ because
$\smash{B_{S_{(\emptyset,j)}}(\emptyset,n)\subseteq B_{\Gamma}(\emptyset,n)}$
and $\varphi_{j}(\alpha)$ restricts to $\alpha$ on
$\smash{S_{(\emptyset,j)}}$. Conversely,
$\smash{\varphi_{j}^{-1}(U_{n})\supseteq V_{n}}$ by definition of
$\varphi_{j}$ and because $d_{\Gamma_{j}}(u_{j}(x),u_{j})\leq
d_{\Gamma}(x,\emptyset)$ for all $x\in V(\Gamma)$. Also,
$\varphi_{j}(V_{n})=U_{n}\cap\varphi_{j}(\operatorname{Aut}(\Gamma_{j}))$,
hence $\varphi_{j}$ is a homeomorphism onto its image. ∎

Automorphisms of Proposition 6.1 that fix $\emptyset\\!\in\\!V(\Gamma)$ are
also covered by the following proposition, whose greater flexibility entails
that $\operatorname{Aut}(\Gamma)$ is often non-discrete. The notation
$\lambda(\tilde{v})$ for a vertex $\tilde{v}\\!=\\!v_{1}\ldots v_{l}$ in a
free product
$\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$
refers to the index $i\\!\in\\!\\{1,\ldots,n\\}$ such that
$v_{l}\\!\in\\!V(\Gamma_{i})$. We leave $\lambda(\emptyset)$ undefined and set
$\\{\lambda(\emptyset)\\}\\!:=\\!\emptyset$.

######  Proposition 6.6.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs and initialise
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$
with
$\mathbf{u}(\emptyset)=(u_{1},\ldots,u_{n})\\!\in\\!\prod_{i=1}^{n}V(\Gamma_{i})$.
For every $\tilde{v}\\!\in\\!V(\Gamma)$ and
$i\\!\in\\!\\{1,\dots,n\\}\setminus\\{\lambda(\tilde{v})\\}$ let
$\beta_{(\tilde{v},i)}\in\operatorname{Aut}(\Gamma_{i})$. Recursively define
$\beta$ on $V(\Gamma)$ by setting $\beta(\emptyset):=\emptyset$ and, for
$\tilde{v}\in V(\Gamma)\setminus\\{\emptyset\\}$ and $v_{l+1}\in
V(\Gamma_{i})$ with $i\in\\{1,\dots,n\\}\setminus\\{\lambda(\tilde{v})\\}$,

(11) $\beta(\tilde{v}v_{l+1})=\beta(\tilde{v})\beta_{(\tilde{v},i)}(v_{l+1}).$

Then $\beta\\!\in\\!\operatorname{Aut}(\Gamma)$ if
$\beta_{(\tilde{v},i)}(u_{i}(\tilde{v}))\\!=\\!u_{i}(\beta(\tilde{v}))$ for
all $\tilde{v}\\!\in\\!V(\Gamma)$ and
$i\\!\in\\!\\{1,\dots,n\\}\setminus\\{\lambda(\tilde{v})\\}$.

###### Proof.

First we show that $\beta(\tilde{v})\in V(\Gamma)$. Since
$\beta_{(\tilde{v},i)}(v_{l+1})\in V(\Gamma_{i})$, the first half of Equation
(2) is satisfied. The condition that $v_{l+1}\neq u_{i}(\tilde{v})$ is
preserved as well: Since
$\beta_{(\tilde{v},i)}(u_{i}(\tilde{v}))=u_{i}(\beta(\tilde{v}))$ and
$\beta_{(\tilde{v},i)}$ is a bijection, we have
$\beta_{(\tilde{v},i)}(v_{l+1})\neq u_{i}(\beta(\tilde{v}))$.

Next, we show that $\beta$ preserves all edge relations. Every edge $e$ of
$\Gamma$ belongs to a unique $\Gamma_{i}$-sheet $S_{(\tilde{v},i)}$ for a
unique $i$. If $e$ is not incident on $\tilde{v}$, then
$e=\\{\tilde{v}v_{l+1},\tilde{v}v^{\prime}_{l+1}\\}$ for some $\\{v_{l+1}$,
$v^{\prime}_{l+1}\\}\in E(\Gamma_{i})$ and
$\beta(e)=\\{\beta(\tilde{v})\beta_{(\tilde{v},i)}(v_{l+1}),\beta(\tilde{v})\beta_{(\tilde{v},i)}(v^{\prime}_{l+1})\\}$
is an edge in the $\Gamma_{i}$-sheet $S_{(\beta(\tilde{v}),i)}$ because
$\beta_{(\tilde{v},i)}$ is an automorphism of $\Gamma_{i}$. If $e$ is incident
on $\tilde{v}$, then $e=\\{\tilde{v},\tilde{v}v_{l+1}\\}$ for some $v_{l+1}\in
V(\Gamma_{i})$ such that $\\{u_{i}(\tilde{v}),v_{l+1}\\}$ in $E(\Gamma_{i})$.
Then
$\beta(e)=\\{\beta(\tilde{v}),\beta(\tilde{v})\beta_{(\tilde{v},i)}(v_{l+1})\\}$
is an edge in the $\Gamma_{i}$-sheet $S_{(\beta(\tilde{v}),i)}$ because
$\\{u_{i}(\beta(\tilde{v})),\beta_{(\tilde{v},i)}(v_{l+1})\\}\in
E(\Gamma_{i})$. ∎

######  Corollary 6.7.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ $(n\\!\geq\\!2)$ be connected graphs and
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$.
If $\operatorname{Aut}(\Gamma_{j})_{u}\neq\\{\operatorname{id}\\}$ for some
$j\\!\in\\!\\{1,\ldots,n\\}$ and $u\\!\in\\!V(\Gamma_{j})$ then
$\operatorname{Aut}(\Gamma)$ is non-discrete.

###### Proof.

Initalise $\Gamma$ with
$\mathbf{u}(\emptyset)=(u_{1},\ldots,u_{n})\\!\in\\!\prod_{i=1}^{n}V(\Gamma_{i})$.
By Corollary 4.7 we may assume $u_{j}=u$. It suffices to show that the
stabiliser $\operatorname{Aut}(\Gamma)_{B(\emptyset,k)}$ of the ball
$B(\emptyset,k)$ of radius $k$ around $\emptyset\in V(\Gamma)$ is non-trivial
for every $k\in\operatorname{\mathbb{N}}$. Let
$\beta_{0}\in\operatorname{Aut}(\Gamma_{j})_{u}$ be non-trivial. For every
$\tilde{v}_{0}\in V(\Gamma)$ with $\lambda(\tilde{v}_{0})\neq j$ and
$u_{j}(\tilde{v}_{0})=u$ define $\smash{\beta^{(\tilde{v}_{0})}}$ as in
Proposition 6.6 by setting

$\beta^{(\tilde{v}_{0})}_{(\tilde{v},i)}:=\begin{cases}\beta_{0}&\text{if
$\tilde{v}_{0}$ is a prefix of $\tilde{v}$ and $i=j$}\\\
\operatorname{id}&\text{otherwise}\end{cases}.$

Then $\beta^{(\tilde{v}_{0})}\in\operatorname{Aut}(\Gamma)$ by Proposition
6.6: To begin, we have

$\beta^{(\tilde{v}_{0})}_{(\tilde{v}_{0},j)}(u_{j}(\tilde{v}_{0}))=\beta_{0}(u)=u=u_{j}(\tilde{v}_{0})=u_{j}(\beta^{(\tilde{v}_{0})}(\tilde{v}_{0})).$

Further, if $\tilde{v}_{0}=v_{1}\ldots v_{l}$ is a prefix of
$\tilde{v}=v_{1}\ldots v_{m}$ with $\lambda(\tilde{v})\neq j$, and the last
letter from $\Gamma_{j}$ in the word $\tilde{v}$ has index $k>l$ then
$\beta^{(\tilde{v}_{0})}_{(\tilde{v},j)}(u_{j}(\tilde{v}))=\beta_{0}(v_{k})=u_{j}(\beta^{(\tilde{v}_{0})}(\tilde{v}))$.
In all other cases, we have
$\beta^{(\tilde{v}_{0})}_{(\tilde{v},i)}(u_{i}(\tilde{v}))=u_{i}(\beta^{(\tilde{v}_{0})}(\tilde{v}))$
for all $i\in\\{1,\ldots,n\\}\backslash\lambda(\tilde{v})$ because neither
$\beta^{(\tilde{v}_{0})}$ nor $\beta^{(\tilde{v}_{0})}_{(\tilde{v},i)}$ impact
the $i$-th coordinate of $\mathbf{u}$. Since there are choices for
$\tilde{v}_{0}$ with $d(\emptyset,\tilde{v}_{0})$ arbitrarily large, resulting
in automorphisms $\beta^{(\tilde{v}_{0})}$ that stabilise
$B(\emptyset,d(\emptyset,\tilde{v}_{0}))$ pointwise, the assertion follows ∎

In a similar fashion, we see that $\operatorname{Aut}(\Gamma)$ is also non-
discrete when $\Gamma$ has at least three factors, two of which are isomorphic
and vertex-transitive. In contrast to Corollary 6.7, this applies to graphs
with a regular automorphism group. Note that the assumption $n\geq 3$ cannot
be weakened to $n\geq 2$ as the case $\Gamma:=T_{1}\ast T_{1}$ shows.

######  Proposition 6.8.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ $(n\geq 3)$ be connected graphs and
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$.
If two factors of $\Gamma$ are isomorphic then $\operatorname{Aut}(\Gamma)$ is
non-discrete.

###### Proof.

We show that the stabiliser $\operatorname{Aut}(\Gamma)_{B(\emptyset,l)}$ of
the ball $B(\emptyset,l)$ of radius $l$ around $\emptyset\in V(\Gamma)$ is
non-trivial for every $l\in\operatorname{\mathbb{N}}$. Let
$\varphi:\Gamma_{i}\to\Gamma_{j}$ be an isomorphism for some distinct
$i,j\in\\{1,\ldots,n\\}$ and fix $k\in\\{1,\ldots,n\\}\backslash\\{i,j\\}$.
For every $\tilde{v}_{0}\in V(\Gamma)$ with $\lambda(\tilde{v}_{0})=k$ and
$\varphi(u_{i}(\tilde{v}_{0}))=u_{j}(\tilde{v}_{0})$, define an automorphism
$\smash{\beta^{(\tilde{v}_{0})}}\in\operatorname{Aut}(\Gamma)_{B(\emptyset,d(\emptyset,\tilde{v}_{0}))}$
as follows: Let $\tilde{v}=v_{1}\ldots v_{l}\in V(\Gamma)$. If $\tilde{v}_{0}$
is not a prefix of $\tilde{v}$, set
$\beta^{(\tilde{v}_{0})}(\tilde{v})=\tilde{v}$. When $\tilde{v}_{0}$ is a
prefix of $\tilde{v}$, we define $\beta^{(\tilde{v}_{0})}(\tilde{v})$ by
induction on $r\geq 0$ where $\tilde{v}=\tilde{v}_{0}v_{m+1}\ldots v_{m+r}$,
that is $l=l(\tilde{v})=l(\tilde{v}_{0})+r=m+r$. If $r=0$, put
$\smash{\beta^{(\tilde{v}_{0})}(\tilde{v})=\tilde{v}}$. Now consider vertices
of the form $\tilde{v}v_{m+(r+1)}$ where $l(\tilde{v})=m+r$. Set

$\beta^{(\tilde{v}_{0})}(\tilde{v}v_{m+(r+1)}):=\begin{cases}\beta^{(\tilde{v}_{0})}(\tilde{v})\varphi(v_{m+(r+1)})&\text{if
}v_{m+(r+1)}\in V(\Gamma_{i})\\\
\beta^{(\tilde{v}_{0})}(\tilde{v})\varphi^{-1}(v_{m+(r+1)})&\text{if
}v_{m+(r+1)}\in V(\Gamma_{j})\\\
\beta^{(\tilde{v}_{0})}(\tilde{v})v_{m+(r+1)}&\text{if }v_{m+(r+1)}\not\in
V(\Gamma_{i})\sqcup V(\Gamma_{j})\end{cases},$

Then $\smash{\beta^{(\tilde{v}_{0})}}$ is a bijection on vertices, preserves
both types of edges 5 and 6 and so does its inverse. Hence
$\smash{\beta^{(\tilde{v}_{0})}}$ is an automorphism. Since there are choices
for $\tilde{v}_{0}$ with $d(\emptyset,\tilde{v}_{0})$ arbitrarily large,
resulting in automorphisms $\beta^{(\tilde{v}_{0})}$ that stabilise
$B(\emptyset,d(\emptyset,\tilde{v}_{0}))$ pointwise, the assertion follows. ∎

As a consequence of Corollary 6.7 and Proposition 6.8, the Cayley graph

$\Gamma(\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}G_{i},\sqcup_{i=1}^{n}S_{i})\cong\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma(G_{i},S_{i})$

of a free product of finitely generated groups $(G_{i},S_{i})$
$(i\in\\{1,\ldots,n\\})$ has non-discrete automorphism group whenever
$\operatorname{Aut}(\Gamma(G_{i},S_{i}))\gneq G_{i}$ for some
$i\in\\{1,\ldots,n\\}$, or $n\geq 3$ and
$\Gamma(G_{i},S_{i})\cong\Gamma(G_{j},S_{j})$ for some distinct
$i,j\in\\{1,\ldots,n\\}$.

The question of how $\operatorname{Aut}(\Gamma(G,S))$ relates to its subgroup
$G$ is frequently studied, see e.g. [26], [7] and [17]. However, the focus
often lies on minimising the index $[\operatorname{Aut}(\Gamma(G,S)):G]$. In
the trivial case, the graph $\Gamma(G,S)$ is called a _graphical regular
representation_ of $G$. For example, in the case of finite groups there is a
complete classification of groups $G$ which admit a symmetric generating set
$S$ such that $\operatorname{Aut}(\Gamma(G,S))=G$, see [14] and [10]. From a
t.d.l.c. group perspective we are interested in non-discrete automorphism
groups of Cayley graphs and therefore ask the following.

######  Question 6.9.

Does every finitely generated group $G$, other than $C_{2}$, admit a finite
symmetric generating set $S$ such that $\operatorname{Aut}(\Gamma(G,S))\gneq
G$?

Note that if a generator in $S$ is repeated then
$\operatorname{Aut}(\Gamma(G,S))\gneq G$. Hence we suppose that the generators
in Question 6.9 are distinct.

In case of a positive answer to Question 6.9, we conclude that every free
product of finitely generated groups admits a locally finite Cayley graph with
non-discrete automorphism group: Free products other than $C_{2}\ast C_{2}$
are covered by the above discussion, whereas for $C_{2}\ast C_{2}\cong\langle
a,b\mid a^{2},b^{2}\rangle$ the Cayley graph with respect to the finite
symmetric generating set $\\{a,a^{-1},b,b^{-1},ab,(ab)^{-1},bab,(bab)^{-1}\\}$
has non-discrete automorphism group.

##  7\. Sheet-preserving automorphisms

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs and
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$.
We define two subgroups of $\operatorname{Aut}(\Gamma)$ that preserve the set
of sheets $\operatorname{\mathcal{S}}:=\\{S_{(v,i)}\mid v\in V(\Gamma),\
i\in\\{1,\ldots,n\\}\\}$. Recall that the colour $c(S)\in\\{1,\ldots,n\\}$ of
a sheet $S\in\operatorname{\mathcal{S}}$ is well-defined. We set

$\displaystyle\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$
$\displaystyle:=\\{\alpha\in\operatorname{Aut}(\Gamma)\mid\forall
S\in\operatorname{\mathcal{S}}:\ \alpha(S)\in\operatorname{\mathcal{S}}\\},$
$\displaystyle\operatorname{Aut}_{\operatorname{\mathcal{S}},c}(\Gamma)$
$\displaystyle:=\\{\alpha\in\operatorname{Aut}(\Gamma)\mid\forall
S\in\operatorname{\mathcal{S}}:\ \alpha(S)\in\operatorname{\mathcal{S}}\text{
and }c(\alpha(S))=c(S)\\}.$

Note that
$\operatorname{Aut}_{\operatorname{\mathcal{S}},c}(\Gamma)\leq\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)\leq\operatorname{Aut}(\Gamma)$.
If the factors of $\Gamma$ are $2$-connected then the set
$\operatorname{\mathcal{S}}$ coincides with the maximal $2$-connected
subgraphs of $\Gamma$, also known as “blocks”, or “lobes”, see e.g. [15] and
[11]. In this case,
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)=\operatorname{Aut}(\Gamma)$.
If, in addition, the factors of $\Gamma$ are pairwise non-isomorphic we
conclude that
$\operatorname{Aut}_{\operatorname{\mathcal{S}},c}(\Gamma)=\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)=\operatorname{Aut}(\Gamma)$.

######  Example 7.1.

The following examples illustrate the non-$2$-connected case.

  1. (i)

Let $\Gamma:=T_{1}\ast T_{1}$. Then $\Gamma\cong T_{2}$ and
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)=\operatorname{Aut}(\Gamma)=D_{\infty}$.
Furthermore,
$[\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma):\operatorname{Aut}_{\operatorname{\mathcal{S}},c}(\Gamma)]=[\operatorname{Aut}(\Gamma):\operatorname{Aut}_{\operatorname{\mathcal{S}},c}(\Gamma)]=2$.

  2. (ii)

Let
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{d}T_{1}\cong
T_{d}$. Then
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)=\operatorname{Aut}(\Gamma)$.
Following the notation of Burger–Mozes [3, Section 3.2] and Tornier [25,
Definition 3.1], we have
$\smash{\operatorname{Aut}_{\operatorname{\mathcal{S}},c}(\Gamma)=\mathrm{U}_{1}^{(c)}(\\{\operatorname{id}\\})}$,
which is discrete. In particular, we obtain
$[\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma):\operatorname{Aut}_{\operatorname{\mathcal{S}},c}(\Gamma)]=[\operatorname{Aut}(\Gamma):\operatorname{Aut}_{\operatorname{\mathcal{S}},c}(\Gamma)]=\infty$.

  3. (iii)

Let $\Gamma:=T_{1}\ast T_{2}\cong T_{3}$. In this case,
$\smash{\operatorname{Aut}_{\operatorname{\mathcal{S}},c}(\Gamma)=\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)=\mathrm{U}_{1}^{(l)}(\langle\tau\rangle)}$
where $\tau:=(12)\in S_{3}$ and $l$ is the legal labelling of $T_{3}$ arising
from the labellings $3$ and $\cdots$$\cdots$$1$$2$$1$ of the factors of
$\Gamma$. We deduce
$[\operatorname{Aut}(\Gamma)\\!:\\!\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)]\\!=\\!\infty$
as
$\smash{[\operatorname{Aut}(\Gamma)_{\emptyset}\\!:\\!\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)_{\emptyset}]\\!=\\![\mathrm{U}_{1}^{(l)}(S_{3})_{\emptyset}\\!:\\!\mathrm{U}_{1}^{(l)}(\langle\tau\rangle)_{\emptyset}]\\!=\\!\infty}$.

######  Example 7.2.

In [5, Example 3.7], Caprace and De Medts consider the free product
$\Gamma:=T_{2}\ast T_{2}$ of two lines and the group
$G:=\operatorname{Aut}_{\operatorname{\mathcal{S}},c}(\Gamma)$.

Every graph that is not $2$-connected has a cut vertex. Therefore, the
following proposition contrasts the case where all factors of $\Gamma$ are
$2$-connected.

######  Proposition 7.3.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs and
$\Gamma\\!:=\\!\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$.
If $\Gamma$ has two isomorphic factors which contain a cut vertex then
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)\lneq\operatorname{Aut}(\Gamma)$.
Conversely, if
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)\\!\lneq\\!\operatorname{Aut}(\Gamma)$
then some factor of $\Gamma$ contains a cut vertex.

###### Proof.

Let $\varphi:\Gamma_{i}\to\Gamma_{j}$ be an isomorphism for some distinct
$i,j\in\\{1,\ldots,n\\}$. Pick a cut vertex $u_{i}\\!\in\\!V(\Gamma_{i})$ and
a decomposition
$\smash{\Gamma_{i}\\!=\\!(\Gamma_{i}^{(1)},u_{i})\\#(\Gamma_{i}^{(2)},u_{i})}$
of $\Gamma_{i}$ associated to it. Let
$\smash{\Gamma_{j}=(\Gamma_{j}^{(1)},u_{j})\\#(\Gamma_{j}^{(2)},u_{j})}$ be
the image of the decomposition of $\Gamma_{i}$ under $\varphi$. Making
arbitrary choices of $u_{k}\in V(\Gamma_{k})$
($k\in\\{1,\ldots,n\\}\backslash\\{i,j\\}$), we may assume without loss of
generality that $\textbf{u}(\emptyset)=(u_{1},u_{2},u_{3},\ldots,u_{n})$.
Define an automorphism
$\hat{\varphi}\in\operatorname{Aut}(\Gamma)\backslash\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$
as follows. Let $\smash{B_{i}^{(1)},B_{j}^{(1)}\leq\Gamma}$ be the subgraphs
of $\Gamma$ spanned by the sets of vertices $\tilde{v}=v_{1}\ldots v_{l}$ with
$\smash{v_{1}\in\Gamma_{i}^{(1)}}$ and $\smash{v_{1}\in\Gamma_{j}^{(1)}}$
respectively, and note that these subgraphs are two components of
$\Gamma\setminus\\{\emptyset\\}$. Define

$\tilde{\varphi}:\bigsqcup_{k=1}^{n}V(\Gamma_{k})\to\bigsqcup_{k=1}^{n}V(\Gamma_{k}),\
v\mapsto\begin{cases}\varphi(v)&\text{if }v\in V(\Gamma_{i})\\\
\varphi^{-1}(v)&\text{if }v\in V(\Gamma_{j})\\\ v&\text{if }v\notin
V(\Gamma_{i})\sqcup V(\Gamma_{j})\end{cases}.$

Now define $\hat{\varphi}(\emptyset)=\emptyset$ and, for
$\tilde{v}=v_{1}\ldots v_{l}\in V(\Gamma)$,

$\hat{\varphi}(v_{1}\ldots
v_{l}):=\begin{cases}\tilde{\varphi}(v_{1})\ldots\tilde{\varphi}(v_{l})&\text{if
}\tilde{v}\in V(B_{i}^{(1)})\sqcup V(B_{j}^{(1)})\\\ v_{1}\ldots
v_{l}&\text{if }\tilde{v}\not\in V(B_{i}^{(1)})\sqcup
V(B_{j}^{(1)})\end{cases}.$

Then $\hat{\varphi}$ is the identity on all components of
$\Gamma\setminus\\{\emptyset\\}$ except $B_{i}^{(1)}$ and $B_{j}^{(1)}$ and
interchanges those components because it interchanges $i$ and $j$ in Equation
(2). It also preserves edges because $\varphi$ is an isomorphism. Hence,
$\hat{\varphi}\in\operatorname{Aut}(\Gamma)$ but not in
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$ as it does not map
the $\smash{\Gamma_{i}}$\- and $\smash{\Gamma_{j}}$-sheets at $\emptyset\in
V(\Gamma)$ to other sheets.

Now, assume
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)\lneq\operatorname{Aut}(\Gamma)$.
If no factor of $\Gamma$ contains a cut vertex, then all factos of $\Gamma$
are $2$-connected and hence
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)=\operatorname{Aut}(\Gamma)$,
as discussed above, in contradiction to the assumption. ∎

###  7.1. Structure Tree

To analyse $\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$ further,
we associate a _structure tree_ $T$ to $\Gamma$ which captures the fact that
the graph $\Gamma$ is tree-like. Define

$\displaystyle V(T):=V(\Gamma)\sqcup\operatorname{\mathcal{S}}\text{ and
}E(T):=\left\\{\\{v,S\\}\mid v\in V(\Gamma),\
S\in\operatorname{\mathcal{S}}\text{ and }v\in V(S)\right\\}.$

It is immediate from the definition that $T$ is a bipartite graph with parts
$V(\Gamma)$ and $\operatorname{\mathcal{S}}$. Then, since any two distinct
vertices in $V(\Gamma)$ can belong to at most one sheet, and any two distinct
sheets in $\operatorname{\mathcal{S}}$ intersect in at most one vertex, $T$ is
a tree. When all factors of $\Gamma$ are $2$-connected the tree $T$ is
precisely the block-cut tree of $\Gamma$, see [13, Section 4]. Note that $T$
is locally finite if and only if all factors of $\Gamma$ are finite. Also, the
actions of $\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$ on the
sets $V(\Gamma)$ and $\operatorname{\mathcal{S}}$ induce an injective
homomorphism
$\tau:\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)\to\operatorname{Aut}(T)$.

######  Remark 7.4.

The map
$\tau:\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)\to\operatorname{Aut}(T)$
is in fact a topological embedding: To check continuity, let $F\subseteq V(T)$
be a finite set and decompose $F=F_{V}\sqcup F_{\operatorname{\mathcal{S}}}$
into vertices $F_{V}$ coming from vertices of $\Gamma$, and vertices
$F_{\operatorname{\mathcal{S}}}$ coming from sheets of $\Gamma$. For every
$S\in F_{\operatorname{\mathcal{S}}}$, choose $e_{S}\in E(S)$. Then
$\tau^{-1}(\operatorname{Aut}(T)_{F})$ contains the open set
$\smash{\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)_{F_{V}\cup\\{e_{S}\mid
S\in F_{\operatorname{\mathcal{S}}}\\}}}$. To see that $\tau$ is open onto its
image, note that $V(\Gamma)\subseteq V(T)$ and therefore
$\tau(\operatorname{Aut}(\Gamma)_{F})=\operatorname{Aut}(T)_{F}\cap\operatorname{im}\tau$
for any finite set $F\subseteq V(\Gamma)$.

Using the standard metric $d^{\prime}$ on $V(T)$, define a metric $d$ on
$\operatorname{\mathcal{S}}\subseteq V(T)$ by $d:=\frac{1}{2}d^{\prime}$, as
well as the map
$\|\cdot\|:\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)\to\operatorname{\mathbb{N}}_{0},\
\alpha\mapsto\min\\{d(S,\alpha(S))\mid S\in\operatorname{\mathcal{S}}\\}$.

Let $\alpha\in\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$. If
$\|\alpha\|=0$ then $\alpha$ leaves a sheet invariant. For example, this
applies to the automorphisms of Propositions 6.1 and 6.6. The automorphisms in
the following proposition satisfy either $\|\alpha\|=0$ or $\|\alpha\|=1$.

######  Proposition 7.5.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs,
$\Gamma\\!:=\\!\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$
and $\varphi:\Gamma_{i}\to\Gamma_{j}$ an isomorphism for distinct
$i,j\in\\{1,\ldots,n\\}$. If $\tilde{v}_{0}\\!\in\\!V(\Gamma)$ satisfies
$\varphi(u_{i}(\tilde{v}_{0}))\\!=\\!u_{j}(\tilde{v}_{0})$ then there is
$\hat{\varphi}\in\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)_{\tilde{v}_{0}}$
with $\hat{\varphi}(S_{(\tilde{v}_{0},i)})=S_{(\tilde{v}_{0},j)}$ and
$\hat{\varphi}(S_{(\tilde{v}_{0},j)})=S_{(\tilde{v}_{0},i)}$.

###### Proof.

First, assume $\tilde{v}_{0}=\emptyset$ and set

$\tilde{\varphi}:\bigsqcup_{k=1}^{n}V(\Gamma_{k})\to\bigsqcup_{k=1}^{n}V(\Gamma_{k}),\
v\mapsto\begin{cases}\varphi(v)&\text{if }v\in V(\Gamma_{i})\\\
\varphi^{-1}(v)&\text{if }v\in V(\Gamma_{j})\\\ v&\text{if }v\notin
V(\Gamma_{i})\sqcup V(\Gamma_{j})\end{cases}.$

Now, set $\hat{\varphi}(\emptyset)=\emptyset$. For $\tilde{v}=v_{1}\ldots
v_{l}\in V(\Gamma)$, define

$\hat{\varphi}(v_{1}\ldots
v_{l}):=\begin{cases}\tilde{\varphi}(v_{1})\ldots\tilde{\varphi}(v_{l})&\text{if
}v_{1}\in V(\Gamma_{i})\cup V(\Gamma_{j})\\\ v_{1}\ldots
v_{l}&\text{otherwise}\end{cases}.$

Note that $\hat{\varphi}(S_{(\tilde{v}_{0},i)})=S_{(\tilde{v}_{0},j)}$ and
$\hat{\varphi}(S_{(\tilde{v}_{0},j)})=S_{(\tilde{v}_{0},i)}$ by definition,
that it maps sheets to sheets, and that it exchanges the roles of $i$ and $j$
in Equation (2). It also preserves edge relations, because $\varphi$ is an
automorphism, and $\hat{\varphi}(\emptyset)=\emptyset$. Hence $\hat{\varphi}$
belongs to
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)_{\tilde{v}_{0}}$.

If $\tilde{v}_{0}\neq\emptyset$, consider the free product
$\Gamma^{\prime}:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$
initialised with $\mathbf{u}^{\prime}(\emptyset)=\mathbf{u}(\tilde{v}_{0})$.
Let $\psi:\Gamma^{\prime}\to\Gamma$ be the isomorphism with
$\psi(\emptyset)=\tilde{v}_{0}$ provided by Corollary 4.7. Then
$\psi\circ\hat{\varphi}\circ\psi^{-1}$, where $\hat{\varphi}$ is applied to
$\Gamma^{\prime}$ serves. ∎

The following classification of sheet-preserving automorphisms of $\Gamma$ is
analogous to [24, Proposition 3.2]. A _bi-infinite line of sheets_ in $\Gamma$
is a map $\gamma:\operatorname{\mathbb{Z}}\to\operatorname{\mathcal{S}}$ such
that $d(\gamma(n),\gamma(m))=|n-m|$ for all $n,m\in\operatorname{\mathbb{Z}}$.
An automorphism
$\alpha\in\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$ acts as a
_translation of length $l$_ along $\gamma$ if $\alpha(\gamma(n))=\gamma(n+l)$
for all $n\in\operatorname{\mathbb{Z}}$.

######  Theorem 7.6.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected graphs,
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$
and $\alpha\in\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$. Then
$\alpha$ satisfies exactly one of the following conditions. Either, it

  1. ($\|\alpha\|=0$)

leaves a sheet invariant, or

  2. ($\|\alpha\|=1$)

fixes a vertex without leaving a sheet invariant, or

  3. ($\|\alpha\|\geq 1$)

is a translation of length $\|\alpha\|$ along a unique bi-infinite line of
sheets.

Furthermore, if $\|\alpha\|\leq 1$ then $\alpha=\sigma\circ\beta$ for some
automorphisms
$\sigma,\beta\in\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$ that
leave a sheet invariant and stabilise a vertex respectively.

###### Proof.

Consider the automorphism $\tau(\alpha)\in\operatorname{Aut}(T)$ induced by
$\alpha\in\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$. By [24,
Proposition 3.2], the automorphism $\tau(\alpha)$ either fixes a vertex,
inverts an edge or acts as a translation along a unique bi-infinite line in
$T$. If $\tau(\alpha)$ fixes a vertex in $\operatorname{\mathcal{S}}\subseteq
V(T)$ then $\alpha$ is of the first type. If $\tau(\alpha)$ fixes a vertex in
$V(\Gamma)\subseteq V(T)$, but no vertex in
$\operatorname{\mathcal{S}}\subseteq V(T)$, then $\alpha$ is of the second
type. The case where $\tau(\alpha)$ is an inversion does not occur because
$\alpha$ preserves the bipartition
$V(T)=V(\Gamma)\sqcup\operatorname{\mathcal{S}}$. The final option is that
$\tau(\alpha)$ acts as a translation of length $l$ along a unique bi-infinite
line $\gamma^{\prime}:\operatorname{\mathbb{Z}}\to V(T)$ in $T$. Without loss
of generality, $\gamma^{\prime}(0)\in\operatorname{\mathcal{S}}\subseteq
V(T)$. Then $\alpha$ is a translation of length $l/2$ along
$\gamma:\operatorname{\mathbb{Z}}\to\operatorname{\mathcal{S}}$, where
$\gamma(t)=\gamma^{\prime}(2t)$, and $\|\alpha\|=l/2$.

Now consider the case $\|\alpha\|\leq 1$. If $\|\alpha\|=0$ or $\alpha$ fixes
a vertex then $\alpha$ decomposes trivially. We may therefore assume that
$\alpha$ is a translation of length $1$ along a bi-infinite line
$\gamma:\operatorname{\mathbb{Z}}\to\operatorname{\mathcal{S}}$ of sheets. Let
$i_{k}:=c(\gamma(k))\in\\{1,\ldots,n\\}$ for all
$k\in\operatorname{\mathbb{Z}}$. Since $\\{1,\ldots,n\\}$ is finite there are
$k,l\in\operatorname{\mathbb{Z}}$ with $k<l$ and $i_{k}=i_{l}$. Moreover, we
may choose $l\in\operatorname{\mathbb{Z}}_{>k}$ minimal with this property.
Put $S:=\gamma(k)$. Note that the fact that $d(\gamma(k),\gamma(k+1))=1$
implies that $\gamma(k)\cap\gamma(k+1)=\\{v\\}$ for some $v\in V(\Gamma)$ and
that $\gamma(k)$ and $\gamma(k+1)$ belong to sheets of different colours, so
that $l\in\operatorname{\mathbb{Z}}_{>k+1}$. Let
$\mathbf{u}(v)=(v_{1},\ldots,v_{n})$. Then
$u_{i_{k}}(\alpha^{l-k-1}(v))=u_{i_{k}}(v)=v_{i_{k}}$ as no minimal path from
$v$ to $\alpha^{l-k-1}(v)$ passes through a sheet of type $i_{k}$. Hence the
isomorphism
$\smash{\varphi_{(v,i_{k+1})}^{-1}\circ\alpha^{-(l-k-1)}\circ\varphi_{(\alpha^{(l-k-1)}(v),i_{k})}:\Gamma_{i_{k}}\to\Gamma_{i_{k+1}}}$,
where the maps $\varphi$ are the embeddings introduced in Example 4.3i, maps
$v_{i_{k}}$ to $v_{i_{k+1}}$. Proposition 7.5 now provides an automorphism
$\beta\in\text{Aut}(\Gamma)$ which fixes $v\in V(\Gamma)$ and swaps
$\gamma(k)$ and $\gamma(k+1)$. Then $\sigma:=\alpha\circ\beta$ is an
automorphism of the free product graph that preserves the sheet $\alpha(S)$
and $\alpha=(\alpha\circ\beta)\circ\beta^{-1}$ as required. ∎

######  Example 7.7.

Let $\Gamma:=T_{1}\ast T_{1}\ast T_{1}$. Then $\Gamma\cong T_{3}$,
$\operatorname{\mathcal{S}}=E(T_{3})$, and
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)=\operatorname{Aut}(\Gamma)$.
Let $\alpha\in\operatorname{Aut}(T_{3})$. If $\alpha$ is elliptic then either
$\alpha$ fixes an edge, in which case $\|\alpha\|=0$, or it does not fix any
edge, in which case $\|\alpha\|=1$. If $\alpha$ is an inversion, then $\alpha$
leaves an edge and hence a sheet invariant and $\|\alpha\|=0$. (Note that
inversions of $\Gamma$ are not inversions of $T$.) Finally, if $\alpha$ is
hyperbolic of length $l$ then $\|\alpha\|=l$.

###  7.2. Simplicity

Here, we apply Tits’ simplicity criterion for groups acting on trees to
subgroups of $\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$ via the
injective homomorphism
$\tau:\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)\to\operatorname{Aut}(T)$.

First, we briefly recall this criterion. See e.g. ([8, Section 6.3]) for more
detail. Let $C$ denote a finite or (bi)infinite path in $T$. For every $x\in
V(C)$, the pointwise stabilizer $H_{C}$ induces an action
$\smash{H_{C}^{(x)}\leq\operatorname{Aut}(\pi^{-1}(x))}$ on the subtree
spanned by those vertices of $T$ whose closest vertex in $C$ is $x$; here,
$\pi:V(T)\to V(C)$ denotes the closest point projection. We therefore obtain
an injective homomorphism

$\varphi_{C}:H_{C}\to\prod\nolimits_{x\in V(C)}H_{C}^{(x)}.$

A subgroup $H\leq\operatorname{Aut}(T)$ satisfies _Property $P$_ if
$\varphi_{C}$ is an isomorphism for every path $C$ in $T$. Also recall that
Tits defines the subgroup $G^{+}$ of $G$ to be that generated by the pointwise
stabilisers of the edges of the tree $T$.

######  Theorem ([24, 4.5 Théorème]).

Let $G\leq\operatorname{Aut}(T)$. Suppose $G$ neither fixes an end nor
preserves a proper subtree of $T$ setwise, and that $G$ satisfies Property
$P$. Then the group $G^{+}$ is either trivial or simple.

Now, let $H\leq\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$. Given
a sheet $S\in\operatorname{\mathcal{S}}$ and $v\in V(S)$, we define the
subgroup $H_{(S,v)}:=\\{h\in H\mid h(v)=v\text{ and }h(S)=S\\}$ and put

$H^{+_{\operatorname{\mathcal{S}}}}:=\langle\\{H_{(S,v)}\mid
S\in\operatorname{\mathcal{S}},\ v\in
V(S)\\}\rangle(=\tau^{-1}(\tau(H)^{+})).$

If $\tau(H)\leq\operatorname{Aut}(T)$ preserves no proper subtree, fixes no
end of $T$, and satisfies Property (P) then $\tau(H)^{+}$ is either trivial or
simple by [24, 4.5 Théorème], and hence so is
$H^{+_{\operatorname{\mathcal{S}}}}\cong\tau(H)^{+}$.

######  Proposition 7.8.

Let $\Gamma_{1},\ldots,\Gamma_{n}$ be connected, vertex-transitive graphs and
let
$\Gamma:=\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{n}\Gamma_{i}$.
Then
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)^{+_{\operatorname{\mathcal{S}}}}$
is either trivial or simple.

###### Proof.

Let $G:=\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$. We first
show that $\tau(G)\leq\operatorname{Aut}(T)$ is geometrically dense: Since the
automorphisms of Corollary 6.4 preserve the set of sheets
$\operatorname{\mathcal{S}}$, the group $\tau(G)$ acts transitively on
$V(\Gamma)\subseteq V(T)$. Hence it preserves no proper subtree of $T$.
Proposition 6.1 and vertex-transitivity of the factors $\Gamma_{i}$ imply that
the stabiliser, $\tau(G)_{S}$, of a sheet
$S\in\operatorname{\mathcal{S}}\subseteq V(T)$ acts transitively on
$N_{T}(S)=V(S)\subseteq V(\Gamma)\subseteq V(T)$. In particular, none of the
sheets neighbouring $S$ are fixed by $\tau(G)_{S}$. If $\tau(G)$ fixed an end
of $T$, then $\tau(G)_{S}$ would have to fix every vertex on a ray beginning
at $S$, which would contradict that. Therefore, $\tau(G)$ fixes no end of $T$.

To see that $\tau(G)$ has Property (P), let $C$ be a finite or (bi)infinite
path in $T$. Further, let $\pi:V(T)\to V(C)$ be the closest point projection.
Given $\alpha\in G$ such that $\tau(\alpha)\in\tau(G)_{C}$ and $x\in V(C)$,
consider the restriction $\tau(\alpha)_{x}$ of $\tau(\alpha)$ to
$\pi^{-1}(x)$. Define
$\alpha_{x}\in\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)$ by
setting $\alpha_{x}(v):=\alpha(v)$ if either $v\in V(\pi^{-1}(C))$ or $v\in
V(S)$ for some $S\in V(\pi^{-1}(C))$, and $\alpha_{x}(v):=v$ otherwise. Then
$\tau(\alpha_{x})\in\tau(G)_{C}$, and we have
$\tau(\alpha_{x})_{x}=\tau(\alpha)_{x}$ as well as
$\tau(\alpha_{x})\in\mathrm{rist}(\pi^{-1}(C))$, the rigid stabiliser of
$\pi^{-1}(C)$ introduced in Section 2, as required. ∎

######  Example 7.9.

  1. (i)

Let
$\Gamma\\!:=\\!\operatorname{\scalebox{1.7}{\raisebox{-1.29167pt}{$\ast$}}}_{i=1}^{d}T_{1}\\!\cong\\!T_{d}$
be as in Example 7.1ii. Then
$\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)^{+_{\operatorname{\mathcal{S}}}}\\!=\\!\operatorname{Aut}(T_{d})^{+}$.

  2. (ii)

Let $\Gamma:=T_{1}\ast T_{2}$ be as in Example 7.1iii. Then
$\smash{\operatorname{Aut}_{\operatorname{\mathcal{S}}}(\Gamma)^{+_{\operatorname{\mathcal{S}}}}=\mathrm{U}_{1}(\langle\tau\rangle)^{+}}$.

### Acknowledgements

We gratefully acknowledge research support by an AMSI Vacation Research
Scholarship and the ARC Laureate Fellowship FL170100032. We owe thanks to
Brian Alspach, Ben Brawn and Colin Reid for helpful discussions, and Ben Brawn
for numerous improvements. Finally, the helpful comments of two anonymous
reviewers were much appreciated.

## References

  * [1] C. Banks, M. Elder, and G. A. Willis.  Simple groups of automorphisms of trees determined by their actions on finite subtrees.  J. Group Theory, 18(2) (2015), 235–261.
  * [2] U. Baumgartner and G. A. Willis.  Contraction groups and scales of automorphisms of totally disconnected locally compact groups.  Israel J. Math., 142(1) (2004), 221–248.
  * [3] M. Burger and S. Mozes.  Groups acting on trees: from local to global structure.  Publ. Math. Inst. Hautes Études Sci., 92 (2000), 113–150.
  * [4] T. P. Bywaters and S. Tornier.  Willis Theory via Graphs.  Groups, Geom. Dyn., (2019).
  * [5] P.-E. Caprace and T. De Medts.  Simple locally compact groups acting on trees and their germs of automorphisms.  Transform. Groups, 16(2) (2011), 375.
  * [6] R. Charney.  An introduction to right-angled artin groups.  Geom. Dedicata, 125(1) (2007), 141–158.
  * [7] E. Dobson, P. Spiga, and G. Verret.  Cayley graphs on abelian groups.  Combinatorica, 36(4) (2016), 371–393.
  * [8] A. Garrido, Y. Glasner, and S. Tornier.  Automorphism Groups of Trees: Generalities and Prescribed Local Actions.  In P.-E. Caprace and M. Monod, editors, New Directions in Locally Compact Groups, Cambridge University Press, (2018), 92–116.
  * [9] A. Gleason.  Groups without small subgroups.  Annals of Math., (1952), 193–212.
  * [10] C.D. Godsil.  GRR’s for Non-solvable Groups.  Mathematics research report. University of Melbourne, (1978).
  * [11] J. Graver and M. Watkins.  Lobe, edge, and arc transitivity of graphs of connectivity.  Ars Math. Contemp., 17(2) (2019), 581–589.
  * [12] R. Hammack, W. Imrich, and S. Klavžar.  Handbook of graph products.  Discrete Math. Appl., (2011).
  * [13] F. Harary.  Graph theory.  Addison-Wesley, (1969).
  * [14] W. Imrich and M.E. Watkins.  On automorphism groups of cayley graphs.  Period. Math. Hungar., 7(3-4) (1976), 243–258.
  * [15] H. Jung and M. Watkins.  On the structure of infinite vertex-transitive graphs.  Discrete Math., 18(1) (1977), 45–53.
  * [16] B. Krön and R. Möller.  Analogues of cayley graphs for topological groups.  Math. Z., 258(3) (2008), 637.
  * [17] P.-H. Leemann and M. de la Salle.  Cayley graphs with few automorphisms.  J. Algebraic Combin., (2020), 1–30.
  * [18] B. Mohar.  Tree amalgamation of graphs and tessellations of the cantor sphere.  J. Combin. Theory Ser. B, 96(5) (2006), 740–753.
  * [19] R. Möller.  Structure theory of totally disconnected locally compact groups via graphs and permutations.  Canad. J. Math., 54(4) (2002), 795–827.
  * [20] R. Möller, N. Seifter, W. Woess, and S. Zemljic.  Amalagamated free products of graphs and arc-types.  Unpublished, (2018).
  * [21] D. Montgomery and L. Zippin.  Small subgroups of finite-dimensional groups.  Proc. Natl. Acad. Sci. USA, 38(5) (1952), 440–442.
  * [22] T. Pisanski and T. Tucker.  Growth in products of graphs.  Australas. J. Combin., 26 (2002), 155–170.
  * [23] G. Quenell.  Combinatorics of free product graphs.  Contemp. Math., 173 (1994), 257–257.
  * [24] J. Tits.  Sur le groupe des automorphismes d’un arbre.  In Essays on topology and related topics, Springer, (1970), 188–211.
  * [25] S. Tornier.  Groups acting on trees with prescribed local action.  arxiv preprint 2002.09876, (2020).
  * [26] M.E. Watkins.  Graphical regular representations of free products of groups.  J. Combin. Theory Ser. B, 21(1) (1976), 47–56.
  * [27] G. A. Willis.  The structure of totally disconnected locally compact groups.  Math. Ann., 300(1) (1994), 341–363.
  * [28] H. Yamabe.  A generalization of a theorem of Gleason.  Annals of Math., (1953), 351–365.