  The problem of a restricted random walk on graphs which keeps track of the
number of immediate reversal steps is considered by using a transfer matrix
formulation. A closed-form expression is obtained for the generating function
of the number of n-step walks with r reversal steps for walks on any graph. In
the case of graphs of a uniform valence, we show that our result has a
probabilistic meaning, and deduce explicit expressions for the generating
function in terms of the eigenvalues of the adjacency matrix. Applications to
periodic lattices and the complete graph are given.

Statistical Mechanics;Combinatorics