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 v0∈G, and let Ln denote the number of loops of length n based at v0; that is, the number of sequences of vertices v0, v1, ..., vn such that vn = v0 and there is an edge from vi to vi+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 Ln ≤ Cn, 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 v0v1v2... to v1v2v3.... 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.