Let G be a directed graph with a countable number of vertices, and suppose G is strongly connected (given any two vertices v and w, there exists a path from v to w). Fix a base vertex v_{0}∈G, and let L_{n} denote the number of loops of length n based at v_{0}; that is, the number of sequences of vertices v_{0}, v_{1}, ..., v_{n} such that v_{n} = v_{0} and there is an edge from v_{i} to v_{i+1} for every 0 ≤ i < n. We allow the loops to self-intersect, repeat segments, etc.

Let h be the exponential growth rate of the number of such loops: $h=\lim_{n\to\infty} \frac 1n \log L_n$. The value of h may be either finite or infinite, and I am interested in finding conditions on the graph that help determine which of these is the case.

**Question****: Is there any characterisation of the set of graphs for which h < ∞?** A necessary and sufficient condition would be ideal, but anything that is known would be appreciated.

*Partial answer so far*: If G is uniformly locally finite -- that is, if there exists C < ∞ such that every vertex of G has incoming degree ≤ C or every vertex has outgoing degree ≤ C -- then L_{n} ≤ C^{n}, and so h ≤ log(C) < ∞. However, it is not difficult to construct locally finite graphs with unbounded degree, or even graphs that are not locally finite, for which h < ∞, so this condition is not necessary. *If G is undirected, or equivalently, if v → w implies w → v, then one can show that this condition is both necessary and sufficient. However, the directed case is more subtle.*

*Motivation*: One can define a *topological Markov chain* as the space of all infinite paths through the graph G together with a shift that maps v_{0}v_{1}v_{2}... to v_{1}v_{2}v_{3}.... The value h defined above is the *Gurevich entropy* of this dynamical system, and it is of interest to know when the Gurevich entropy is finite.