Take the 2-minute tour ×
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.

I was once interested in the returning paths on cubic graphs . But I'm even more curious to have the number of ways without backtracking, which means doing one step forward and than one back (which might be good for dancing), e.g. $1\to 2\to 1$ .

The solution with the powers of the adjacency matrix doesn't seem to work here. Does anybody know a solution?

share|improve this question
    
    
oh, linking in bounty's text doesn't seems to work: What is the combinatorical interpretation of this relation? –  draks ... Nov 27 '13 at 21:34
add comment

2 Answers

up vote 4 down vote accepted
+50

Call a walk reduced if it does not backtrack. If $A=A(X)$ for a graph $X$, define $p_r(A)$ to be the matrix (of the same order as $A$) such that $(p_r(A)_{u,v})$ is the number of reduced walks in $X$ from $u$ to $v$. Observe that $$ p_0(A)=I,\quad p_1(A) =A,\quad p_2(A) = A^2-\Delta, $$ where $\Delta$ is the diagonal matrix of valencies of $X$. If $r\ge3$ we have the recurrence $$ Ap_r(A) = p_{r+1}(A) +(\Delta-I) p_{r-1}(A). $$ These calculations were first carried out by Norman Biggs, who observed the implication that $p_r(A)$ is a polynomial in $A$ and $\Delta$, of degree $r$ in $A$.

If $X$ is cubic, $\Delta=3I$ and we want the polynomials $p_r(t)$ satisfying the recurrence $$ p_{r+1}(t) = tp_r(t)-2p_{r-1}(t). $$ with $p_0=1$ and $p_1=t$. If my calculation are correct, then $2^{-r/2}p_r(t/\sqrt{2})$ is a Chebyshev polynomial.

share|improve this answer
    
Wow, cool thing. How does this relate to Ross' answer? Doesn't look like your solution needs directed graphs at all... –  draks ... Aug 2 '12 at 7:41
    
You may view a non-backtracking walk as a sequence of ordered pairs $(x,y)$, where $x$ and $y$ are adjacent vertices (and consecutive pairs overlap in the obvious way). This is then a walk on a directed graph (the line digraph of $X$). But you may also view it as simply a non-backtracking walk, with no directions. You have a choice. –  Chris Godsil Aug 2 '12 at 13:27
    
Do you have the Norman Biggs reference for $Ap_r(A) = p_{r+1}(A) +(\Delta-I) p_{r-1}(A)$ or can you sketch the proof? I hope I don't ask for too much, I can also go with your current result. –  draks ... Aug 2 '12 at 13:34
    
Your question is not a duplicate of the one you linked to. The entries of $p_r(A)$ can be computed in polynomial time. As for a proof, the idea is to consider the $ij$-entry of $Ap_r(A)$; this counts reduced walks of length $r+1$, plus some stuff we do not want. The latter stuff is counted by the second term, which effectively counts counts walks of length $r+1$ that backtrack once, at the very end. –  Chris Godsil Aug 3 '12 at 13:32
    
I don't think it's a Chebyshev, I get $t^3-4t$ for $p_3(t)$, which, substitued and scaled, doesn't match $T_3(x)=4x^3-3x$. I might also be wrong, so can you prove it? –  draks ... Dec 23 '12 at 23:17
show 3 more comments

You can do it with an adjacency matrix, but the states are now combinations of the node and where you came from. Aside from the starting vertex, for a cubic graph there are three times as many. There is one extra for the starting vertex as you didn't come from anywhere for the start. The number of length $n$ paths back to start is the sum of the three different states that represent start in the $n^{\text{th}}$ power of this matrix.

Added: If your cubic graph is $K_4$ with nodes 1,2,3,4 and you start at 1, your states are $1(start), 1 (came from 2), \ldots 2(came from 1), 2(came from 3),\ldots 4(came from 3)$ for a total of $13$ of them. You calculate an adjacency matrix as usual. Each state will have three outgoing edges and (except for the start one) three or four incoming edges. You can then take powers of it to find the number of paths to any state. If you want paths coming back to $1$ of length $n$, you add the 1 (came from 2), 1 (came from 3), and 1 (came from 4) values in the $n^{\text{th}}$ power of the adjacency matrix.

share|improve this answer
    
Thanks again. $13$ because $n\cdot (n-1)+1$, right? Is there a kind of tensor prodcut structure? –  draks ... Aug 1 '12 at 20:46
    
@draks : Yes about the 13. There are 4 vertices. As it is a cubic graph, each one can be arrived at from 3 other places, plus the one you start at, which has no restriction on the first move. I don't know about a tensor structure. –  Ross Millikan Aug 1 '12 at 20:50
    
I tried, but I can't get at it. What does $1(start)$ mean? Is it on the diagonal? Does $(camefromX)$ imply a direction? Do I have to deal with directed graphs? I would be ever so happy, if you could post an explicte example. Sorry for bothering you again... –  draks ... Aug 1 '12 at 21:06
    
If you are at 1, without the restriction of no backtracking, you can go to 2,3, or 4. With the restriction, if the last step was from 2 to 1, you can only go to 3 or 4. This makes it a different state from being at 1 having come from 3. 1(start) means the start of the path, when you didn't come from anywhere and can go to 2,3, or 4. Yes, it is a directed graph-I hadn't noticed that before. –  Ross Millikan Aug 1 '12 at 21:14
add comment

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.