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