Which integer recurrence relations can be formulated as counting walks on a graph?

Question

Observation: If we take the graph with two vertices, A and B, with a loop {A,A} and undirected edge {A,B}, then the number of closed walks $W_n$ of length $n \geq 1$ starting from A we get $W_1=1$ (counting AA), $W_2=2$ (counting AAA and ABA) and $W_n=W_{n-1}+W_{n-2}$, i.e. the Fibonacci numbers.

Question: Which types of recurrences can be realised as the number of closed walks from the origin of a graph?

More generally, which types of recurrences can be realised as the number of walks of some type in some graph?

If we can interpret a recurrence relation as the number of walks in a graph in some way, then might be able to use spectral theory to find formulas for the sequence. (see: Frank Harary and Allen J. Schwenk, The spectral approach to determining the number of walks in a graph. Pacific J. Math. Volume 80, Number 2 (1979), 443-449.)

Answer 1

Okay, so it's not quite a duplicate because I guess you're asking about initial conditions as well. The generating functions of the sequences $a_n$ which have this property are called $\mathbb{N}$-recognizable or $\mathbb{N}$-rational in the literature, and they are essentially (precisely?) the generating functions of word lengths in regular languages (star example: the look-and-say sequence). Not all rational functions with non-negative integer coefficients are $\mathbb{N}$-rational; see for example the counterexamples in these slides. These slides also seem relevant.

Stanley's Enumerative Combinatorics discusses some of these issues, in particular look at Section 4.7.

Answer 2

If the motivation is to use spectral methods, then there is no need to interpret things as a graph. To count walks in a graph one gets a recurrence relation (given by the adjacency matrix) and proceeds using spectral methods. If $A$ is an $n \times n$ matrix and $x_0$ a column vector then setting $x_{m+1}=Ax_m$ leads to a system of $n$ first order linear recurrences in the $n$ positions. In most non-degenerate cases one can get a single $nth$ order recurrence for a particular entry (or linear combination of entries). Similarly for the $r,c$ entry of $A^m$, the trace and other linear combinations. Really one is studying the entries of $A^m$ since $A^mx_0=x_m$. In the case that one starts with an $nth$ order linear recurrence one just has a rather special kind of graph.

That said, if the entries of $A$ are non-negative integers then one can naturally interpret $A^m$ as counting length $m$ walks in a certain $n$-vertex directed graph with multiple edges and loops allowed. For an arbitrary $n \times n$ matrix with entries from a ring one could consider the entries as multiplicitive edge weights on the complete $n$-vertex directed graph (with loops) and $A^m$ as recording in position $u,v$ the total weight of the length $m$ paths starting at $u$ and ending at $v$.

But again, once one enjoys the fact that every linear recurrence can be interpreted as a weighted path enumeration problem, there is usual not much motivation to actually do so. I suppose that the initial conditions are not really accounted for in this sketch, but they don't really come into solving recurrence relations until the very end.