# Returning Paths on Cubic Graphs

Suppose we have a 3-edge-colorable cubic graph with $N$ vertices. How many paths of length $N$ exist that return to its origin?

Or putting it differently: What is "Pólya's Random Walk Constant" on such graphs?

-
Are you looking for *bounds* on Polya's random walk constant constant for such graphs? –  Srivatsan Nov 13 '11 at 23:13
Yes, that would be perfect. –  draks ... Nov 14 '11 at 7:14
In that case, please post at least a brief answer so that it can be upvoted by others (including me :)). You are even permitted to accept your answer. –  Srivatsan Nov 14 '11 at 19:49

## 1 Answer

I think what I was looking for is simply the diagonal entries of the $N$-th power of the adjacence matrix for the given graph. Maybe I should have noted that I'm dealing with finite graphs and I'm not expert enough to see if Pólya's Random Walk Constant makes sense here.

-
for a more worked-out answer, see here... –  draks ... Aug 2 '12 at 12:02