# Returning Paths on Cubic Graphs Without Backtracking

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?

-
– draks ... Aug 1 '12 at 22:05
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

Chris Godsil's beautiful answer is marred, I believe, by errors in the last two lines. Since numerous other posts refer to that answer and since there seems to be some reluctance to modify it, while at the same time there still seems to be some confusion/disagreement about what the correct result is, I have written this community wiki answer in order to place what I believe to be a corrected version of Chris's answer on the record. If this correction is in error, I hope that people will downvote it mercilessly; if it is valid, I hope that some form of the corrections will be incorporated into the original post so that this answer can be deleted.

Here is Chris's answer, with correction appended:

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 initial conditions $p_1=t$ and $p_2=t^2-3$. Note that the recurrence does not hold when $r=1$ since $tp_1(t)-2p_0(t)=t^2-2$ is not equal to $p_2(t)=t^2-3$. The function $q_r(t)=2^{-r/2}p_r(2^{3/2}t)$ satisfies the recurrence of the Chebyshev polynomials, $$q_{r+1}(t)=2tq_r(t)-q_{r-1}(t)$$ with initial conditions \begin{aligned} q_1(t)&=2t=U_1(t)=U_1(t)-\frac{1}{2}U_{-1}(t),\\ q_2(t)&=4t^2-\frac{3}{2}=4t^2-1-\frac{1}{2}=U_2(t)-\frac{1}{2}U_0(t). \end{aligned} Here $U_r(t)$ are the Chebyshev polynomials of the second kind, which satisfy the initial conditions \begin{aligned} U_0(t)&=1,\\ U_1(t)&=2t, \end{aligned} and the further relations \begin{aligned} U_{-1}(t)&=0,\\ U_2(t)&=4t^2-1, \end{aligned} as implied by the recurrence. Since the recurrence is linear, we conclude that $$q_r(t)=\begin{cases}1 & \text{if r=0,}\\ U_r(t)-\frac{1}{2}U_{r-2}(t) & \text{if r\ge1.}\end{cases}$$ From this it follows that $$p_r(t)=\begin{cases}1 & \text{if r=0,}\\ 2^{r/2}U_r(t/2^{3/2})-2^{(r-2)/2}U_{r-2}(t/2^{3/2}) & \text{if r\ge1.}\end{cases}$$

-

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.

-
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
"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$." As an expression you give earlier in your post implies, $p_2(t)=t^2-3$. This is not consistent with the recurrence. It needn't be since the recurrence derives from the expression you give for $r\ge3$. But it does mean that $p_0=1$ and $p_1=t$ can't be used as initial conditions. Instead you need to use $p_1=t$ and $p_2=t^2-3$. As a consequence, $p_0$ needs to be separately defined to be $1$. – Will Orrick May 10 '15 at 18:54
A second consequence is that $p_r(t)$ is not related to Chebyshev polynomials in quite the way that you say. There are two issues here. One is that your recurrence is related to the Chebyshev recurrence by a change of variable, but not the one stated in your post or the one stated in the comments. From $$p_{r+1}(t)=tp_r(t)-2p_{r-1}(t)$$ you get $$p_{r+1}(2^{3/2}t)=2^{3/2}tp_r(2^{3/2}t)-2p_{r-1}(2^{3/2}t)$$ and therefore $$2^{-(r+1)/2}p_{r+1}(2^{3/2}t)=2t\cdot2^{-r/2}p_r(2^{3/2}t)-2^{-(r-1)/2}p_{r-1}‌​(2^{3/2}t).$$ Hence $q_r(t):=2^{-r/2}p_r(2^{3/2}t)$ satisfies the Chebyshev recurrence. – Will Orrick May 10 '15 at 19:09
The second issue is that $q_r(t)$ is neither the Chebyshev polynomial of the first kind nor the Chebyshev polynomial of the second kind because it satisfies different initial conditions than either. Observe that $q_0(t)=1$, $q_1(t)=2t$, $q_2(t)=4t^2-3/2$. If $q_2(t)$ satisfied the Chebyshev recurrence it would equal $4t^2-1$ and $q_r(t)$ would equal the Chebyshev polynomial of the second kind, $U_r(t)$. Instead, one can verify that $q_r(t)=U_r(t)-\frac{1}{2}U_{r-2}(t)$ for $r\ge1$, where we take $U_{-1}(t)=0$, which is compatible... – Will Orrick May 10 '15 at 19:37
... with the recurrence. From this we get $$p_r(t)=2^{r/2}U_r(t/2^{3/2})-2^{(r-2)/2}U_{r-2}(t/2^{3/2})$$ for $r\ge1$. – Will Orrick May 10 '15 at 19:37

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.

-
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

As in Chris Godsil's answer, I will use $A$ to denote the adjacency matrix and $\Delta$ to denote the diagonal matrix of vertex degrees.

A pretty standard inclusion-exclusion approach can be formulated as follows. Define $P(a,b,n,\{j_1,\ldots,j_k\})$ to be the set of paths from $a$ to $b$ of length $n$ in which each of steps $j_1,\ \ldots,\ j_k\in\{2,3,\ldots,n\}$ reverses the preceding step. Then the number of paths of length $n$ with no reversals is $$\lvert P(a,b,n,\{\})\rvert-\sum_{j=2}^n\lvert P(a,b,n,\{j\})\rvert+\sum_{2\le j<k\le n}\lvert P(a,b,n,\{j,k\})\rvert-\sum_{2\le j<k<\ell\le n}\lvert P(a,b,n,\{j,k,\ell\})\rvert+\ldots$$

The task now is to compute $\lvert P(a,b,n,\{j_1,\ldots,j_k\})\rvert$ for general $\{j_1,\ldots,j_k\}$. We know that $\lvert P(a,b,n,\{\})\rvert$ is the $(a,b)$ element of $A^n$. Since a reversal in step $j$ implies that the same vertex is visited after the $(j-2)^\text{nd}$ and $j^\text{th}$ steps, $\lvert P(a,b,n,\{j\})\rvert$ is the $(a,b)$ element of $A^{j-2}\Delta A^{n-j}=A^{j-2}(3I)A^{n-j}=3A^{n-2}$.

Things get harder when there are multiple reversals. Consider the set of paths with $k-1$ consecutive reversals, $k\ge2$, starting in step $j$, $$P(a,b,n,\{j,j+1,j+2,\ldots,j+k-2\}).$$ If $v_i$ is the vertex visited after the $i^\text{th}$ step then $v_{j-2}=v_j=v_{j+2}=v_{j+4}=\ldots$ (call this the even sequence) and $v_{j-1}=v_{j+1}=v_{j+3}=v_{j+5}=\ldots$ (call this the odd sequence). In the case that $k$ is even, the vertex visited after the final reversal, $v_{j+k-2}$, is in the even sequence. This situation is similar to the $k=2$ situation analyzed in the previous paragraph and the number of paths is the $(a,b)$ element of $$A^{j-2}\Delta A^{n-(k-2)-j}=A^{j-2}(3I)A^{n-(k-2)-j}=3A^{n-k}.$$ If $k$ is odd, then $v_{j+k-2}$ is in the odd sequence and the number of $k$-step paths joining $v_{j-2}$ to $v_{j+k-2}$ is the same as the number of one-step paths joining $v_{j-2}$ to $v_{j-1}$, that is, it is given by the adjacency matrix. Hence the number of $n$-step paths joining $a$ to $b$ is the $(a,b)$ element of $$A^{j-2}AA^{n-(k-2)-j}=A^{n-k+1}.$$

In the most general case we have to handle sets of paths having multiple sequences of consecutive reversals. A set of reversals containing multiple sequences can be reduced to the lengths of the sequences. So, for example, if $n=10$ and the set of reversals is $\{2,3,4,6,9,10\}$, then this set can be represented as the sum $4+2+1+3$ since

• in steps $1$, $2$, $3$, $4$, step $2$ reverses $1$, $3$ reverses $2$, and $4$ reverses $3$;
• in steps $5$, $6$, step $6$ reverses $5$;
• no subsequent step reverses step $7$;
• in steps $8$, $9$, $10$, step $9$ reverses $7$ and $10$ reverses $9$.

A second example: the set of reversals $\{3,6,7,8\}$ is represented by the sum $1+2+1+4+1+1$ (again with $n=10$). The set with no reversals is represented by the sum $1+1+\ldots+1$ ($n$ terms). Since each reversal added to the set merges two terms in the sum, a set of $r$ reversals is represented by a sum of $n-r$ terms.

We now see what needs to be done to compute $$\sum_{2\le j_1<\ldots<j_r\le n}\lvert P(a,b,n,\{j_1,\ldots,j_r\})\rvert.$$ Represent each set $\{j_1,\ldots,j_r\}$ by a sum of positive integers totaling $n$. The number of length $n$ paths from $a$ to $b$ corresponding to that set equals the $(a,b)$ element of the product $3^eA^o$, where $e$ is the number of even terms in the sum and $o$ is the number of odd terms in the sum. Examples: the length $10$ paths with reversals $\{2,3,4,6,9,10\}$ are enumerated by $(3I)(3I)AA$; those with reversals $\{3,6,7,8\}$ are enumerated by $A(3I)A(3I)AA$.

It remains to enumerate sums of $n-r$ positive terms totaling $n$. The answer is a binomial coefficient, but we need to enumerate our sums according to the numbers of even and odd terms. Here's where things get messy. Make the definitions \begin{aligned} \mathcal{E}&:=\text{sum of even terms,}\\ \mathcal{J}&:=\frac{1}{2}\mathcal{E},\\ \mathcal{O}&:=n-2\mathcal{J}=\text{sum of odd terms.} \end{aligned} Note that the parity of the sum of the odd terms is the parity of the number of odd terms. Hence $\mathcal{O}-o$ is even and we define $$\mathcal{K}:=\frac{\mathcal{O}-o}{2},$$ which is the sum of the numbers obtained by subtracting $1$ from each of the odd terms and then halving. This implies \begin{aligned} o&=\mathcal{O}-2\mathcal{K}=n-2\mathcal{J}-2\mathcal{K}\\ e&=n-r-o=2\mathcal{J}+2\mathcal{K}-r. \end{aligned} Since $\mathcal{J}$ is the sum of $e$ positive terms, $e\le\mathcal{J}$ and therefore $\mathcal{K}\le(r-\mathcal{J})/2$.

Now by a standard stars-and-bars argument, the number of sums of $e$ positive even numbers totaling $\mathcal{E}$ is $$\binom{(\mathcal{J}-e)+(e-1)}{\mathcal{J}-e}=\binom{\mathcal{J}-1}{r-\mathcal{J}-2\mathcal{K}}.$$ The number of sums of $o$ positive odd numbers totaling $\mathcal{O}$ is $$\binom{\mathcal{K}+(o-1)}{\mathcal{K}}=\binom{n-2\mathcal{J}-\mathcal{K}-1}{\mathcal{K}}.$$ In forming the full sum, the even and odd terms may be interleaved in $$\binom{o+e}{o}=\binom{n-r}{n-2\mathcal{J}-2\mathcal{K}}$$ ways.

Incorporating these results in the inclusion-exclusion sum gives the result that the number of length $n$ paths from $a$ to $b$ with no reversing steps is the $(a,b)$ element of $$\sum_{r=0}^{n-1}(-1)^r\sum_{\mathcal{J}=0}^{\lfloor n/2\rfloor}\sum_{\mathcal{K}=0}^{\lfloor(r-\mathcal{J})/2\rfloor}3^{2\mathcal{J}+2\mathcal{K}-r}A^{n-2\mathcal{J}-\mathcal{K}}\binom{\mathcal{J}-1}{r-\mathcal{J}-2\mathcal{K}}\binom{n-2\mathcal{J}-\mathcal{K}-1}{\mathcal{K}}\binom{n-r}{n-2\mathcal{J}-2\mathcal{K}}.$$

Discussion: This answer is not so nice as the answers that have been given by Chris Godsil and Ross Millikan, but I wanted to see how things would work using a contrasting method. As in the method used here, Chris Godsil's answer uses inclusion-exclusion. It does so by building the set of length $n$ paths with no reversing steps by extending a set of shorter paths from which reversing steps have already been excluded. The resulting formula involving Chebyshev polynomials can be expressed in terms of relatively simple single sums, as discussed in a followup post. In contrast, my method produces a somewhat unpleasant triple sum. The main reason I can see for the simplicity of Chris Godsil's answer is that in none of the terms of the inclusion-exclusion sum do you have reversing steps that "interact", that is, that are consecutive, whereas in my solution this does happen and must be dealt with.

Addendum: In my answer to the followup post (scroll down to see the new answer), I derive the sum you get from Chris Godsil's answer using the principle of inclusion-exclusion nonrecursively. Instead of the sets $P(a,b,n,\{j\})$, I start with sets of a slightly different definition, chosen so that sets that have consecutive labeled reversing steps, such as $P(a,b,n,\{j,j+1\})$, are empty. The simple single-sum form of the answer then falls out naturally.

-
Hi. I just updated another question of mine. Would be glad if you could have look. Cheers... – draks ... May 18 '15 at 21:57
What do you mean by "it must be possible to understand Chris Godsil's answer nonrecursively"? – draks ... May 18 '15 at 22:35
@draks...: in Chris Godsil's recurrence, paths with a reversing step are eliminated for length $2$ by the $-\Delta$ term. This is an inclusion-exclusion argument. Inclusion-exclusion is then applied repeatedly, every time the length of the path is increased by $1$, when $(\Delta-I)p_{n-1}(A)$ gets subtracted from $Ap_n(A)$ to produce $p_{n+1}(A)$. By "nonrecursive", I mean an argument that applies inclusion-exclusion to the set of all paths of length $n$, rather than to a set obtained by extending shorter paths from which reversing steps have already been eliminated. – Will Orrick May 19 '15 at 11:31
@draks...: I feel that I have now largely done this to my own satisfaction. See my revised answer to your other post. If it's not clear, please let me know so I can try to improve the presentation. – Will Orrick May 19 '15 at 11:33