Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
@Srivatsan Hi again, it's been a while, but the question evolved as you could see when you follow the links in subsequent questions... – draks ... May 21 '15 at 11:04
up vote 0 down vote accepted

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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.