> Which sequences of natural numbers arise by counting the number of paths of length n from the chosen node in a pointed graph to itself?
I'll consider a simpler graph: one that has distinct loops of lengths \\(a_1, ... a_k\\). Then the number of paths with length \\(n\\) that start and end at the chosen node is the number of ways to pick nonnegative integer coefficients \\(b_i\\) such that:
\\(n=\sum_i^k a_i \cdot b_i\\)
_Edit: that's not good enough! See my discussion with John below._
I have no idea how to simplify that expression, but I claim it to be the answer to John's first question.
Regarding the second question, if two graphs give the same sequence then they contain the same kinds of loops and the same number of them. I have no proof for this at the moment, just a strong hunch.