text:
# Some Intrinsic Properties of Simple Graph 𝐶^∗-algebras

## 1. Introduction

This paper brings together ideas from the theory of nonnegative matrices associated to strongly connected graphs and topological graph theory to prove some structure results for graph $`C^{}`$-algebras. Because of the diverse backgrounds involved, we have made an effort to make this paper self-contained by including a little relevant background from each of these areas.

We begin by establishing our notation and conventions for directed graphs and their $`C^{}`$-algebras (we are aware that graph theorists use quite different terminology (see \[ChO\] for example)). Next we bring together two sets of results on the simplicity of graph $`C^{}`$-algebras due to Paterson \[Pt\] and Szymański \[Sz\]. We show that up to Morita equivalence, a simple graph $`C^{}`$-algebra is either AF or the $`C^{}`$-algebra of a strongly connected graph.

We then give some results about the finite path space of a strongly connected graph. These results are essentially restatements of standard facts about irreducible nonnegative matrices. In the following section we describe the construction of a relative skew product graph from $`E`$ (cf. \[GT, GT1\]). Essentially, if $`\mathrm{\Gamma }`$ is a group with subgroup $`H`$, a relative skew product graph $`E\times _c(H\backslash \mathrm{\Gamma })`$ is an extension of $`E`$ by the homogeneous space $`H\backslash \mathrm{\Gamma }`$ using a labelling of the edges in $`E`$ by elements of $`\mathrm{\Gamma }`$. This construction generalises the usual skew product graph used in \[KP, KaQR\]. In Theorem 5.2 we show that any connected covering graph of a given connected graph can be written as a relative skew product graph of the base graph, a generalisation of the results in \[GT, GT1\]. We describe an invariant, called the local voltage group, which enables us to write the connected components of an ordinary skew product graph as skew product graphs in their own right. For a row-finite graph $`E`$ there is a canonical labelling of the edges in $`E`$ with the integer $`1`$ such that $`C^{}(E\times _c𝐙)`$ is isomorphic to $`C^{}(E)\times _\gamma 𝐓`$ where $`\gamma `$ denotes the gauge action of $`𝐓`$ on $`C^{}(E)`$.

In the final section we apply our results to graph $`C^{}`$-algebras. In various stages we prove that the fixed point algebra $`C^{}(E)^\gamma `$ of the gauge action $`\gamma `$ on $`C^{}(E)`$ is simple if and only if either $`E`$ consists of a single vertex or $`E`$ is row-finite and has a cofinal subgraph with finitely many vertices which is strongly connected with period one. If $`E`$ is strongly connected with period $`d`$ then $`C^{}(E)^\gamma `$ is the direct sum of $`d`$ mutually isomorphic AF algebras. If, in addition $`E^0`$ is finite then $`C^{}(E)`$ is stably isomorphic to a crossed product of a simple AF algebra by a $`𝐙`$-action.

The authors would like to thank the referee for several helpful comments which led to improvements in the final draft.

## 2. Graphs and their $`C^{}`$-algebras

A directed graph $`E`$ consists of a sets $`E^0,E^1`$ of vertices and edges respectively, together with maps $`r,s:E^1E^0`$ giving the direction of each edge. A subgraph $`F`$ of $`E`$ consists of subsets $`F^iE^i`$ for $`i=0,1`$ such that $`s(F^1)F^0`$ and $`r(F^1)F^0`$. A path in the directed graph $`E`$ is a finite sequence $`\alpha =\alpha _1\mathrm{}\alpha _n`$ of edges such that $`r(\alpha _i)=s(\alpha _{i+1})`$ for $`1in1`$. For a finite path $`\alpha =\alpha _1\mathrm{}\alpha _n`$, its length $`|\alpha |:=n`$ is the number of edges in the sequence $`\alpha `$. An infinite path in $`E`$ is an infinite sequence $`(x_i)_{i1}`$ of edges such that $`r(x_i)=s(x_{i+1})`$ for $`i1`$; the set of infinite paths in $`E`$ is denoted $`E^{\mathrm{}}`$. For $`n0`$, let $`E^n`$ denote all those paths in the directed graph $`E`$ of length $`n`$. Let $`E^{}=_{n0}E^n`$ denote the set of all finite paths in $`E`$. The range and source maps extend naturally to $`E^{}`$; for $`\alpha =\alpha _1\mathrm{}\alpha _nE^{}`$ define $`r(\alpha )=r(\alpha _n)`$ and $`s(\alpha )=s(\alpha _1)`$. The graph $`E`$ is called row-finite if every vertex emits finitely many edges. A vertex which does not emit any edges is called a sink. A vertex which does not receive any edges is called a source.

Let $`E`$ be a directed graph, for $`eE^1`$ we formally denote by $`e^1`$, the edge $`e`$ traversed backwards, so that $`s(e^1)=r(e)`$ and $`r(e^1)=s(e)`$. The set of reverse edges is denoted $`E^1`$; it is then natural to define $`(e^1)^1=e`$ for $`e^1E^1`$. A walk in the directed graph $`E`$ is a sequence $`a=a_1\mathrm{}a_n`$, where $`a_iE^1E^1`$ are such that $`r(a_i)=s(a_{i+1})`$ for $`i=1,\mathrm{},n1`$; we write $`s(a)=s(a_1)`$ and $`r(a)=r(a_n)`$. A walk $`a=a_1\mathrm{}a_n`$ is said to be reduced if it does not contain the subword $`a_ia_{i+1}=aa^1`$ for any $`aE^1E^1`$. Given a reduced walk $`a=a_1\mathrm{}a_n`$ the reverse walk is written $`a^1:=a_n^1\mathrm{}a_1^1`$, which is also reduced. If $`a,b`$ are reduced walks with $`r(a)=s(b)`$, then $`ab`$ will be understood to be the reduced walk obtained by concatenation and then cancellation using the relations $`ee^1=s(e)`$, $`e^1e=r(e)`$, $`e^1s(e)=e^1=r(e)e^1`$ and $`er(e)=e=s(e)e`$ for $`eE^1`$. With composition and inverse operations defined above, the set $`\pi _1(E)`$ of reduced walks, forms a groupoid with unit space $`E^0`$ and is referred to as the fundamental groupoid of $`E`$ (note that the roles of the range and source map must be reversed to make $`\pi _1(E)`$ a category, cf. \[KP2\]).

Let $`E`$, $`F`$ be directed graphs. A graph morphism $`\varphi :FE`$ consists of maps $`\varphi ^i:F^iE^i`$ for $`i=0,1`$ such that $`\varphi ^0(r(f))=r(\varphi ^1(f))`$ and $`\varphi ^0(s(f))=s(\varphi ^1(f))`$ for all $`fE^1`$.

###### Definition 2.1.

Let $`E`$, $`F`$ be directed graphs and $`p:FE`$ be a graph morphism; then $`p`$ is covering map if for each $`vF^0`$, $`p`$ maps $`r^1(v)`$ bijectively onto $`r^1(p(v))`$ and $`s^1(v)`$ bijectively onto $`s^1(p(v))`$ (cf. \[St, §2.1.6\]).

Let $`p:FE`$ be a covering map, for $`a=a_1\mathrm{}a_n\pi _1(F)`$ let $`p(a)=p(a_1)\mathrm{}p(a_n)`$ where $`p(f^1):=p(f)^1`$ for $`fE^1`$. In this way, the covering map $`p`$ induces a morphism $`p_{}:\pi _1(F)\pi _1(E)`$. A graph morphism $`p:FE`$ has the unique walk lifting property (see \[GT, Theorem 2.1.1\]) if given $`uF^0`$ and $`a\pi _1(E)`$ with $`s(a)=p^0(u)`$, there is a unique $`\stackrel{~}{a}\pi _1(F)`$ such that $`s(\stackrel{~}{a})=u`$ and $`p(\stackrel{~}{a})=a`$; one may also lift reduced walks which end at $`p^0(u)`$. Likewise one may lift infinite paths from $`E`$ to $`F`$. The following result is routine (see \[Ko, Lemma 17.4\] for instance):

###### Lemma 2.2.

Let $`E`$, $`F`$ be directed graphs and $`p:FE`$ be a graph morphism. Then $`p`$ has the unique walk lifting property if and only if $`p`$ is a covering map.

The directed graph $`E`$ is said to be connected if, given any two distinct vertices in $`E`$, there is a reduced walk between them. A directed graph $`T`$ is a tree if and only if there is precisely one reduced walk between any two vertices (so a tree is connected). For a connected graph $`E`$ and $`vE^0`$ we may define

$$\pi _1(E,v)=\{a\pi _1(E):s(a)=v=r(a)\}$$

so that $`\pi _1(E,v)`$ is the isotropy group of the unit $`v`$ in $`\pi _1(E)`$. If $`E`$ is connected, then the groupoid $`\pi _1(E)`$ is connected and so all its isotropy groups are isomorphic. Our definition of the fundamental group matches the usual one given in \[St, §2.1.6\] because taking the reduction of a walk coincides with the notion of path equivalence used there.

Using the axiom of choice it may be shown that every connected graph $`E`$ contains a spanning tree $`T`$ (cf. \[St, §2.1.5\]): a subgraph $`T`$ which is itself a tree with $`T^0=E^0`$. Fix a given spanning tree $`T`$ of $`E`$ and a vertex $`vE^0`$, then for $`wT^0`$ we set $`b_w`$ to be the unique reduced walk in $`T`$ from $`v`$ to $`w`$. If $`E`$ has a spanning tree then it is connected.

Let $`E`$ be a directed graph, then a Cuntz-Krieger $`E`$-family (or a representation of $`E`$) consists of a family $`\{P_v:vE^0\}`$ of mutually orthogonal projections and a family $`\{S_e:eE^1\}`$ of partial isometries with mutually orthogonal ranges such that

$$S_e^{}S_e=P_{r(e)},S_eS_e^{}P_{s(e)},P_v=\underset{s(e)=v}{}S_eS_e^{}\text{ if }0<|s^1(v)|<\mathrm{}.$$

The graph $`C^{}`$-algebra $`C^{}(E)`$ is generated by a universal Cuntz-Krieger $`E`$-family $`\{s_e,p_v\}`$ (see \[RSz, §1\]). The class of graph $`C^{}`$-algebras is quite broad, it includes, up to Morita equivalence, all AF algebras and all Cuntz-Krieger algebras (see \[KPR\], \[KPRR\] amongst others).

## 3. Simple graph algebras

A loop in $`E`$ is a path $`\alpha `$ with $`|\alpha |1`$ such that $`s(\alpha )=r(\alpha )`$. The loop $`\alpha E^n`$ is simple if the vertices $`\{r(\alpha _i):1in\}`$ are distinct. The graph $`E`$ satisfies condition (K) if no vertex lies on exactly one simple loop. The directed graph $`E`$ is cofinal if, given $`xE^{\mathrm{}}`$ and $`vE^0`$ there is a path $`\alpha `$ such that $`s(\alpha )=v`$ and $`r(\alpha )=r(x_n)`$ for some $`n1`$.

If $`v,wE^0`$ then we write $`vw`$ if there is a path from $`v`$ to $`w`$. A subset $`H`$ of $`E^0`$ is hereditary if $`vH`$ and $`vw`$ implies that $`wH`$. A hereditary subset $`H`$ is saturated if there is no vertex $`vE^0\backslash H`$ with $`0<|s^1(v)|<\mathrm{}`$ such that $`r(e)H`$ for all $`es^1(v)`$. For $`XE^0`$ define $`L_X`$ to be the hereditary subset consisting of all vertices which $`X`$ connects to; then $`\mathrm{\Sigma }(X)`$, the smallest saturated hereditary subset containing $`X`$ consists of all those vertices of $`vE^0`$ with $`0<|s^1(v)|<\mathrm{}`$ such that every infinite path starting at $`v`$ eventually uses vertices in $`L_X`$. Recall from \[BHRSz\] that a nontrivial saturated hereditary subset $`H`$ of $`E`$ gives rise to a nontrivial gauge invariant ideal $`I_H`$ of $`C^{}(E)`$.

###### Theorem 3.1.

Let $`E`$ be a directed graph then $`C^{}(E)`$ is simple if and only if

* $`E`$ is cofinal,
* $`E`$ satisfies condition (K),
* If vertex $`v`$ emits infinitely many edges then every vertex connects to $`v`$.

###### Proof.

See \[Pt, Theorem 4\] or \[Sz, Theorem 12\]. In \[Pt, Theorem 4\] the proof of the only if direction is omitted, but as we see below it is not hard.

Suppose that $`E`$ is not cofinal, then there are $`xE^{\mathrm{}}`$ and $`vE^0`$ such that $`v`$ does not connect to any vertex used by $`x`$. Hence $`s(x)\mathrm{\Sigma }(L_{\{v\}})`$ because the infinite path $`x`$ does not enter $`L_{\{v\}}`$. Therefore $`\mathrm{\Sigma }(L_{\{v\}})`$ gives rise to a nontrivial gauge invariant ideal $`I_{\mathrm{\Sigma }(L_{\{v\}})}`$ of $`C^{}(E)`$ in which case $`C^{}(E)`$ is not simple.

Suppose that $`E`$ does not satisfy condition (K), then there is a simple loop $`L`$ in $`E`$ such that each vertex of $`L`$ lies on no other loop. Either $`E`$ is cofinal or it is not. If $`E`$ is not cofinal then $`C^{}(E)`$ is not simple by the argument above. If $`E`$ is cofinal then by \[KPR, Theorem 2.4\] $`C^{}(E)`$ is strongly Morita equivalent to $`C(𝐓)`$ which is not simple.

If $`E`$ has a vertex $`v`$ of infinite valency and a vertex $`w`$ which does not connect to $`v`$, then $`vL_{\{w\}}`$; moreover $`v\mathrm{\Sigma }(L_{\{w\}})`$, since $`v`$ has infinite valency. Hence $`\mathrm{\Sigma }(L_{\{w\}})`$ is a nontrivial saturated hereditary subset of $`E^0`$ and so gives rise to a nontrivial gauge invariant ideal $`I_{\mathrm{\Sigma }(L_{\{w\}})}`$ of $`C^{}(E)`$. Hence $`C^{}(E)`$ is not simple, which concludes the proof. ∎

The directed graph $`E`$ is strongly connected if for every pair of vertices $`v,w`$ there is a path $`\alpha `$ with $`|\alpha |1`$ such that $`s(\alpha )=v`$, $`r(\alpha )=w`$. A strongly connected graph is sometimes said to be transitive or irreducible (since its vertex incidence matrix $`A_E`$ is irreducible (cf. \[S, §1.3\])). If $`E`$ is strongly connected, then it is cofinal. A subgraph $`F`$ of $`E`$ is said to be cofinal if for every $`xE^{\mathrm{}}`$ there exists $`N(x)`$ such that $`r(x_n)F^0`$ for $`nN(x)`$.

###### Theorem 3.2.

If the directed graph $`E`$ is cofinal then either $`E`$ has no loops, or there exists a strongly connected cofinal subgraph $`FE`$.

###### Proof.

Under the relation of mutual connectivity (i.e. $`vw`$ if and only if $`vw`$ and conversely), there exists an equivalence class $`X`$ of vertices which contains any vertex which lies on a loop. If $`E`$ has a loop and is cofinal there can only be one such equivalence class. Let $`F`$ be the subgraph with $`F^0=X`$ and $`F^1=\{e:s(e)F^0\}`$. We claim that $`r(F^1)F^0`$. Suppose that $`eF^1`$ is such that $`r(e)F^0`$. Since $`s(e)F^0`$, the vertex $`s(e)`$ connects to itself via $`\alpha `$. Let $`y=\alpha \alpha \alpha \mathrm{}E^{\mathrm{}}`$ then since $`E`$ is cofinal $`r(e)`$ must connect to some vertex on $`\alpha `$ and hence to $`s(e)`$. But this contradicts our assumption that $`r(e)F^0`$. By its definition, $`F`$ is strongly connected, it remains to show that $`FE`$ is cofinal.

Let $`xE^{\mathrm{}}`$ then if $`s(x)F^0`$ then we may take $`N(x)=1`$. So we suppose that $`s(x)F^0`$. Let $`vF^0`$, then there is a loop $`\alpha `$ with $`s(\alpha )=v`$ which yields $`y=\alpha \alpha \mathrm{}E^{\mathrm{}}`$. Since $`E`$ is cofinal there exists $`\beta E^{}`$ such that $`s(\beta )=v`$ and $`r(\beta )=r(x_m)`$ some $`m1`$. Let $`w=r(x_{m+1})`$ then by cofinality there must be a path $`\gamma E^{}`$ with $`s(\gamma )=w`$ and $`r(\gamma )=r(y_{\mathrm{}|\alpha |})=v`$ for some $`\mathrm{}1`$. Then $`v`$ connects to $`w`$ via $`\beta x_{m+1}`$ and $`w`$ connects to $`v`$ via $`\gamma `$, and so $`wF^0`$ by definition. ∎

###### Corollary 3.3.

Suppose that $`C^{}(E)`$ is simple then either $`C^{}(E)`$ is an AF-algebra or there exists a strongly connected subgraph $`FE`$ such that $`C^{}(E)`$ is strongly Morita equivalent to $`C^{}(F)`$.

###### Proof.

If $`C^{}(E)`$ is simple, then by Theorem 3.1 the graph $`E`$ is cofinal. If $`E`$ has no loops then by Theorem 3.1 $`E`$ cannot have any vertices of infinite valency and then $`C^{}(E)`$ is an AF-algebra by \[KPR, Theorem 2.4\]. On the other hand if $`E`$ has loops, then by Theorem 3.2 there exists a strongly connected cofinal subgraph $`F`$ of $`E`$. Let $`P=_{vF^0}p_v`$, then by a similar argument to the one given in \[BPRSz, §1\] $`P`$ defines a projection in the multiplier algebra of $`C^{}(E)`$ such that $`PC^{}(E)PC^{}(F)`$. To see that $`PC^{}(E)P`$ is full, just observe that $`P0`$ and that $`C^{}(E)`$ is simple. Hence $`C^{}(E)`$ is strongly Morita equivalent to $`C^{}(F)`$ as required. ∎

## 4. Strongly connected graphs

In this section we briefly give some results about the path space of a strongly connected graph. Essentially, they are reformulations of results about finite, nonnegative matrices. For more details about nonnegative matrices see \[S, §1.3\] or \[LM, §4\]. Let $`E`$ be a directed graph, then for $`vE^0`$ we define its period $`d(v)`$, to be the greatest common divisor of the lengths of all loops which begin at $`v`$. If there are no such loops then we set $`d(v)=0`$.

###### Lemma 4.1.

If $`E`$ is strongly connected then for any $`v,wE^0`$ we have $`d(v)=d(w)`$.

###### Proof.

Let $`v,wE^0`$, then since $`E`$ is strongly connected there are paths $`\alpha E^k`$ and $`\beta E^{\mathrm{}}`$ from $`v`$ to $`w`$ and $`w`$ to $`v`$, respectively. So, if $`w`$ is the source of a loop of length $`s`$ then $`v`$ is the source of loops of length $`k+\mathrm{}+s`$ and $`k+\mathrm{}+2s`$. Hence $`d(v)`$ divides $`(k+\mathrm{}+2s)(k+\mathrm{}+s)=s`$. Therefore $`d(v)`$ divides $`s`$ for every loop with source $`w`$ of length $`s`$. Since $`d(w)`$ is the greatest common divisor of such numbers $`s`$ we must have $`d(v)d(w)`$. But since the argument can be repeated with $`v`$ and $`w`$ exchanged we have $`d(w)d(v)`$ and so $`d(v)=d(w)`$ as required. ∎

Hence we may define the period of a strongly directed graph to be the period of any one of its vertices. If $`E`$ is strongly connected with period $`1`$ and has finitely many vertices then its vertex incidence matrix $`A_E`$ is aperiodic in the sense that there is a $`k1`$ such that every entry of $`A_E^k`$ is strictly positive (cf. \[CK, p.253\]).

###### Lemma 4.2.

Let $`E`$ be a strongly connected graph with period $`d`$. For each $`vE^0`$ there is a positive integer $`N(v)`$ such that for $`kN(v)`$, $`v`$ is the source of a loop of length $`kd`$.

###### Proof.

Suppose that $`\alpha E^{kd}`$ and $`\beta E^{sd}`$ are loops with source $`v`$. Then $`\alpha \beta E^{(k+s)d}`$ is a loop with source $`v`$. Hence the set

$$V=\{kd:\text{ there is a loop of the length }kd\text{ in }E\text{ with source }v\text{ }\}$$

of positive integers is closed under addition, and also their the greatest common divisor is $`d`$. But then by Lemma \[S, Lemma A3\] $`V`$ must contain all but a finite number of positive multiples of $`d`$, and the result follows. ∎

Next we examine the structure of the finite path space of a strongly connected graph with period $`d`$ (see \[S, Theorem 1.3 in Part I\]):

###### Lemma 4.3.

Let $`E`$ be a strongly connected graph with period $`d`$, and $`vE^0`$. For any $`wE^0`$ there exists $`r_w`$ with $`0r_w<d`$ such that

* if $`\mu E^s`$ is a path from $`v`$ to $`w`$ then $`sr_w`$ (mod $`d`$),
* there is a positive integer $`N(w)`$ such that for $`kN(w)`$ there is a path of length $`kd+r_w`$ from $`v`$ to $`w`$.

###### Proof.

For (i), let $`\alpha E^m`$ and $`\beta E^m^{}`$ be paths from $`v`$ to $`w`$. Since $`E`$ is strongly connected there is a path $`\gamma E^p`$ from $`w`$ to $`v`$. Hence $`\alpha \gamma E^{m+p}`$ and $`\beta \gamma E^{m^{}+p}`$ are loops with source $`v`$. Since $`E`$ has period $`d`$ it follows that $`d`$ divides $`m+p`$ and $`m^{}+p`$, and so $`d`$ divides $`(m+p)(m^{}+p)=mm^{}`$, that is, $`mm^{}0`$ (mod $`d`$). Set $`r_w=m`$ (mod $`d`$). If $`\mu E^s`$ is a path from $`v`$ to $`w`$ then $`sr_w`$ (mod $`d`$).

For (ii), let $`\alpha E^n`$ be a path from $`v`$ to $`w`$, then from (i) there is a positive integer $`m`$ such that $`n=md+r_w`$. By Lemma 4.2 there is a positive integer $`N_0`$ such that for all $`sN_0`$, $`v`$ is the source of a loop of length $`sd`$. Set $`N(w)=N_0+m`$, if $`kN(w)`$ then $`kmN_0`$ and so there is a loop $`\delta E^{(km)d}`$ with source $`v`$. Hence $`\alpha \delta `$ is a path of length $`n+(km)d=(m+km)d+r_w=kd+r_w`$ from $`v`$ to $`w`$. ∎

Note that if $`w=v`$ in the above Lemma, then $`r_v=0`$. Note also that $`r_w`$ in Lemma 4.3 is called a residue class of $`w`$ with respect to $`v`$ (cf. \[S, Definition 1.7 in Part I\]).

## 5. Skew product graphs

In this section we describe the relative skew product graph construction and show how it can be used to describe all connected coverings of a given connected graph. We introduce an invariant, called the local voltage group which enables us to describe the connected components of ordinary skew product graphs and exhibit them as ordinary skew product graphs in their own right. Finally we specialise to a certain skew product graphs formed from the integers with a view to applications to graph $`C^{}`$-algebras in the next section.

The following definition generalises the ones given in \[GT1, §4\] and \[GT, §2.3.2\] for row-finite graphs with finitely many vertices and groups which are finite. Let $`E`$ be a directed graph, $`\mathrm{\Gamma }`$ a countable group with subgroup $`H`$ and $`c:E^1\mathrm{\Gamma }`$ a function, which we think of as a labelling of the edges in $`E`$ by elements of $`\mathrm{\Gamma }`$. From this data we may form the relative skew product graph $`E\times _c(H\backslash \mathrm{\Gamma })`$ has vertex set $`E^0\times (H\backslash \mathrm{\Gamma })`$, edge set $`E^1\times (H\backslash \mathrm{\Gamma })`$ where the range and source of the the edge $`(e,Hg)`$ are given by

$$s(e,Hg)=(s(e),Hg)\text{ and }r(e,Hg)=(r(e),Hgc(e))\text{ respectively}.$$

If $`H`$ is the trivial subgroup of $`\mathrm{\Gamma }`$ then the above definition reduces to that of the ordinary skew product graph $`E\times _c\mathrm{\Gamma }`$ used in \[KP, Definition 2.1\] and \[GT, §2.1.1\] (as opposed to those used in \[KaQR, DPR\] where the labelling gives rise to a coaction of $`\mathrm{\Gamma }`$ on $`C^{}(E)`$). If $`H`$ is trivial there is a free action $`\lambda `$ of $`\mathrm{\Gamma }`$ on $`E\times _c\mathrm{\Gamma }`$ defined for $`g,h\mathrm{\Gamma }`$ by $`\lambda _h^i(x,g)=(x,hg)\text{ where }xE^i\text{ for }i=0,1`$. If $`H`$ is a subgroup of $`\mathrm{\Gamma }`$, then $`H`$ also acts freely on $`E\times _c\mathrm{\Gamma }`$ and the quotient graph $`H\backslash (E\times _c\mathrm{\Gamma })`$ is isomorphic to $`E\times _c(H\backslash \mathrm{\Gamma })`$ via the maps $`[x,g](x,Hg)`$ where $`xE^i`$ for $`i=0,1`$.

For functions $`c_1,c_2:E^1\mathrm{\Gamma }`$ we say that $`c_1`$ and $`c_2`$ are cohomologous and write $`c_1c_2`$ if there is a function $`b:E^0\mathrm{\Gamma }`$ such that $`c_1(e)b(r(e))=b(s(e))c_2(e)`$ for all $`eE^1`$. The relation $``$ amongst all functions from $`E^1`$ to $`\mathrm{\Gamma }`$ is an equivalence relation. If $`c_1,c_2:E^1\mathrm{\Gamma }`$ are cohomologous then $`E\times _{c_1}\mathrm{\Gamma }`$ is equivariantly isomorphic to $`E\times _{c_2}\mathrm{\Gamma }`$ and $`E\times _{c_1}(H\backslash \mathrm{\Gamma })E\times _{c_2}(H\backslash \mathrm{\Gamma })`$ via the maps $`(v,g)(v,gb(v))`$ and $`(e,g)(e,gb(s(e)))`$.

The map $`p_c:E\times _c(H\backslash \mathrm{\Gamma })E`$ defined by $`p_c(x,Hg)=x\text{ where }xE^i\text{ for }i=0,1`$ is a covering map. If $`E,E\times _c(H\backslash \mathrm{\Gamma })`$ are connected and $`H`$ is normal in $`\mathrm{\Gamma }`$ then $`p_c`$ is a regular covering since the image of $`\pi _1(E\times _c(H\backslash \mathrm{\Gamma }),(v,Hg))`$ under $`(p_c)_{}`$ is a normal subgroup of $`\pi _1(E,v)`$. In fact, we shall show that every connected covering of a given connected graph $`E`$ is a relative skew product graph formed from $`E`$ (cf. \[GT, GT1\]).

###### Lemma 5.1.

Let $`E`$ and $`F`$ be connected graphs, $`p:FE`$ a covering map, $`T`$ a spanning tree for $`E`$ and $`vE^0`$. Then there is a spanning forest $`\{\stackrel{~}{T}_u:up^1(v)\}`$ of $`F`$ such that $`p(\stackrel{~}{T}_u)=T`$ for all $`up^1(v)`$.

###### Proof.

For $`wE^0`$ let $`b_w`$ be the unique reduced walk in $`T`$ from $`v`$ to $`w`$. For $`up^1(v)`$ let $`\stackrel{~}{b}_w(u)`$ be the unique lift of $`b_w`$ to a reduced walk beginning at $`uF^0`$. Put $`\stackrel{~}{T}_u^0=r(\stackrel{~}{b}_w(u))`$ and let $`\stackrel{~}{T}_u^1`$ consist of all the edges comprising each $`\stackrel{~}{b_w}(u)`$ as $`w`$ runs through $`E^0`$. By the unique walk lifting property $`\stackrel{~}{T}_u`$ is a tree such that $`p(\stackrel{~}{T}_u)=T`$.

To show that $`\{\stackrel{~}{T}_u:up^1(v)\}`$ is a forest we must show that the $`\stackrel{~}{T}_u`$ are disjoint. Suppose that $`w`$ is a vertex in $`\stackrel{~}{T}_u\stackrel{~}{T}_u^{}`$, where $`u,u^{}p^1(v)`$. Let $`a`$ be the unique reduced walk in $`\stackrel{~}{T}_u`$ from $`u`$ to $`w`$ and $`b`$ be the unique reduced walk in $`\stackrel{~}{T}_u^{}`$ from $`u^{}`$ to $`w`$. Then $`ab^1`$ is a reduced walk in $`F`$ from $`u`$ to $`u^{}`$, and so $`p(ab^1)=p(a)p(b)^1`$ is a loop in $`T`$ with source $`v`$. Hence $`p(a)=p(b)`$ and then $`a^1=b^1`$ by unique walk lifting at $`w`$. Therefore we have that $`u=s(a)=s(b)=u^{}`$. A similar argument shows that $`\stackrel{~}{T}_u`$ and $`\stackrel{~}{T}_u^{}`$ cannot have an edge in common.

To show that $`\{\stackrel{~}{T}_u:up^1(v)\}`$ spans $`F`$, suppose that $`wF^0`$, then there exists a unique reduced walk $`b_{p(w)}`$ in $`T`$ from $`v`$ to $`p(w)`$. By the unique walk lifting property there is a reduced walk $`\stackrel{~}{b}_{p(w)}^1`$ in $`F`$ such that $`s(\stackrel{~}{b}_{p(w)}^1)=w`$ and $`p(\stackrel{~}{b}_{p(w)}^1)=b_{p(w)}^1`$. Since $`p(r(\stackrel{~}{b}_{p(w)}^1))=v`$ we must have $`r(\stackrel{~}{b}_w^1)p^1(v)`$ and so $`w`$ lies in $`\stackrel{~}{T}_{r(\stackrel{~}{b}_w^1)}`$. ∎

###### Theorem 5.2.

Let $`E,F`$ be connected graphs, $`p:FE`$ a covering map, $`T`$ a spanning tree for $`E`$ and $`vE^0`$ . Let $`wF^0`$ be such that $`p(w)=vE^0`$ then there exists a map $`c=c_{v,T}:E^1\pi _1(E,v)`$ such that $`FE\times _c(p_{}\pi _1(F,w)\backslash \pi _1(E,v))`$.

###### Proof.

Let $`H=p_{}\pi ^1(F,w)`$ and $`\{a_i:iI\}\pi ^1(E,v)`$ be a right transversal for $`H`$ in $`\pi ^1(E,v)`$. For $`iI`$, let $`\stackrel{~}{a_i}`$ be the lift of $`a_i`$ in $`F`$ with $`s(\stackrel{~}{a}_i)=w`$, put $`\stackrel{~}{v}_i=r(\stackrel{~}{a}_i)`$ then $`p^1(v)=\{\stackrel{~}{v}_i:iI\}`$. Let $`c=c_{v,T}:E^1\pi ^1(E,v)`$ be defined by $`c(e)=b_{s(e)}eb_{r(e)}^1`$ where $`b_{s(e)}`$ and $`b_{r(e)}`$ are the unique reduced walks in $`T`$ from $`v`$ to $`s(e)`$ and $`r(e)`$ respectively.

For $`iI`$ let $`\stackrel{~}{T}_i`$ be the tree $`\stackrel{~}{T}_{\stackrel{~}{v}_i}`$ in $`F`$ described in Lemma 5.1. Define a map $`\varphi :FE\times _c(H\backslash \pi ^1(E,v))`$ as follows: if $`u\stackrel{~}{T}_i^0`$, then set $`\varphi ^0(u)=(p(u),Ha_i)`$. If $`fF^1`$ is such that $`s(f)\stackrel{~}{T}_j^0`$ and $`r(f)\stackrel{~}{T}_i^0`$, then we put $`\varphi ^1(f)=(p(f),Ha_ic(p(f))^1)`$.

For $`fF^1`$ we have $`\varphi ^0(s(f))=(p(s(f)),Ha_j)`$ whereas

$$s(\varphi ^1(f))=s(p(f),Ha_ic(p(f))^1)=(s(p(f)),Ha_ic(p(f))^1),$$

so $`s(\varphi ^1(f))=\varphi ^0(s(f))`$ provided that $`Ha_ic(p(f))^1=Ha_j`$. To see this, let

$$h=\stackrel{~}{a}_i\stackrel{~}{b}_{r(f)}^1f^1\stackrel{~}{b}_{s(f)}\stackrel{~}{a}_j^1$$

where $`\stackrel{~}{b}_{r(f)}`$ is the lift of $`b_{p(r(f))}`$ with $`s(\stackrel{~}{b}_{r(f)})=\stackrel{~}{v}_i`$ and $`\stackrel{~}{b}_{s(f)}`$ is the lift of $`b_{p(s(f))}`$ with $`s(\stackrel{~}{b}_{r(f)})=\stackrel{~}{v}_j`$; so $`h`$ is a closed walk in $`F`$ with $`s(h)=w`$. Hence

$$p(h)=a_ib_{p(r(f))}^1p(f)^1b_{p(s(f))}a_j^1=a_ic(p(f))^1a_j^1H,$$

and so $`Ha_ic(p(f))^1=Ha_j`$ as required. It is straightforward to show that $`r\varphi ^1=\varphi ^0r`$, and hence $`\varphi `$ is a graph morphism.

We now show that $`\varphi `$ is injective. Suppose that for some $`\stackrel{~}{e},\stackrel{~}{f}F^1`$ we have $`\varphi ^1(\stackrel{~}{e})=\varphi ^1(\stackrel{~}{f})`$, where $`r(\stackrel{~}{e})\stackrel{~}{T}_i`$, $`r(\stackrel{~}{f})\stackrel{~}{T}_i^{}`$, $`s(\stackrel{~}{e})\stackrel{~}{T}_j`$ and $`s(\stackrel{~}{f})\stackrel{~}{T}_j^{}`$. Then $`(p(\stackrel{~}{e}),Ha_ic(p(\stackrel{~}{e}))^1)=(p(\stackrel{~}{f}),Ha_i^{}c(p(\stackrel{~}{f}))^1)`$ in which case $`p(\stackrel{~}{e})=p(\stackrel{~}{f})`$ and then $`i=i^{}`$. Let $`\stackrel{~}{b}`$ be a reduced walk in $`\stackrel{~}{T}_i`$ from $`s(\stackrel{~}{e})`$ to $`s(\stackrel{~}{f})`$ then $`b=p(\stackrel{~}{b})`$ is a closed reduced walk in $`T`$ which implies that $`s(\stackrel{~}{e})=s(\stackrel{~}{f})`$. So $`\stackrel{~}{e}=\stackrel{~}{f}`$ by unique walk lifting of $`p(\stackrel{~}{e})=p(\stackrel{~}{f})`$ at $`s(\stackrel{~}{e})`$. The proof that $`\varphi `$ is injective on $`F^0`$ follows similarly.

Finally we claim that $`\varphi `$ is surjective. Given $`(e,Ha_j)`$ in $`(E\times _c(H\backslash \pi _1(E,v)))^1`$, let $`\stackrel{~}{a}=\stackrel{~}{a_j}\stackrel{~}{b}_{s(e)}`$ be the lift of $`a_j`$ at $`w`$ followed by the lift of $`b_{s(e)}`$ at $`\stackrel{~}{v}_j`$. Set $`\stackrel{~}{e}`$ to be the lift of $`e`$ in $`F`$ based at $`r(\stackrel{~}{a})`$, then $`s(\stackrel{~}{e})\stackrel{~}{T}_j`$ and suppose that $`r(\stackrel{~}{e})\stackrel{~}{T}_i`$. Then since $`p(\stackrel{~}{e})=e`$ we have $`\varphi ^1(\stackrel{~}{e})=(e,Ha_ic(e)^1)`$ and $`Ha_ic(e)^1=Ha_j`$ by a similar argument to the one given to show that $`\varphi ^0s=s\varphi ^1`$ above. The proof that $`\varphi ^0`$ is surjective follows similarly. ∎

The function $`c=c_{v,T}:E^1\pi _1(E,v)`$ given in the proof of Theorem 5.2 depends on the transversal $`p_{}\pi _1(F,w)`$ in $`\pi _1(E,v)`$, and the choice of $`v`$ and $`T`$. In Remarks 5.9 we show that the cohomology class of $`c`$ is independent of the choice of $`v`$ and $`T`$. By unique walk lifting, a different transversal has no effect other than to permute the trees in the spanning forest of $`F`$.

We shall now fix our attention on ordinary skew product graphs. Let $`E`$ be a directed graph and $`c:E^1\mathrm{\Gamma }`$ a function where $`\mathrm{\Gamma }`$ is a countable group. Then there is a map (which we shall also denote by $`c`$) from $`\pi _1(E)`$ to $`\mathrm{\Gamma }`$ defined by

$$c(a_1\mathrm{}a_n)=c(a_1)\mathrm{}c(a_n),$$

where $`c(e^1)=c(e)^1`$. It is straightforward to show that $`c`$ is a functor from $`\pi _1(E)`$ to $`\mathrm{\Gamma }`$. For $`vE^0`$ let

$$\mathrm{\Gamma }_v(c)=\{c(a):a\pi ^1(E,v)\}.$$

Since it is the range of a homomorphism, $`\mathrm{\Gamma }_v(c)`$ is a subgroup of $`\mathrm{\Gamma }`$, called the local voltage group of $`c`$ based at $`v`$ (in \[GT, §2.5\] these groups are referred to as the local group). The following facts are not difficult to establish (see \[Rh, Lemma 6.5\]):

###### Lemma 5.3.

Let $`E`$ be a directed graph and $`c:E^1\mathrm{\Gamma }`$ a function where $`\mathrm{\Gamma }`$ is a countable group.

* If there is a walk between $`v,wE^0`$ then $`\mathrm{\Gamma }_v(c)`$ and $`\mathrm{\Gamma }_w(c)`$ are conjugate subgroups of $`\mathrm{\Gamma }`$.
* If $`c_1,c_2:E^1\mathrm{\Gamma }`$ are cohomologous then for all $`vE^0`$, $`\mathrm{\Gamma }_v(c_1)`$ and $`\mathrm{\Gamma }_v(c_2)`$ are conjugate subgroups of $`\mathrm{\Gamma }`$.

###### Remark 5.4.

Let $`E`$ be a directed graph and $`c:E^1\mathrm{\Gamma }`$ a function where $`\mathrm{\Gamma }`$ is a countable group. If $`\stackrel{~}{a}`$ is a reduced walk in $`E\times _c\mathrm{\Gamma }`$ from $`(v,g)`$ to $`(u,h)`$, then $`h=gc(a)`$ and $`a=p_c(\stackrel{~}{a})`$ is a reduced walk in $`E`$ from $`v`$ to $`u`$ (cf. \[GT, Theorem 2.1.2\]).

###### Proposition 5.5.

Let $`E`$ be a connected graph, $`c:E^1\mathrm{\Gamma }`$ a function where $`\mathrm{\Gamma }`$ is a countable group. Then the vertices $`(v,g)`$ and $`(u,h)`$ lie in the same connected component of $`E\times _c\mathrm{\Gamma }`$ if and only if there is a reduced walk $`a`$ in $`E`$ from $`v`$ to $`u`$ such that $`g^1h`$ lies in the coset $`\mathrm{\Gamma }_v(c)c(a)`$ of the local voltage group of $`c`$ based at $`v`$.

###### Proof.

If $`(v,g)`$ and $`(u,h)`$ lie in the same connected component of $`E\times _c\mathrm{\Gamma }`$ then there exists a reduced walk $`\stackrel{~}{a}`$ in $`E\times _c\mathrm{\Gamma }`$ from $`(v,g)`$ to $`(u,h)`$. By Remark 5.4 we have $`h=gc(a)`$, where $`a=p_c(\stackrel{~}{a})`$, then $`g^1h=c(a)`$ lies in $`\mathrm{\Gamma }_v(c)c(a)`$ as required.

Conversely let $`a`$ be a reduced walk in $`E`$ from $`v`$ to $`u`$ such that $`g^1h\mathrm{\Gamma }_v(c)c(a)`$. Hence there is $`b\pi ^1(E,v)`$ such that $`g^1h=c(b)c(a)=c(ba)`$. Let $`\stackrel{~}{d}`$ be the unique lift of $`d=ba`$ in $`E\times _c\mathrm{\Gamma }`$ starting at $`(v,g)`$ then $`\stackrel{~}{d}`$ is a reduced walk in $`E\times _c\mathrm{\Gamma }`$ with $`s(\stackrel{~}{d})=(v,g)`$ and $`r(\stackrel{~}{d})=(r(ba),gc(ba))=(u,h)`$ so that $`(v,g)`$ and $`(u,h)`$ are in the same connected component. ∎

###### Corollary 5.6.

Let $`E`$ be a connected graph and $`c:E^1\mathrm{\Gamma }`$ a function where $`\mathrm{\Gamma }`$ is a countable group. Then $`E\times _c\mathrm{\Gamma }`$ consists of $`|\mathrm{\Gamma }:\mathrm{\Gamma }_v(c)|`$ mutually isomorphic connected components, where $`\mathrm{\Gamma }_v(c)`$ is the local voltage group of $`c`$ based at $`vE^0`$. In particular, $`E\times _c\mathrm{\Gamma }`$ is connected if and only if $`\mathrm{\Gamma }_v(c)=\mathrm{\Gamma }`$ for some $`vE^0`$.

###### Proof.

By Proposition 5.5 the number of connected components of $`E\times _c\mathrm{\Gamma }`$ is equal to $`|\mathrm{\Gamma }:\mathrm{\Gamma }_v(c)|`$, the number of cosets of $`\mathrm{\Gamma }_v(c)`$ in $`\mathrm{\Gamma }`$. Since the natural action $`\lambda `$ of $`\mathrm{\Gamma }`$ on $`E\times _c\mathrm{\Gamma }`$ is transitive on $`p_c^1(v)=\{(v,g):g\mathrm{\Gamma }\}`$ for all $`vE^0`$ and $`E`$ is connected it follows that the connected components of $`E\times _c\mathrm{\Gamma }`$ are mutually isomorphic. ∎

There appears to be an error on \[GT, p.88\] where it is shown that the connected components of $`E\times _c\mathrm{\Gamma }`$ are mutually isomorphic by the transitivity of the natural action of $`\mathrm{\Gamma }`$ on $`E\times _c\mathrm{\Gamma }`$ – which is certainly not the case in general.

###### Definition 5.7.

Let $`E`$ be a directed graph, $`c:E^1\mathrm{\Gamma }`$ a function where $`\mathrm{\Gamma }`$ is a countable group. Fix $`T`$ a spanning tree of $`E`$ and vertex $`vE^0`$ then define the $`T`$–voltage based at $`v`$ to be the function $`c_{v,T}:E^1\mathrm{\Gamma }`$ given by

(5.1)
$$c_{v,T}(e):=c(b_{s(e)}eb_{r(e)}^1)=c(b_{s(e)})c(e)c(b_{r(e)})^1,$$

where for $`wE^0`$, $`b_w`$ is the unique reduced walk in $`T`$ from $`v`$ to $`w`$.

The function $`c_{v,T}:E^1\mathrm{\Gamma }`$ is the same as the one used in the proof of Theorem 5.2. The following result is not difficult to establish

###### Proposition 5.8.

Let $`E`$ be a directed graph with spanning tree $`T`$ and $`c:E^1\mathrm{\Gamma }`$ be a function where $`\mathrm{\Gamma }`$ is a countable group. Then for $`vE^0`$, we have $`c_{v,T}c`$; furthermore $`\mathrm{\Gamma }_v(c)=\mathrm{\Gamma }_v(c_{v,T})`$.

###### Remarks 5.9.

Proposition 5.8 shows that if we use another base vertex to compute the $`T`$-voltages or if we use a different spanning tree then we get an cohomologous function from $`E^1`$ to $`\mathrm{\Gamma }`$. Moreover, if $`T`$ is a spanning tree for $`E`$ then the local voltage group of $`c`$ at $`v`$ is generated by $`\{c_{v,T}(e):eE^1\backslash T^1\}`$ (cf. \[GT, Theorem 2.5.3\]).

###### Proposition 5.10.

Let $`E`$ be a connected directed graph with spanning tree $`T`$, $`vE^0`$ and $`c:E^1\mathrm{\Gamma }`$ a function where $`\mathrm{\Gamma }`$ is a countable group. Then each connected component of $`E\times _c\mathrm{\Gamma }`$ is isomorphic to $`E\times _{c_{v,T}}\mathrm{\Gamma }_v(c)`$.

###### Proof.

For $`wE^0`$ let $`b_w`$ be the unique reduced walk in $`T`$ from $`v`$ to $`w`$. Since each of the connected components of $`E\times _c\mathrm{\Gamma }`$ are isomorphic by Corollary 5.6, we shall deal with the connected component $`F`$ which contains the vertex $`(v,1_\mathrm{\Gamma })`$. Define $`\varphi :E\times _{c_{v,T}}\mathrm{\Gamma }_v(c)E\times _c\mathrm{\Gamma }`$ by

$$\varphi ^0(v,c(a))=(v,c(a)c(b_v))\text{ and }\varphi ^1(e,c(a))=(e,c(a)c(b_{s(e)})),$$

where $`a\pi _1(E,v)`$. We check that $`\varphi `$ is a graph morphism:

$`\varphi ^0(r(e,c(a))=\varphi ^0(r(e)c(a)c(b_{s(e)}eb_{r(e)}^1))`$ $`=(r(e),c(a)c(b_{s(e)}e))`$
$`=r(e,c(a)c(b_{s(e)})=r(\varphi ^1(e,c(a)),`$
and

$$\varphi ^0(s(e,c(a)))=(s(e),c(a)b_{s(e)})=s(e,c(a)b_{s(e)})=s(\varphi ^1(e,c(a)).$$

To see that $`\varphi `$ is injective, suppose that $`\varphi ^1(e,c(a))=\varphi ^1(f,c(b))`$, then $`(e,c(a)c(b_{s(e)}))=(f,c(b)c(b_{s(f)}))`$ in which case $`e=f`$ and then $`c(a)=c(b)`$. To show that $`\varphi ^0`$ is injective is similar. It only remains to show that the image of $`\varphi `$ is $`F`$. Suppose that $`(u,g)F^0`$ then there is a reduced walk $`\stackrel{~}{b}`$ from $`(v,1_\mathrm{\Gamma })`$ such that $`b=p_c(\stackrel{~}{b})`$ is a reduced walk in $`E`$ from $`v`$ to $`u`$ with $`g=c(b)`$. Since $`bb_u^1`$ is a closed reduced walk in $`E`$ which begins at $`v`$ it follows that $`c(bb_u^1)\mathrm{\Gamma }_v(c)`$ and then $`(u,c(bb_u^1)`$ is a vertex in $`E\times _{c_{v,T}}\mathrm{\Gamma }_v(c)`$ such that $`\varphi ^0(u,c(bb_u^1))=(u,c(b))=(u,g)`$. A similar proof shows that $`\varphi ^1`$ is surjective which completes our proof. ∎

###### Remark 5.11.

Let $`E`$ be a directed graph and $`c:E^1\mathrm{\Gamma }`$ a function. If $`E\times _c\mathrm{\Gamma }`$ is cofinal then $`E`$ is cofinal, however the converse is not true.

We shall be interested in the case when each edge in $`E`$ is labelled by the integer $`1`$. The skew product graph $`E\times _c𝐙`$ then has no loops (see \[KP, Proposition 2.6\]). The next result can be deduced from the definitions and the results from section 4.

###### Proposition 5.12.

Let $`E`$ be strongly connected and let $`c:E^1𝐙`$ given by $`c(e)=1`$ for all $`eE^1`$. If $`E`$ has period $`d`$ then $`\mathrm{\Gamma }_v(c)d𝐙`$ for all $`vE^0`$.

If $`E^0`$ is finite then we can say a little more.

###### Proposition 5.13.

Let $`E`$ be a strongly connected graph of period $`d`$ with finitely many vertices. Let $`c:E^1𝐙`$ be given by $`c(e)=1`$ for all $`eE^1`$, then each connected component of $`E\times _c𝐙`$ is cofinal.

###### Proof.

Suppose that $`\stackrel{~}{x}`$ is an infinite path in one connected component of $`E\times _c𝐙`$ and $`(v,m)`$ a vertex in the same component. Since $`E^0`$ is finite there is $`uE^0`$ and an increasing sequence $`n_1n_2n_3\mathrm{}`$ of integers such that $`(u,n_i)`$ is the range of some edge in $`\stackrel{~}{x}`$. Let $`\alpha `$ be a shortest path from $`v=p_c(v,m)`$ to $`w=s(p_c(\stackrel{~}{x}))`$ in $`E`$, then $`|\alpha |=r_w`$, the residue class of $`w`$ in $`E`$ with respect to $`v`$ (see Lemma 4.3). Let $`\stackrel{~}{\alpha }`$ be the lift of $`\alpha `$ in $`E\times _c𝐙`$ with source $`(v,m)`$, then by Remark 5.4, $`r(\stackrel{~}{\alpha })=(w,m+r_w)`$. Since $`(w,n):=s(\stackrel{~}{x})`$ and $`(w,m+r_w)`$ belong to the same connected component, by Proposition 5.5 we must have

(5.2)
$$n(m+r_w)=k^{}d$$

for some $`k^{}𝐙`$. Since $`(w,n)`$ connects to $`(u,n_i)`$, it also follows from Lemma 4.3(ii) that for all $`i1`$ we have

(5.3)
$$n_i=n+k_id+s_u$$

for some $`k_i1`$, where $`s_u`$ is the residue class of $`u`$ in $`E`$ with respect to $`w`$. By Lemma 4.3(ii) there is a positive integer $`N(u)`$ such that for all $`kN(u)`$ there exists a path of length $`kd+s_u`$ from $`w`$ to $`u`$. Since the $`k_i`$’s become arbitrarily large we may assume that $`k^{}+k_iN(u)`$ for sufficiently large $`i`$, and so by Lemma 4.3(ii) there exists paths $`\beta _i`$ in $`E`$ from $`w`$ to $`u`$ of length $`(k^{}+k_i)d+s_u`$. Let $`\stackrel{~}{\beta }_i`$ be the lift of $`\beta _i`$ in $`E\times _c𝐙`$ with source $`(w,m+r_w)`$, then by Remark 5.4

$`r(\stackrel{~}{\beta }_i)`$ $`=(u,m+r_w+(k^{}+k_i)d+s_u)`$
$`=(u,m+r_w+(n(m+r_w))+k_id+s_u)\text{ by (}\text{5.2}\text{)}`$
$`=(u,n+k_id+s_u)=(u,n_i)\text{ by (}\text{5.3}\text{).}`$
Hence $`\stackrel{~}{\alpha }\stackrel{~}{\beta }_i`$ is a path in the connected component of $`E\times _c𝐙`$ containing $`(v,m)`$ and $`(w,n)`$ beginning at $`(v,m)`$ and ending at $`(u,n_i)`$ for sufficiently large $`i`$. Since $`\stackrel{~}{x}`$ passes through $`(u,n_i)`$ for all $`i`$ it follows that this component is cofinal by definition. ∎

## 6. The AF core

Let $`E`$ be a directed graph, and $`\{s_e,p_v\}`$ a Cuntz-Krieger $`E`$-family generating $`C^{}(E)`$. There is a strongly continuous action $`\gamma `$ of $`𝐓`$ on $`C^{}(E)`$ called the gauge action which is characterised by

$$\gamma _zs_e=zs_e,\text{ and }\gamma _zp_v=p_v,$$

where $`z𝐓`$. The fixed point algebra of the gauge action, $`C^{}(E)^\gamma `$ is AF and normally referred to as the AF core (see \[PR, §2.2\] and \[BPRSz, §2\]). We wish to establish conditions which guarantee that $`C^{}(E)^\gamma `$ is simple. To do this we shall use the following Morita equivalence which was established in \[KP, Proposition 2.8\].

###### Lemma 6.1.

Let $`E`$ be a row-finite directed graph with no sinks and sources, and $`c:E^1𝐙`$ be given by $`c(e)=1`$ for all $`eE^1`$. Then $`C^{}(E)^\gamma `$ is strongly Morita equivalent to $`C^{}(E\times _c𝐙)`$.

The case when there are finitely many vertices is straightforward.

###### Theorem 6.2.

Let $`E`$ be a row-finite directed graph with no sinks or sources and $`E^0`$ finite. Then $`C^{}(E)^\gamma `$ is simple if and only if $`E`$ is strongly connected with period $`1`$.

###### Proof.

Let $`E`$ be strongly connected with period one, and $`c:E^1𝐙`$ be given by $`c(e)=1`$ for all $`eE^1`$. By Proposition 5.13 the skew product graph $`E\times _c𝐙`$ is cofinal. Since $`E\times _c𝐙`$ has no loops and $`E`$ is row-finite, by Theorem 3.1 $`C^{}(E\times _c𝐙)`$ is simple, and then so is $`C^{}(E)^\gamma `$ by Lemma 6.1.

Now suppose that $`C^{}(E)^\gamma `$ is simple, then by Lemma 6.1 $`C^{}(E\times _c𝐙)`$ is simple. From Theorem 3.1 $`E\times _c𝐙`$ is cofinal and so $`E`$ is cofinal by Remark 5.11. We claim that $`E`$ is strongly connected. Let $`u,vE^0`$ then since $`E^0`$ is finite and $`E`$ has no sources there is a loop $`\alpha E^{}`$ and a path $`\beta E^{}`$ with $`s(\alpha )=s(\beta )`$ and $`r(\beta )=v`$. Let $`x=\alpha \alpha \mathrm{}E^{\mathrm{}}`$ then since $`E`$ is cofinal there is a path $`\mu E^{}`$ with $`s(\mu )=u`$ and $`r(\mu )=s(\alpha )`$. Hence there is a path $`\mu \beta E^{}`$ from $`u`$ to $`v`$, which establishes our claim. From Proposition 5.12 and Corollary 5.6 it follows that $`E`$ has period $`1`$. ∎

###### Remark 6.3.

Theorem 6.2 is not true if $`E^0`$ is infinite. The graph $`E`$ shown below

...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................$`\mathrm{}`$$``$$``$$``$$``$$``$$`1`$$`2`$$`3`$$`4`$$`5`$
is clearly strongly connected with period $`1`$. However for the function $`c:E^1𝐙`$ given by $`c(e)=1`$ for all $`eE^1`$, the skew product graph $`E\times _c𝐙`$ is not cofinal.

If $`E`$ has sinks or a vertex of infinite valency then we will make use of the following result:

###### Lemma 6.4.

Let $`E`$ be a directed graph, and suppose that $`HE^0`$ is a nonempty saturated hereditary subset of $`E^0`$ such that $`HE^0`$, then $`C^{}(E)^\gamma `$ is not simple.

###### Proof.

Let $`H`$ be a nontrivial saturated hereditary subset of $`E^0`$ and $`I_H`$ be the gauge invariant ideal of $`C^{}(E)`$ generated by $`\{p_v:vH\}`$. Let $`\mathrm{\Phi }:C^{}(E)C^{}(E)^\gamma `$ be the conditional expectation associated to the gauge action, then $`\mathrm{\Phi }`$ is faithful on positive elements (cf. \[BPRSz, §1\]). Since $`H`$ is a proper subset of $`E^0`$, and $`\mathrm{\Phi }`$ an expectation which is faithful on positive elements, it follows that $`\mathrm{\Phi }(I_H)`$ is a proper ideal of $`C^{}(E)^\gamma `$ and the result follows. ∎

Let us first deal with the case when there are sinks.

###### Proposition 6.5.

Let $`E`$ be a row-finite directed graph which has at least one sink. Then $`C^{}(E)^\gamma `$ is simple if and only if $`E`$ consists of a single vertex.

###### Proof.

If $`E`$ consists a single vertex, then since are no edges we have $`C^{}(E)=C^{}(E)^\gamma =𝐂`$ which is simple. Suppose that $`E`$ has sinks $`v_1v_2`$ then $`\mathrm{\Sigma }(\{v_1\})`$ is a proper saturated hereditary subset of $`E^0`$ and so gives rise to a proper ideal in $`C^{}(E)^\gamma `$ by Lemma 6.4. Suppose now that $`v`$ is the only sink and let $`J`$ be the subalgebra of $`C^{}(E)^\gamma `$ generated by elements of the form $`s_\mu s_\nu ^{}`$ where $`\mu ,\nu E^n`$ for some $`n1`$ are such that $`r(\mu )=r(\nu )`$. It is straightforward to show that $`J`$ is a closed $`2`$-sided ideal in $`C^{}(E)`$. If $`E`$ has edges then $`J`$ is nontrivial and $`JC^{}(E)`$ since $`p_vJ`$. Hence $`C^{}(E)^\gamma `$ is simple only if there are no edges and $`E^0=\{v\}`$. ∎

The case when there is a vertex of infinite valency is quite similar.

###### Proposition 6.6.

Let $`E`$ be a directed graph with at least one vertex of infinite valency, then $`C^{}(E)^\gamma `$ is not simple.

###### Proof.

Suppose $`vE^0`$ has infinite valency. Let $`J`$ be the $`C^{}`$-subalgebra of $`C^{}(E)^\gamma `$ generated by elements of the form $`s_\mu s_\nu ^{}`$ where $`\mu ,\nu E^n`$ for some $`n1`$ are such that $`r(\mu )=r(\nu )`$. It is straightforward to show that $`J`$ is a closed $`2`$-sided ideal in $`C^{}(E)^\gamma `$. Now $`JC^{}(E)^\gamma `$ since $`p_vJ`$, and $`J`$ is nonzero since $`E`$ has edges, so the result follows. ∎

Now suppose that $`E^0`$ is infinite and $`E`$ has no sinks. If $`E`$ is either strongly connected or has no loops then we claim that for each $`vE^0`$ there is an infinite path $`x(v)`$, with source $`v`$ such that for all $`n`$ there is no path of length less than $`n`$ from $`v`$ to $`r(x(v)_n)`$. Every vertex on such a path is visited in the shortest distance from $`v`$. An infinite path with this property is said to be $`v`$-depth-first, since it is a path in the depth-first spanning tree of $`E`$ (see \[ChO, §3.3\]).

For $`vE^0`$ let $`V(0)=\{v\}`$ and for $`n1`$ let $`V(n)`$ denote those vertices to which $`v`$ connects by a path whose length is less than $`n`$. Since $`E^0`$ is infinite with no sinks and $`E`$ is strongly connected or has no loops it follows that $`V(n)`$ is nonempty and the containment $`V(n1)V(n)`$ is strict for $`n1`$. The set $`V(n)\backslash V(n1)`$ denotes those vertices which can be reached from $`v`$ with shortest path of length $`n`$. We say that a path $`\alpha E^n(v):=\{\alpha E^n:s(\alpha )=v\}`$ is $`v`$-deep if it uses different vertices, that is if $`r(\alpha _i)V(i)\backslash V(i1)`$ for $`1in`$. Let $`E_g^n(v)`$ denote the collection of $`v`$-deep paths in $`E^n(v)`$.

###### Lemma 6.7.

Let $`E`$ be a directed graph with $`E^0`$ infinite and no sinks. If $`E`$ is strongly connected or has no loops then for $`vE^0`$ the set $`E_g^n(v)`$ is non-empty for all $`n1`$.

###### Proof.

The result then follows immediately from the fact that $`r\left(E_g^n(v)\right)=V(n)\backslash V(n1)`$ which is non-empty for all $`n1`$. ∎

###### Theorem 6.8.

Let $`E`$ be a row-finite directed graph with $`E^0`$ infinite and no sinks. If $`E`$ is strongly connected or has no loops then for each $`vE^0`$ there is a $`v`$-depth-first path.

###### Proof.

For integers $`m>n0`$ let $`E_g^{n,m}(v)`$ denote those $`\alpha ^{}E_g^n(v)`$ which appear as the first part of some $`\alpha E_g^m(v)`$. Clearly $`E_g^{n,m}(v)\mathrm{}`$ for all $`m>n0`$ since $`E_g^m(v)`$ is non-empty and for any $`\alpha =\alpha ^{}\alpha ^{\prime \prime }E_g^m(v)`$ with $`\alpha ^{}E^n(v)`$ we have $`\alpha ^{}E_g^{n,m}(v)`$. Moreover, this argument also shows that $`E_g^{n,m}(v)E_g^{n,p}(v)`$ for all integers $`p>m>n0`$. Let

$$E_g^{n,\mathrm{}}(v)=\underset{m>n}{}E_g^{n,m}(v),$$

then $`E_g^{n,\mathrm{}}(v)\mathrm{}`$ since it is the intersection of a decreasing sequence of finite non-empty sets. Now we may define the infinite path we seek: Since $`E_g^{1,\mathrm{}}(v)\mathrm{}`$ there is $`x(v)_1E^1`$ such that there are $`\alpha _nE^n`$ for $`n1`$ with $`x(v)_1\alpha _nE_g^{1,n+1}(v)`$. Since $`E`$ is row-finite there is $`x(v)_2E^1`$ such that there are infinitely many such $`\alpha _n`$ with $`\alpha _n=x(v)_2\alpha ^{\prime \prime }`$ where $`\alpha ^{\prime \prime }E^{n1}`$. In particular $`x(v)_1x(v)_2E_g^{2,\mathrm{}}(v)`$ since for $`n>2`$ there are $`\alpha E_g^{2,n}(v)`$ with $`\alpha =x(v)_1x(v)_2\alpha ^{\prime \prime }`$ for some $`\alpha ^{\prime \prime }E^{n2}`$. In this way we may define $`x(v)=(x(v)_i)E^{\mathrm{}}`$ with $`s(x(v)_1)=v`$ and $`r(x(v)_i)V(i)\backslash V(i1)`$ for all $`i1`$. ∎

###### Corollary 6.9.

Let $`E`$ be a row-finite directed graph with $`E^0`$ infinite and no sinks. If $`E`$ is strongly connected or has no loops then $`C^{}(E)^\gamma `$ is not simple.

###### Proof.

Let $`c:E^1𝐙`$ be given by $`c(e)=1`$ for all $`eE^1`$ and for $`vE^0`$, let $`x(v)`$ be a $`v`$-depth-first path. Let $`x^{}(E\times _c𝐙)^{\mathrm{}}`$ be the lift of $`x(v)`$ with source $`(1,v)`$, and suppose that $`\alpha ^{}`$ is such that $`s(\alpha ^{})=(0,v)`$ and $`r(\alpha ^{})=r(x_{}^{}{}_{i}{}^{})=(i1,r(x(v)_i))`$ for some $`i`$. Hence $`\alpha =p_c(\alpha ^{})`$ is a path of length $`i1`$ from $`v`$ to $`r(x(v)_i)`$ which means that $`r(x(v)_i)V(i1)`$, which contradictions the definition of $`x(v)`$. Hence $`E\times _c𝐙`$ is not cofinal, so $`C^{}(E\times _c𝐙)`$ is not simple by Theorem 3.1 and hence $`C^{}(E)^\gamma `$ is not simple by Lemma 6.1

###### Theorem 6.10.

Let $`E`$ be a directed graph, then $`C^{}(E)^\gamma `$ is simple if and only if either $`E`$ has a cofinal strongly connected subgraph of period $`1`$ which has finitely many vertices or $`E`$ consists of a single vertex.

###### Proof.

If $`E`$ has a vertex infinite valency then $`C^{}(E)^\gamma `$ is not simple by Proposition 6.6. So we may suppose that $`E`$ is row-finite. If $`E`$ is not cofinal then, by the proof of Theorem 3.1, there is a nontrivial saturated hereditary subset of $`E^0`$ which gives rise to a nontrivial ideal in $`C^{}(E)^\gamma `$ by Lemma 6.4. So we may suppose that $`E`$ is cofinal. If $`E`$ does not satisfy condition (K) then there is a cofinal subgraph $`L`$ which consists of a loop with no exits. Let $`c:E^1𝐙`$ be given by $`c(e)=1`$ for all $`eE^1`$, then $`E\times _c𝐙`$ is cofinal if and only if $`L`$ has one vertex. Hence by Lemma 6.1, $`C^{}(E)^\gamma `$ is simple if and only if $`E`$ has a cofinal strongly connected subgraph of period $`1`$ which consists of a single vertex (and edge). So we may suppose that $`E`$ also satisfies condition (K). Therefore we may assume that $`E`$ satisfies conditions (i)-(iii) of Theorem 3.1 and so $`C^{}(E)`$ is simple.

If $`E`$ has a sink then by Proposition 6.5, $`C^{}(E)^\gamma `$ is simple if and only if $`E`$ consists of a single vertex. So we suppose that $`E`$ has no sinks. By Theorem 3.2 either $`E`$ has no loops or there is a strongly connected cofinal subgraph $`FE`$. Suppose that $`E`$ has no loops, then $`E^0`$ cannot be finite (as that would mean there had to be a sink cf. \[KPR, §2\]). If $`E^0`$ is infinite then $`C^{}(E)^\gamma `$ is not simple by Corollary 6.9. Suppose $`E`$ has a strongly connected cofinal subgraph $`F`$ then by Corollary 3.3 there is a projection $`PM(C^{}(E))`$ such that $`C^{}(F)PC^{}(E)P`$. Since this isomorphism is essentially the identity map, it commutes with the usual gauge actions on $`C^{}(E)`$ and $`C^{}(F)`$ which are both denoted by $`\gamma `$. The projection $`P`$ is the limit of a sum of projections in $`C^{}(E)`$ which are invariant under the gauge action. Hence $`PM(C^{}(E))^\gamma `$, and then $`C^{}(F)^\gamma PC^{}(E)^\gamma P`$. Since $`F`$ is cofinal in $`E`$, it follows that $`PC^{}(E)^\gamma P`$ is full and so $`C^{}(E)^\gamma `$ is strongly Morita equivalent to $`C^{}(F)^\gamma `$. The result now follows from Theorem 6.2 and Theorem 6.9. ∎

If we discount the trivial case when the graph only consists of a single vertex, Theorem 6.10 says the following: Up to Morita equivalence, the only graphs $`E`$ for which the AF core of $`C^{}(E)`$ is simple are those which have finitely many vertices and are strongly connected with period one. For strongly connected graphs we have the following structure results for the AF core.

###### Theorem 6.11.

Let $`E`$ be a strongly connected row-finite graph with period $`d`$. Then $`C^{}(E)^\gamma `$ is a direct sum of $`d`$ mutually isomorphic AF algebras. If, in addition $`E^0`$ is finite then these AF algebras are simple.

###### Proof.

Let $`E`$ be strongly connected, row-finite with period $`d`$, and $`c:E^1𝐙`$ be given by $`c(e)=1`$ for all $`eE^1`$. By Corollary 5.6 $`E\times _c𝐙`$ consists of $`d`$ mutually isomorphic components. Since each component is a subgraph of a graph which has no loops, the first part follows from Lemma 6.1 and \[KPR, Theorem 2.4\]. If $`E^0`$ is finite then each component is cofinal by Proposition 5.13 and the last statement follows from Theorem 3.1. ∎

###### Theorem 6.12.

Let $`E`$ be a strongly connected row-finite graph with finitely many vertices, then $`C^{}(E)`$ is stably isomorphic to a crossed product of a simple AF algebra by an action of $`𝐙`$.

###### Proof.

Let $`E`$ be a strongly connected graph with period $`d`$, $`T`$ be a spanning tree for $`E`$, $`vE^0`$ and $`c:E^1𝐙`$ be given by $`c(e)=1`$ for all $`eE^1`$. By Proposition 5.10 each component of $`E\times _c𝐙`$ is isomorphic to $`E\times _{c_{v,T}}\mathrm{\Gamma }_v(c)`$. Since $`E`$ is strongly connected with period $`d`$, by Proposition 5.12 we have $`\mathrm{\Gamma }_v(c)=d𝐙𝐙`$. Let $`\lambda `$ denote the free $`𝐙`$-action on $`E\times _{c_{v,T}}d𝐙`$ which has quotient $`E`$ then by \[KP, Corollary 3.9\] we have

$$C^{}(E\times _{c_{v,T}}d𝐙)\times _\lambda 𝐙C^{}(E)𝒦\left(\mathrm{}^2(𝐙)\right).$$

Since $`E\times _{c_{v,T}}d𝐙`$ is isomorphic to a subgraph of $`E\times _c𝐙`$ it has no loops, and so $`C^{}(E\times _{c_{v,T}}d𝐙)`$ is AF by \[KPR, Theorem 2.4\]. If $`E^0`$ is finite then $`E\times _{c_{v,T}}d𝐙`$ is cofinal by Proposition 5.13. It then follows that $`C^{}(E\times _{c_{v,T}}d𝐙)`$ is simple by Theorem 3.1 which completes the proof. ∎