WALK POLYNOMIAL: A New Graph Invariant

A walk between two vertices u and v of G is finite alternating sequence u = v₀, e₁, v₁, e₂, v₂, e₃, v₃, …, e_k, v_k = v of vertices and edges of G such that the edge e_i joins the vertices v_i–1 and v_i.

[1] If A is the adjacency matrix of simple graph G, then the entrya_ij ∈ A^k is the number of different walks of length k between the vertices i and j.

The walk polynomial in variable x of a simple connected graph G is defined as

W(G,x)=12∑k=1d(G)(∑aij∈Akaij−tr(Ak))xk,$$\begin{array}{} \displaystyle \mathscr{W}(G,x) =\frac{1}{2}\sum_{k=1}^{d(G)}\big(\sum_{a_{ij}\in A^{k}}a_{ij}-tr(A^{k})\big)x^{k}, \end{array}$$

where A is the adjacency matrix of G.

The walk polynomial of the complete bipartite graphK_m,n, m ≥ 2, n ≥ 1, is 𝓦 (K_m,n) = mnx¹ + mn2(m+n−2)x2.$\begin{array}{} \displaystyle \frac{mn}{2}(m+n-2)x^{2}. \end{array}$

Since the diameter of K_m,n is 2, we need only two matrices, the adjacency matrix A and its square matrix A². In order to give the total number of walks of lengths 1 and 2, we first give the general forms of A and A². The (m + n) × (m + n) adjacency matrix corresponding to K_m,n is

A=Om,mJm,nJm,nTOn,n,$$\begin{array}{} \displaystyle A=\left( \begin{array}{cc} O_{m,m} & J_{m,n} \\ J_{m,n}^{T} & O_{n,n} \\ \end{array} \right), \end{array}$$

where O and J are respectively matrices of zeros and ones. It is better to see the adjacency matrix of the bipartite graph k_2,4:

A=001111001111110000110000110000110000$$\begin{array}{} \displaystyle A=\left( \begin{array}{cccccc} 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ \end{array} \right) \end{array}$$

Since the upper triangular part of the adjacency matrix A is the matrix J_m,n, the sum of entries of this matrix is mn. Thus the number of all walks of length 1 in J_m,n is w₁ = mn. Similarly, the general form of A² is

A2=nJm,mOm,nOm,nTmJn,n,$$\begin{array}{} \displaystyle A^{2}=\left( \begin{array}{cc} nJ_{m,m} & O_{m,n} \\ O_{m,n}^{T} & mJ_{n,n} \\ \end{array} \right), \end{array}$$

where n(J_m,m) represents the multiplication of J with the number n. The following is the second power of the adjacency matrix of the bipartite graph k_2,4.

A2=440000440000002222002222002222002222$$\begin{array}{} \displaystyle A^2=\left( \begin{array}{cccccc} 4 & 4 & 0 & 0 & 0 & 0 \\ 4 & 4 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 2 & 2 & 2 \\ 0 & 0 & 2 & 2 & 2 & 2 \\ 0 & 0 & 2 & 2 & 2 & 2 \\ 0 & 0 & 2 & 2 & 2 & 2 \\ \end{array} \right) \end{array}$$

The number w₂ of walks of length 2 in K_m,n is w2=12$\begin{array}{} \displaystyle w_{2}=\frac{1}{2} \end{array}$ [the sum of entries of, nJm,m−tr(nJm,m)]+12$\begin{array}{} \displaystyle nJ_{m,m}-tr(nJ_{m,m})]+\frac{1}{2} \end{array}$ [the sum of entries of mJ_n,n–tr(mJn,n)]=12[n(m2)−n(m)]+12[m(n2)−m(n)]=mn2[m+n−2].$\begin{array}{} \displaystyle (mJ_{n,n})]=\frac{1}{2}[n(m^{2})-n(m)]+\frac{1}{2}[m(n^{2})-m(n)]=\frac{mn}{2}[m+n-2]. \end{array}$ This completes the proof. □

Let S_n represent the star graph. ThenW(Sn)=(n−1)x1+12(n2−3n+2)x2.$\begin{array}{} \displaystyle \mathscr{W}(S_{n})=(n-1) x^{1}+\frac{1}{2}(n^{2}-3n+2)x^{2}. \end{array}$

Since the diameter of S_n is 2, we need only two matrices, the adjacency matrix A and its square matrix A², each of order n × n:

A=O1,1J1,n−1J1,n−1TOn−1,n−1,$$\begin{array}{} \displaystyle A=\left( \begin{array}{cc} O_{1,1} & J_{1,n-1} \\ J_{1,n-1}^{T} & O_{n-1,n-1} \\ \end{array} \right), \end{array}$$

where O and J are matrices of zeros and ones, respectively. You can see the adjacency matrix of S₇:

A=0111111100000010000001000000100000010000001000000$$\begin{array}{} \displaystyle A=\left( \begin{array}{ccccccc} 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right) \end{array}$$

Since the upper triangular part of the adjacency matrix A is the matrix J_1,n–1, the sum of entries of this matrix is n–1. Thus the number of all walks of length 1 in J_1,n–1 is w₁ = n–1. Similarly, the general form of A² is

A2=(n−1)J1,1O1,n−1O1,n−1TJn−1,n−1,$$\begin{array}{} \displaystyle A^{2}=\left( \begin{array}{cc} (n-1)J_{1,1} & O_{1,n-1} \\ O_{1,n-1}^{T} & J_{n-1,n-1} \\ \end{array} \right), \end{array}$$

where n(J_1,1) represents the multiplication of J_1,1 with the number n–1. The following is the second power of the adjacency matrix of S₇.

A2=6000000011111101111110111111011111101111110111111$$\begin{array}{} \displaystyle A^2=\left( \begin{array}{ccccccc} 6 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \right) \end{array}$$

Note that the walks of length 2 the contribution comes only from the matric J_n–1,n–1, and in this case the sum of all entries of this matrix is (n–1)². Now the number of walks of length 2 in S_n is

w2=12[the sum of entries ofJn−1,n−1−tr(Jn−1,n−1)]=12[(n−1)2−(n−1)]=12[n2−3n+2],$$\begin{array}{} \displaystyle w_{2} &=& \frac{1}{2}[\,\mbox{the sum of entries of}\,\, J_{n-1,n-1}-tr(J_{n-1,n-1})] \\ \displaystyle &=& \frac{1}{2}[(n-1)^{2}-(n-1)] \\ \displaystyle &=& \frac{1}{2}[n^{2}-3n+2], \end{array}$$

and the proof is finished.

The walk polynomial of wheel graph is 𝓦(W_n) = (2n–2)x¹ + 1/2(n² + 3n–4)x²for n ≥ 3 with 2n–2 edges and n vertices.

Here, again, the diameter of the wheel graph is 2. So, again, we need just two matrices, the adjacency matrix A and its square A². The adjacency matrix corresponding to W_n is A = (a_ij), where

aij=0,i=j1,i=1orj=11,j=i+1ori=j+11,i=2,j=nandi=n,j=20,otherwise.$$\begin{array}{} \displaystyle a_{ij}=\left\{ \begin{array}{lll} 0,& i=j \\ 1,& i=1 \,\,\mbox{or}\,\, j=1 \\ 1,&j=i+1 \,\,\mbox{or}\,\, i=j+1 \\ 1,&i=2,j=n \,\,\mbox{and}\,\, i=n,j=2 \\ 0,&\mbox{otherwise}. \\ \end{array} \right. \end{array}$$

For better understanding, please the following adjacency matrix of W₇.

A=0111111101000111010001010100100101010001011100010$$\begin{array}{} \displaystyle A=\left( \begin{array}{ccccccc} 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ \end{array} \right) \end{array}$$

You can see that there are three types of entries where nonzero entries appear; the nonzero entries are actually 1s. The first type of entries appear at positions where either i = 1 or j = 1, and their count is 2(n–1); The second type of entries appear at positions where either i = j + 1 or j = 1 + 1, and their count is 2((n–1)–1); The third type of entries appear at positions where either i = 2, j = n or i = n, j = 2, and their count is 2. You may observe that all the entries of main diagonal are 0. So, the number of all distinct walks of length 1 in W_n is w1=12(2(n−1))+2((n−1)−1))+2=2(n−1).$\begin{array}{} \displaystyle w_{1}=\frac{1}{2}(2(n-1))+2((n-1)-1))+2=2(n-1). \end{array}$ The upper triangular entries of A² = (b_ij) are

bij=1,j=i+1,i=2,…,n−11,i=2,j=n2,j=i+2,i=2,…,n−22,i=2,j=n−12,i=3,j=n−12,i=1,j=2,…,n1,j=i+3,…,i+(n−4),2≤i≤n−3,i+n−4≤n$$\begin{array}{} \displaystyle b_{ij}=\left\{ \begin{array}{lll} 1,& j=i+1,i=2,\ldots,n-1 \\ 1,& i=2,j=n \\ 2,& j=i+2,i=2,\ldots,n-2 \\ 2,& i=2,j=n-1 \\ 2,& i=3,j=n-1 \\ 2,& i=1,j=2,\ldots,n \\ 1,& j=i+3,\ldots,i+(n-4), 2\leq i \leq n-3, i+n-4\leq n \\ \end{array} \right. \end{array}$$

The following is A² of W₇.

A2=6222222231212121312122213121212131222121312121213$$\begin{array}{} \displaystyle A^2=\left( \begin{array}{ccccccc} 6 & 2 & 2 & 2 & 2 & 2 & 2 \\ 2 & 3 & 1 & 2 & 1 & 2 & 1 \\ 2 & 1 & 3 & 1 & 2 & 1 & 2 \\ 2 & 2 & 1 & 3 & 1 & 2 & 1 \\ 2 & 1 & 2 & 1 & 3 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 3 & 1 \\ 2 & 1 & 2 & 1 & 2 & 1 & 3 \\ \end{array} \right) \end{array}$$

Now we give the sum of all the entries: and the first type of entries are all 1s and appear at the positions where j = i + 1, and their count is (n–2). The second type of entries are all 1s and appear at the positions where i = 2, j = n, and their count is 1. The third type of entries are all 2s and appear at the positions where j = i + 2, i = 2 and their count is (n–3); The fourth type of entries are all 2s and appear at the positions wherei = 2, j = n–1, and their count is 1; the fifth type of entries are all 2s and appear at the positions where i = 3, j = n–1, and their count is 1; the sixth type of entry is are all 2s and appear at the positions where i = 1, j = 2, …, n, and their count is (n–1); the seventh type of entries are all 1s and appear at the positions where j = i + 3, …, i + (n–4), 2 ≤ i ≤ n–3, i + n–4 ≤ n, and their count is ∑4n−3(n−i).$\begin{array}{} \sum_{4}^{n-3}(n-i). \end{array}$. You may observe that all the entries are of upper triangular entries. So, the number of all distinct walks of length 2 in W_n is w2=((n−2)+1+(n−3)+1+1+(n−1)+∑4n−3(n−i))=12(n2+3n−4)$\begin{array}{} w_{2}=((n-2)+1+(n-3)+1+1+(n-1)+\sum_{4}^{n-3}(n-i))=\frac{1}{2}(n^2+3n-4) \end{array}$

The walk polynomial of the gear graphG_n, n ≥ 6, is

W(Gn)=3nx1+(n2+7n2)x2+(3n2+12n)x3+(n3+15n2+24n2)x4.$$\begin{array}{} \displaystyle \mathscr{W}(G_{n})=3nx^{1}+(\frac{n^{2}+7n}{2})x^{2}+(3n^{2}+12n)x^{3}+(\frac{n^{3}+15n^{2}+24n}{2})x^{4}. \end{array}$$

Since the diameter of the gear graph is 4, we need four matrices, A, A², A³, and A⁴.

Walks of lengths 1: Since only the upper-triangular entries contribute towards the walk polynomial, we give only the nonzero upper-triangular entries of the (2n + 1) × (2n + 1) adjacency matrix A = (a_ij) of G_n:

aij=1,i=1,…,2n−1,j=i+11,i=1,j=2n1,i=odd,i<2n+1,j=2n+10,otherwise.$$\begin{array}{} \displaystyle a_{ij}=\left\{ \begin{array}{lll} 1,& i=1,\ldots,2n-1, j=i+1 \\ 1,& i=1,j=2n \\ 1,& i=odd, i\lt2n+1,j=2n+1 \\ 0,&\mbox{otherwise}. \\ \end{array} \right. \end{array}$$

Let us have a look at the adjacency matrix of G₇:

A=010000000000011101000000000000010100000000001001010000000000000101000000001000010100000000000001010000001000000101000000000000010100001000000001010000000000000101001000000000010100000000000001011100000000000100101010101010100$$\begin{array}{} \displaystyle A=\left( \begin{array}{ccccccccccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ \end{array} \right) \end{array}$$

You can see that there are three types of entries where nonzero entries appear; the nonzero entries are actually 1s. The first type of entries appear at positions where i = 1, …, 2n–1 and j = i + 1, and so their count is 2n–1; the second type of entries appear at positions where i = 1 and j = 2n, and so their count is 1; the third type of entries appear at positions where i is odd and is less than 2n + 1 and j = 2n + 1, and so their count is n. So, the number of all distinct walks of length 1 in G_n is w₁ = ((2n–1) + 1 + n) = (3n).

Walks of lengths 2: Now we find walks of lengths 2. The upper triangular entries of A² = (b_ij) are

bij=2,i=odd,1≤i≤(2n−3),j=i+21,i=even,2≤i≤(2n−2),j=i+22,i=even,2≤i≤(2n),j=2n+11,i=odd,1≤i≤(2n−5),j=i+41,i=odd,1≤i≤(2n−7),j=i+61,i=odd,1≤i≤3,j=i+82,i=1,j=2n−11,i=2,j=2n$$\begin{array}{} \displaystyle b_{ij}=\left\{ \begin{array}{lll} 2,& i=odd,1\leq i\leq (2n-3),j=i+2 \\ 1,& i=even,2\leq i\leq (2n-2),j=i+2 \\ 2,& i=even,2\leq i\leq (2n),j=2n+1 \\ 1,& i=odd,1\leq i\leq (2n-5),j=i+4 \\ 1,& i=odd,1\leq i\leq (2n-7),j=i+6 \\ 1,& i=odd,1\leq i\leq 3,j=i+8 \\ 2,& i=1,j=2n-1 \\ 1,& i=2,j=2n \\ \end{array} \right. \end{array}$$

For better understanding you may have a look at the walks of lengths 2 in the matrix A² of G₇.

A2=302010101010200020100000000012203020101010100010201000000002102030201010100000102010000002101020302010100000001020100002101010203020100000000010201002101010102030200000000000102012201010101020300010000000001022020202020202027$$\begin{array}{} \displaystyle A^{2}=\left( \begin{array}{ccccccccccccccc} 3 & 0 & 2 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 2 & 0 & 0 \\ 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 \\ 2 & 0 & 3 & 0 & 2 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \\ 1 & 0 & 2 & 0 & 3 & 0 & 2 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \\ 1 & 0 & 1 & 0 & 2 & 0 & 3 & 0 & 2 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 2 \\ 1 & 0 & 1 & 0 & 1 & 0 & 2 & 0 & 3 & 0 & 2 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 0 & 2 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 2 & 0 & 3 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 \\ 2 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 2 & 0 & 3 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 \\ 0 & 2 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 2 & 7 \\ \end{array} \right) \end{array}$$

Now we give the sum of all these entries. The first type of entries are all 2s and appear at positions where i is odd and 1 ≤ i ≤ (2n–3), j = i + 2, and their count is (n–1). the second type of entries are all 1s and appear at positions where i is even and 2 ≤ i ≤ (2n–2) and j = i + 2, and their count is (n–1); the third type of entries are all 2s and appear at positions where i is even and 2 ≤ i ≤ (2n) and j = 2n + 1, and their count is n; the fourth type of entries are all 1s and appear at positions where i is odd and 1 ≤ i ≤ (2n–5) and j = i + 4, and their count is n–2; the fifth type of entry is are all 1s and appear at positions where i is odd and 1 ≤ i ≤ (2n–7) and j = i + 6, and their count is (n–3); the sixth type of entries are all 1s and appear at positions where i is odd and 1 ≤ i ≤ 3 and j = i + 8, and their count is (n–4); the seventh type of entries are all 2s and appear at positions where i = 1, j = 2n–1, and their count is 1. The eighth type of entries are all 1s and appear at positions where i = 2, j = 2n, and their count is 1. So, the number of all distinct walks of length 2 is w2=n2+7n2.$\begin{array}{} \displaystyle w_{2}=\frac{n^2+7n}{2}. \end{array}$

Walks of lengths 3: In order to find walks of length 3, we need upper triangular entries of the matrix A³:

cij=5,1≤i≤(2n−1),j=i+13,1≤i≤3,j=i+(2n−3)3,1≤i≤2n−3,j=i+32,1≤i≤2n−5,j=i+52,1≤i≤2n−7,,j=i+75,i=1,j=n−1n+4,iis odd,1≤i<2n+1,j=2n+1$$\begin{array}{} \displaystyle c_{ij}=\left\{ \begin{array}{lll} 5,& 1\leq i\leq (2n-1),j=i+1 \\ 3,& 1\leq i\leq 3,j=i+(2n-3) \\ 3,& 1\leq i\leq 2n-3,j=i+3\\ 2,& 1\leq i\leq 2n-5,j=i+5 \\ 2,& 1\leq i\leq 2n-7,,j=i+7 \\ 5,& i=1,j=n-1 \\ n+4,& i\,\, \mbox{is odd}, 1\leq i \lt2n+1, j=2n+1 \\ \end{array} \right. \end{array}$$

The following is the matrix A³ of G₇.

A3=05030202020305115050302020203000505030202020311305050302020200030505030202021120305050302020002030505030202112020305050302000202030505030211202020305050300020202030505031130202020305050003020202030505115030202020305001101101101101101101100$$\begin{array}{} \displaystyle A^3=\left( \begin{array}{ccccccccccccccc} 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 11 \\ 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 0 \\ 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 11 \\ 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 0 \\ 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 11 \\ 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 0 \\ 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 2 & 11 \\ 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 0 & 0 \\ 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 2 & 11 \\ 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 0 & 0 \\ 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 3 & 11 \\ 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 0 & 0 \\ 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 5 & 11 \\ 5 & 0 & 3 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 3 & 0 & 5 & 0 & 0 \\ 11 & 0 & 11 & 0 & 11 & 0 & 11 & 0 & 11 & 0 & 11 & 0 & 11 & 0 & 0 \\ \end{array} \right) \end{array}$$

Now we give the sum of all entries of above diagonals. The first type of entries are 2s. These entries appear in n–4 secondary diagonals, and the entries appear as follows:

cij=2,1≤i≤2n−5,j=i+52,1≤i≤2n−7,j=i+7⋮⋮2,1≤i≤5,j=i+(2n−5)$$\begin{array}{} \displaystyle c_{ij}=\left\{ \begin{array}{lll} 2,& 1\leq i\leq 2n-5,j=i+5 \\ 2,& 1\leq i\leq 2n-7,j=i+7\\ \vdots & \vdots \\ 2,& 1\leq i\leq 5,j=i+(2n-5) \end{array} \right. \end{array}$$

Since the number of 2s appearing at these positions is n(n–4), their sum is 2n(n–4).

The second type of entries are 5s. These numbers appear on secondary diagonal with 1 ≤ i ≤ 2n–1 and j = i + 1, and their count is 2n–1. Moreover, one 5 appears at the position where i = 1, j = 2n. Since the total number of 5s is 2n, their sum is 10n.

The third type of entries are 3s. These entries appear only in 2 secondary diagonals, and their positions are:

cij=3,1≤i≤3,j=i+(2n−3)3,1≤i≤2n−3,j=i+3$$\begin{array}{} \displaystyle c_{ij}=\left\{ \begin{array}{lll} 3,& 1\leq i\leq 3,j=i+(2n-3) \\ 3,& 1\leq i\leq 2n-3,j=i+3\\ \end{array} \right. \end{array}$$

Since the total number of 3s is 2n, their sum is 6n.

The fourth type of entries are n + 4s and appear at positions where i is odd and 1 ≤ i < 2n + 1 and j = 2n + 1. Since their count is n, the sum of these numbers is n(n + 4).

Finally, the number of all distinct walks of length 3 in W_n is 2n(n–4) + 10n + 6n + n(n + 4) = 3n(n + 4).

Walks of lengths 4: Now we go for distinct walks of length 4 by giving upper triangular entries of the matrix A⁴ = (d_ij). You may observe that these entries will form secondary diagonals, which are divided into three types:

Type I.

dij=n+12,i=odd,1≤i≤(2n−3),j=i+28,i=even,2≤i≤(2n−2),j=i+2n+9,i=odd,1≤i≤(2n−5),j=i+45,i=even,2≤i≤(2n−4),j=i+4n+8,i=odd,1≤i≤(2n−7),j=i+64,i=even,2≤i≤(2n−6),j=i+60,otherwise$$\begin{array}{} \displaystyle d_{ij}=\left\{ \begin{array}{lll} n+12,& i=odd,1\leq i\leq (2n-3),j=i+2 \\ 8,& i=even,2\leq i\leq (2n-2),j=i+2 \\ n+9,& i=odd,1\leq i\leq (2n-5),j=i+4 \\ 5,& i=even,2\leq i\leq (2n-4),j=i+4 \\ n+8,& i=odd,1\leq i\leq (2n-7),j=i+6 \\ 4,& i=even,2\leq i\leq (2n-6),j=i+6 \\ 0,& otherwise \\ \end{array} \right. \end{array}$$

Type II. The last two nonzero secondary diagonals are:

dij=n+12,i=1,j=2n−18,i=2,j=2nn+9,i=1,j=2n−35,i=2,j=2n−2n+9,i=3,j=2n−15,i=4,j=2n$$\begin{array}{} \displaystyle d_{ij}=\left\{ \begin{array}{lll} n+12,& i=1,j=2n-1 \\ 8,& i=2,j=2n \\ n+9,& i=1,j=2n-3 \\ 5,& i=2,j=2n-2 \\ n+9,& i=3,j=2n-1 \\ 5,& i=4,j=2n \\ \end{array} \right. \end{array}$$

Type III. There are n–5 secondary diagonals such that the first entry of each of these diagonals is n + 8. In the following m denotes the number of such diagonals, i.e., 1 ≤ m ≤ n–5.

dij=n+8,i=odd,1≤i≤2(n−m)−5,j=2(m+2)+i4,i=even,1≤i≤2(n−m−2),j=2(m+2)+i$$\begin{array}{} \displaystyle d_{ij}=\left\{ \begin{array}{lll} n+8,& i=odd,1\leq i\leq 2(n-m)-5,j=2(m+2)+i \\ 4,& i=even,1\leq i\leq 2(n-m-2),j=2(m+2)+i \\ \end{array} \right. \end{array}$$

The entries which are not covered yet are the entries of the last column of A⁴:

dij=2n+8,i=even,2≤i≤2n,j=2n+1$$\begin{array}{} \displaystyle d_{ij}=\left\{ \begin{array}{lll} 2n+8,& i=even,2\leq i\leq 2n,j=2n+1 \\ \end{array} \right. \end{array}$$

The following is the matrix A⁴ of G₇.

A4=21019016015015016019000100805040405082219021019016015015016000801008050404052216019021019016015015000508010080504042215016019021019016015000405080100805042215015016019021019016000404050801008052216015015016019021019000504040508010082219016015015016019021000805040405080102202202202202202202202277$$\begin{array}{} \displaystyle A^4=\left( \begin{array}{ccccccccccccccc} 21 & 0 & 19 & 0 & 16 & 0 & 15 & 0 & 15 & 0 & 16 & 0 & 19 & 0 & 0 \\ 0 & 10 & 0 & 8 & 0 & 5 & 0 & 4 & 0 & 4 & 0 & 5 & 0 & 8 & 22 \\ 19 & 0 & 21 & 0 & 19 & 0 & 16 & 0 & 15 & 0 & 15 & 0 & 16 & 0 & 0 \\ 0 & 8 & 0 & 10 & 0 & 8 & 0 & 5 & 0 & 4 & 0 & 4 & 0 & 5 & 22 \\ 16 & 0 & 19 & 0 & 21 & 0 & 19 & 0 & 16 & 0 & 15 & 0 & 15 & 0 & 0 \\ 0 & 5 & 0 & 8 & 0 & 10 & 0 & 8 & 0 & 5 & 0 & 4 & 0 & 4 & 22 \\ 15 & 0 & 16 & 0 & 19 & 0 & 21 & 0 & 19 & 0 & 16 & 0 & 15 & 0 & 0 \\ 0 & 4 & 0 & 5 & 0 & 8 & 0 & 10 & 0 & 8 & 0 & 5 & 0 & 4 & 22 \\ 15 & 0 & 15 & 0 & 16 & 0 & 19 & 0 & 21 & 0 & 19 & 0 & 16 & 0 & 0 \\ 0 & 4 & 0 & 4 & 0 & 5 & 0 & 8 & 0 & 10 & 0 & 8 & 0 & 5 & 22 \\ 16 & 0 & 15 & 0 & 15 & 0 & 16 & 0 & 19 & 0 & 21 & 0 & 19 & 0 & 0 \\ 0 & 5 & 0 & 4 & 0 & 4 & 0 & 5 & 0 & 8 & 0 & 10 & 0 & 8 & 22 \\ 19 & 0 & 16 & 0 & 15 & 0 & 15 & 0 & 16 & 0 & 19 & 0 & 21 & 0 & 0 \\ 0 & 8 & 0 & 5 & 0 & 4 & 0 & 4 & 0 & 5 & 0 & 8 & 0 & 10 & 22 \\ 0 & 22 & 0 & 22 & 0 & 22 & 0 & 22 & 0 & 22 & 0 & 22 & 0 & 22 & 77 \\ \end{array} \right) \end{array}$$

Now we give the sum of all these upper-triangular entries. There are four diagonals that appear once in the matrix. The entries of the first such diagonal are n + 12 and 8 and each of these appear n–1 times, and so there sum is (n–1)(n + 12) + 8(n–1). The entries of the second such diagonal are n + 9 and 5 and each of these appear n–2 times, and so there sum is (n–2)(n + 9) + 5(n–2). The entries of the third such diagonal are n + 9 and 5 and each of these appear 2 times, and so there sum is 2n + 28. The entries of the fourth such diagonal are n + 12 and 8 and each of these appears 1 time, and so there sum is n + 20.

Now we find the sum of those n–5 diagonals whose entries are same but appear with different number of times. Each such diagonal has two types of entries, n + 8 and 4. The largest of these diagonals contains n–3 entries of value n + 8, the next contains n–4 entries of value n + 8, and so on the last such diagonal contains 3 entries. Thus the sum of all these entries is

Sum1=(n−<!-- - -->3)(n+8)+(n−<!-- - -->4)(n+8)+⋯<!-- ? -->+(3)(n+8)=(n+8)[(n−<!-- - -->3)+(n−<!-- - -->4)+⋯<!-- ? -->+3]=n2(n+8)(n−<!-- - -->5).$$\begin{array}{} \displaystyle Sum_{1} \!\!\!\!\!&= (n-3)(n+8)+ (n-4)(n+8)+\cdots + (3)(n+8)\\ \displaystyle &= (n+8)[(n-3)+(n-4)+\cdots + 3]\\ \displaystyle &= \frac{n}{2}(n+8)(n-5). \end{array}$$

Similarly, since 4 appears the same number of times the n + 8 appears, their sum is Sum₂ = 2n(n–5).

Since the entries 2n + 8 in the last column appear n times, their sum is n(2n + 8).

Finally, the sum of all upper-triangular entries of A⁴ is

w4=[(n−<!-- - -->1)(n+12)+8(n−<!-- - -->1)]+[(n−<!-- - -->2)(n+9)+5(n−<!-- - -->2)]+[2n+28]+[n+20]+n2(n+8)(n−<!-- - -->5)+2n(n−<!-- - -->5)+n(2n+8)=12[n3+15n2+24n].$$\begin{array}{} w_{4} \!\!\!\!\!&=\displaystyle \big[(n-1)(n+12)+8(n-1)\big]+\big[(n-2)(n+9)+5(n-2)\big]\\ &\displaystyle\quad+\big[2n+28\big]+\big[n+20\big]+\frac{n}{2}(n+8)(n-5)+2n(n-5)+n(2n+8)\\ &\displaystyle= \frac{1}{2}[n^{3}+15n^{2}+24n]. \end{array}$$

The walk polynomial of the Jahangir graphJ_2,m, m ≥ 6, is

W(J2,m)=3mx1+(m2+7m2)x2+(3m2+12m)x3+(m3+15m2+24m2)x4.$$\begin{array}{} \displaystyle \mathscr{W}(J_{2,m})=3mx^{1}+(\frac{m^{2}+7m}{2})x^{2}+(3m^{2}+12m)x^{3}+(\frac{m^{3}+15m^{2}+24m}{2})x^{4}. \end{array}$$

Just substitute m for n in the walk polynomial of the gear graph G_n.