1
$\begingroup$

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?

  • 0
    @Srivatsan Hi again, it's been a while, but the question evolved as you could see when you follow the links in subsequent questions...2015-05-21

1 Answers 1

0

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.

  • 0
    for a more worked-out answer, see [here](http://math.stackexchange.com/a/177699/19341)...2012-08-02