  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.
