Computing Tutte Polynomials of a graph $C_{k,n}$

Question

We let $k,n$ be integers with $k<n$ and let $C_{k,n}$ be the graph on $n$ vertices with vertex $i$ connected to vertices $i-k,...,i-1,i+1,..,i+k$ modulo $n$. The question I am asked is to compute $T_{C_{k,n}}(x,y)$, the Tutte polynomial of $C_{k,n}$.

It's easy to see that for $k \geq \lfloor n/2 \rfloor$ that $C_{k,n}$ is just the complete graph on $n$ vertices.So we need only consider $k<n/2$.

For $k=1$, we just have the $n$-cycle graph. Using the TG-invariance of the Tutte polynomial it's easy to see that

$$ T_{C_{1,n}}(x,y)=T_{C_{1,n}-\lbrace 1,2 \rbrace}(x,y)+T_{C_{1,n-1}}(x,y)$$

and we can inductively compute that

$$ T_{C_{1,n}}(x,y) = y+x+x^2+...x^{n-1} = \frac{x^n-1}{x-1}+y -1 $$

However, even trying to compute this polynomial for $k=2$ seems to be quite challenging: I established some horrible kind of recurrence of the form:

$$ \begin{split} T_{C_{2,n}} & = 2(y+1)T_{C_{2,n-1}}+(2+y)T_{G_{n-1}} \\ T_{G_{n-1}}&=(1+y)T_{G_{n-2}}+T_{H_{n-2}} \\ T_{H_{n-2}}&=T_{G_{n-2}}+yT_{G_{n-3}}+..+y^{n-5}T_{G_{4}}+T_{H_{3}}\\ T_{H_{2}}& = x+y \\ T_{G_2}&=x\end{split} $$

I was trying to use a kind of deletion-contraction argument and then TG-invariance to come up with a kind of recurrence relation. I looked up the paper of Pak where he deduces a recurrence relation for the Tutte polynomial of a complete graph. My general feeling is that this homework question may have been set at a very high level.

Any comments or advice would be appreciated.

Answer 1

I have no idea, but I can use Mathematica to verify some results for small $n,k$

Here is the Mathematica code.

yourGraph[n_, k_] := CirculantGraph[n, Range[1, k]]
Table[{"(n,k)=(" <> ToString@n <> "," <> ToString@k <> ")", 
    TuttePolynomial[yourGraph[n, k], {x, y}]}, {n, 20, 20}, {k, 
    Floor[n/2], Floor[n/2]}] // Flatten[#, 1] & // MatrixForm

$$ \left( \begin{array}{cc} \text{(n,k)=(2,1)} & x \\ \text{(n,k)=(3,1)} & x^2+x+y \\ \text{(n,k)=(4,1)} & x^3+x^2+x+y \\ \text{(n,k)=(4,2)} & x^3+3 x^2+4 x y+2 x+y^3+3 y^2+2 y \\ \text{(n,k)=(5,1)} & x^4+x^3+x^2+x+y \\ \text{(n,k)=(5,2)} & x^4+6 x^3+10 x^2 y+11 x^2+5 x y^3+15 x y^2+20 x y+6 x+y^6+4 y^5+10 y^4+15 y^3+15 y^2+6 y \\ \text{(n,k)=(6,1)} & x^5+x^4+x^3+x^2+x+y \\ \text{(n,k)=(6,2)} & x^5+7 x^4+8 x^3 y+20 x^3+12 x^2 y^2+39 x^2 y+25 x^2+6 x y^4+24 x y^3+52 x y^2+46 x y+11 x+y^7+5 y^6+15 y^5+29 y^4+40 y^3+32 y^2+11 y \\ \text{(n,k)=(6,3)} & x^5+10 x^4+20 x^3 y+35 x^3+15 x^2 y^3+45 x^2 y^2+90 x^2 y+50 x^2+6 x y^6+24 x y^5+60 x y^4+105 x y^3+145 x y^2+106 x y+24 x+y^{10}+5 y^9+15 y^8+35 y^7+64 y^6+96 y^5+120 y^4+120 y^3+80 y^2+24 y \\ \text{(n,k)=(7,1)} & x^6+x^5+x^4+x^3+x^2+x+y \\ \text{(n,k)=(7,2)} & x^6+8 x^5+7 x^4 y+29 x^4+7 x^3 y^2+49 x^3 y+57 x^3+14 x^2 y^3+70 x^2 y^2+119 x^2 y+57 x^2+7 x y^5+35 x y^4+98 x y^3+147 x y^2+105 x y+22 x+y^8+6 y^7+21 y^6+49 y^5+84 y^4+98 y^3+70 y^2+22 y \\ \text{(n,k)=(7,3)} & x^6+15 x^5+35 x^4 y+85 x^4+35 x^3 y^3+105 x^3 y^2+280 x^3 y+225 x^3+21 x^2 y^6+84 x^2 y^5+210 x^2 y^4+420 x^2 y^3+700 x^2 y^2+721 x^2 y+274 x^2+7 x y^{10}+35 x y^9+105 x y^8+245 x y^7+469 x y^6+756 x y^5+1085 x y^4+1330 x y^3+1225 x y^2+644 x y+120 x+y^{15}+6 y^{14}+21 y^{13}+56 y^{12}+126 y^{11}+245 y^{10}+420 y^9+645 y^8+895 y^7+1120 y^6+1260 y^5+1225 y^4+945 y^3+490 y^2+120 y \\ \end{array} \right) $$