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?
Solution 1:
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.
Solution 2:
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} $$
Solution 3:
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.
Solution 4:
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.