  It is known that the generating function associated with the enumeration of
non-backtracking walks on finite graphs is a rational matrix-valued function of
the parameter; such function is also closely related to graph-theoretical
results such as Ihara's theorem and the zeta function on graphs. In [P.
Grindrod, D. J. Higham, V. Noferini, The deformed graph Laplacian and its
application to network centrality analysis, SIAM J. Matrix Anal. Appl. 39(1),
310--341, 2018], the radius of convergence of the generating function was
studied for simple (i.e., undirected, unweighted and with no loops) graphs, and
shown to depend on the number of cycles in the graph. In this paper, we use
technologies from the theory of polynomial and rational matrices to greatly
extend these results by studying the radius of convergence of the corresponding
generating function for general, possibly directed and/or weighted, graphs. We
give an analogous characterization of the radius of convergence for directed
unweighted graphs, showing that it depends on the number of cycles in the
undirectization of the graph. For weighted graphs, we provide for the first
time an exact formula for the radius of convergence, improving a previous
result that exhibited a lower bound. Finally, we consider also
backtracking-downweighted walks on unweighted digraphs, and we prove a version
of Ihara's theorem in that case.
