Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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|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

1 Answer

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|improve this answer
for a more worked-out answer, see here... – draks ... Aug 2 '12 at 12:02

Your Answer

 
discard

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.