Cube Polynomial

Author

Eric W. Weisstein
March 25, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/CubePolynomial.nb.

For more information, see Eric's MathWorld entry https://mathworld.wolfram.com/CubePolynomial.html.

©2026 Wolfram Research, Inc. except for portions noted otherwise

Parametrized families

<<MathWorld`Graphs`

Alkane

(poly=Table[GraphData[{"Alkane",n},"CubePolynomial"],{n,10}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],x]

AlternatingGroupGraph

(poly=Table[GraphData[{"AlternatingGroupGraph",n},"CubePolynomial"],{n,2,6}]/.f_Function:>f[x])//Column

Andasfai

(poly=Table[GraphData[{"Andrasfai",n},"CubePolynomial"],{n,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],{x,x^2},Factor]

Antiprism

Entity["Graph",{"Antiprism",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Expand@Table[GraphData[{"Antiprism",n},"CubePolynomial"],{n,k0=3,25}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>4],{x,x^2}]

Apollonian

(poly=Table[GraphData[{"Apollonian",n},"CubePolynomial"],{n,6}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Collect[FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0],x,Factor]

Barbell

(poly=Factor@Table[GraphData[{"Barbell",n},"CubePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>2],{x,x^2},Factor]

Bishop n×n

(poly=Factor@Table[GraphData[{"Bishop",{n,n}},"CubePolynomial"],{n,k0=1,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

BlackBishop n×n

(poly=Factor@Table[GraphData[{"BlackBishop",{n,n}},"CubePolynomial"],{n,k0=1,20}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

coef=FindLinearRecurrence[poly]

poly=Expand@LinearRecurrence[{3,-1,-5,5,1,-3,1},{1,2+x,5+6 x,8+14 x+3 (x^2),13+32 x+9 (x^2),18+55 x+25 (x^2),25+94 x+51 (x^2)},30];//Timing

Take[poly,20]

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Yes. Since the `(n,n)` black bishop graph is isomorphic to the white bishop graph unless both board dimensions are odd, the even-`n` case is identical to the white-bishop formula, and only the odd case changes. Also, as with the white-bishop case, the cube polynomial has no terms above `x^2`. ([MathWorld][1])

```wl
BlackBishopCubePolynomial[n_, x_] :=
	Piecewise[
		{
			{
				n^2/2
				+ n (n - 1) (2 n - 1)/6 x
				+ n (n - 2) (n - 1)^2/24 x^2,
				Mod[n, 2] == 0
			},
			{
				(n^2 + 1)/2
				+ (n - 1) (2 n^2 - n + 3)/6 x
				+ (n - 3) (n - 1) (n^2 + 2)/24 x^2,
				Mod[n, 2] == 1
			}
		}
	]
```

This gives, for example,

* `n = 2`: `2 + x`
* `n = 3`: `5 + 6 x`
* `n = 4`: `8 + 14 x + 3 x^2`
* `n = 5`: `13 + 32 x + 9 x^2`
* `n = 7`: `25 + 94 x + 51 x^2`
* `n = 9`: `41 + 208 x + 166 x^2`

which is the parity-complementary partner to the white-bishop formula.

[1]: https://mathworld.wolfram.com/BlackBishopGraph.html?utm_source=chatgpt.com "Black Bishop Graph -- from Wolfram MathWorld"

Book

(poly=Table[GraphData[{"Book",n},"CubePolynomial"],{n,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Bruhat

(poly=Table[GraphData[{"Bruhat",n},"CubePolynomial"],{n,6}]/.f_Function:>f[x])//Column

CoefficientList[poly,x]

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Cameron

(poly=Table[GraphData[{"Cameron",n},"CubePolynomial"],{n,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

FindLinearRecurrence[DeleteMissing@poly]

Camel n×n

(poly=Table[GraphData[{"Camel",{n,n}},"CubePolynomial"],{n,20}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Centipede

(poly=Factor@Table[GraphData[{"Centipede",n},"CubePolynomial"],{n,k0=1,kmax=10}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],x]

CocktailParty

(poly=Table[GraphData[{"CocktailParty",n},"CubePolynomial"],{n,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],{x,x^2},Factor]

Complete

Entity["Graph",{"Complete",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Complete",n},"CubePolynomial"],{n,k0=1,kmax=30}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

n+Binomial[n,2]x

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["CubePolynomial"]/.f_Function:>f[x]

DeleteCases[
Sort@Flatten[Table[{
{"CompleteBipartite",{m,n}},
GraphData[{"CompleteBipartite",{m,n}},"CubePolynomial"]/.f_Function:>f[x],
m+n+m n x+Binomial[m,2]Binomial[n,2](x^2)
},{n,10},{m,n}],1],
{_,x_,x_}]

FullSimplify[m+n+m n x+Binomial[m,2]Binomial[n,2](x^2)/.x->1]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"CompleteBipartite",{n,n}},"CubePolynomial"],{n,15}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],{x,x^2,x^3},Factor]

2n+(n^2)x+((Binomial[n,2])^2)(x^2)

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["CubePolynomial"]/.f_Function:>f[x]

DeleteCases[
Sort@Flatten[Table[{
{"CompleteTripartite",{k,m,n}},
GraphData[{"CompleteTripartite",{k,m,n}},"CubePolynomial"]/.f_Function:>f[x],
k+m+n+(k m+k n+m n)x+(Binomial[k,2]Binomial[m,2]+Binomial[k,2]Binomial[n,2]+Binomial[m,2]Binomial[n,2])(x^2)
},{n,10},{m,n},{k,m}],2],
{_,x_,x_}]

FullSimplify[k+m+n+(k m+k n+m n)x+(Binomial[k,2]Binomial[m,2]+Binomial[k,2]Binomial[n,2]+Binomial[m,2]Binomial[n,2])(x^2)]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Factor@Table[GraphData[{"CompleteTripartite",{n,n,n}},"CubePolynomial"],{n,k0=1,10}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],{x,x^2},Factor]

Collect[3(n+n^2 x+Binomial[n,2]^2x^2),{x,x^2},Factor]

FullSimplify[3 n+3 (n^2) x+(3/4) (((-1+n))^2) (n^2) (x^2)/.x->1]//Factor

CompleteTripartiteMinusPerfectMatching

(poly=Table[GraphData[{"CompleteTripartiteMinusPerfectMatching",{2n,2n,2n}},"CubePolynomial"],{n,10}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[poly,z,ValidationLength->2]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],{x,x^2,x^3},Factor]

CrossedPrism

(poly=Table[GraphData[{"CrossedPrism",n},"CubePolynomial"],{n,4,24,2}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Crown

(poly=Table[GraphData[{"Crown",n},"CubePolynomial"],{n,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],{x,x^2,x^3},Factor]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"CubeConnectedCycle",n},"CubePolynomial"],{n,3,8}]/.f_Function:>f[x])//Column

Entity["Graph",{"CubeConnectedCycle",n}]["VertexCount"]

Entity["Graph",{"CubeConnectedCycle",n}]["EdgeCount"]

Table[Piecewise[{{64+96 x+16 (x^2),n==4}},2^n n+3 (2^(n-1)) n x],{n,3,9}]//Column

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Do[Print[{n,CubePolynomial[CubeConnectedCycleGraph[n],x]//Timing}],{n,3,9}]

Cycle

Entity["Graph",{"Cycle",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Cycle",n},"CubePolynomial"],{n,3,30}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

SeriesCoefficient[gf,{z,0,n}]

CycleComplement

(poly=Factor@Table[GraphData[{"CycleComplement",n},"CubePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>2]

DiagonalIntersection

(poly=Factor@Table[GraphData[{"DiagonalIntersection",n},"CubePolynomial"],{n,k0=3,14}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Dipyramid

(poly=Factor@Table[GraphData[{"Dipyramid",n},"CubePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>2]

DorogovtsevGoltsevMendes

(poly=Factor@Table[GraphData[{"DorogovtsevGoltsevMendes",n},"CubePolynomial"],{n,k0=0,7}]/.f_Function:>f[x])//Column

gf=FindGeneratingFunction[DeleteMissing@poly,z]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

DoubleCone

(poly=Factor@Table[GraphData[{"DoubleCone",n},"CubePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])//Column

gf=((z )^3)FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>2]

Empty

Entity["Graph",{"Empty",n}]["CubePolynomial"]/.f_Function:>f[x]

poly=Factor@Table[GraphData[{"Empty",n},"CubePolynomial"],{n,k0=1,30}]/.f_Function:>f[x]

FibonacciCube

A128100

(poly=Factor@Table[GraphData[{"FibonacciCube",n},"CubePolynomial"],{n,k0=1,15}]/.f_Function:>f[x])//Column

CoefficientList[DeleteMissing@poly,x]

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

CoefficientList[FullSimplify@Expand@Table[(((2^(-n)) ((((1-(Sqrt[5+4 x])))^(n-1)) (-3-2 x+(Sqrt[5+4 x]))+(((1+(Sqrt[5+4 x])))^(n-1)) (3+2 x+(Sqrt[5+4 x]))))/(Sqrt[5+4 x])),{n,0,10}],x]

poly=Join[{1,1},DeleteMissing@poly]

coef=FindLinearRecurrence[poly]

CoefficientList[LinearRecurrence[{1,x+1},{1,1},20],x]//Flatten

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>=0]

CoefficientList[Table[(((2^(-n)) (-(((1-(Sqrt[5+4 x])))^n)+(((1+(Sqrt[5+4 x])))^n)))/(Sqrt[5+4 x])),{n,10}],x]//Flatten

CoefficientList[Table[(((2^(-n)) ((((1+(Sqrt[5+4 x])))^n)-(((1-(Sqrt[5+4 x])))^n)))/(Sqrt[5+4 x])),{n,10}],x]//Flatten

Fiveleaper n×n

(poly=Factor@Table[GraphData[{"Fiveleaper",{n,n}},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Table[n^2
+(6 n^2-38 n+48) x
+(15 n^2-190 n+553) x^2
+(20 n^2-380 n+1732) x^3
+(15 n^2-380 n+2358) x^4
+4 (n-16) (n-15) x^5,{n,20}]//Expand//Column

I would treat the tail quadratics as the current closed-form conjecture from the data, with the edge term proved from the move definition. The next useful step is to derive a2,a3,a4,a5 combinatorially from the actual cube-shape types in the infinite fiveleaper graph.

Yes: there should be `a6` terms.

For Wolfram's fiveleaper graph, the allowed moves are the distance-5 moves
`(+/-5,0)`, `(0,+/-5)`, `(+/-3,+/-4)`, and `(+/-4,+/-3)`. In other words, it is the Euclidean distance-5 graph on the grid. ([MathWorld][1])

I checked the infinite move graph directly. There is an induced `Q_6`, for example with step vectors

```wl
{{5,0},{0,5},{3,4},{3,-4},{4,3},{4,-3}}
```

Taking all subset sums of those 6 vectors gives 64 distinct vertices, and two such vertices are adjacent exactly when they differ by one of those 6 step vectors. So the infinite fiveleaper graph contains an induced 6-cube.

I also checked all 7-subsets of the 12 possible move vectors, and none produce an induced `Q_7`. So for the infinite fiveleaper graph, the maximum cube dimension is 6.

Therefore, for `n x n` fiveleaper graphs:

* `a6[n]` does eventually become nonzero.
* There should never be any terms above `x^6`.

A concrete `Q_6` already fits in a `20 x 20` box, and among the 6-cube configurations I checked, that is the smallest bounding box. So the first nonzero `a6[n]` should occur at

```wl
n = 20
```

and for all `n >= 20` you should expect an `x^6` term.

So the answer is:

```wl
degree CubePolynomial[GraphData[{"Fiveleaper",{n,n}}],x] <= 6
```

for all `n`, and equality should first occur at `n = 20`.

If you want, I can next work out an explicit closed form or at least the first several values of `a6[n]`.

[1]: https://mathworld.wolfram.com/FiveleaperGraph.html?utm_source=chatgpt.com "Fiveleaper Graph -- from Wolfram MathWorld"

Yes. The new `x^6` term is exactly the missing piece.

In fact, it leads to a very clean exact formula for all `n`, not just a tail fit. The right way to write it is as a `Max[...]` sum over the finitely many cube footprints.

```wl
FiveleaperCubePolynomial[n_, x_] :=
	Module[{t},
		t[k_] := Max[n - k, 0];

		n^2
		+ (2 n t[5] + 4 t[3] t[4]) x
		+ (t[5]^2 + 2 t[6] t[8] + 4 t[7]^2 + 4 t[4] t[8] + 4 t[3] t[9]) x^2
		+ (4 t[8] t[9] + 4 t[10] t[11] + 2 t[8] t[11] + 8 t[7] t[12] + 2 t[6] t[13]) x^3
		+ (t[14]^2 + 2 t[11] t[13] + 4 t[12]^2 + 4 t[11] t[15] + 4 t[10] t[16]) x^4
		+ (4 t[15] t[16] + 2 t[14] t[19]) x^5
		+ t[19]^2 x^6
	]
```

This reproduces your values exactly for `n = 1..20`, including

* `n = 17`: `289 + 1136 x + 1658 x^2 + 1052 x^3 + 233 x^4 + 8 x^5`
* `n = 20`: `400 + 1688 x + 2753 x^2 + 2132 x^3 + 758 x^4 + 92 x^5 + x^6`

So yes, the new term does help a lot:

* it confirms the degree is exactly `6`
* and it gives the top coefficient
  `a6[n] = Max[n - 19, 0]^2`

The `x^5` coefficient also becomes clear from the same footprint classification:

* `a5[n] = 4 Max[n - 15, 0] Max[n - 16, 0] + 2 Max[n - 14, 0] Max[n - 19, 0]`

For the stable range `n >= 20`, this simplifies to

```wl
n^2
+ (6 n^2 - 38 n + 48) x
+ (15 n^2 - 190 n + 553) x^2
+ (20 n^2 - 380 n + 1732) x^3
+ (15 n^2 - 380 n + 2358) x^4
+ (6 n^2 - 190 n + 1492) x^5
+ (n - 19)^2 x^6
```

So the answer is: yes, and it essentially completes the closed form.

Yes: there is never an `x^7` term.

More precisely, for Wolfram's `Fiveleaper` graph,

```wl
Exponent[CubePolynomial[GraphData[{"Fiveleaper",{n,n}}], x], x] <= 6
```

for all `n`, and equality first occurs at `n = 20`.

Reason:

* Any induced cube in the finite `n x n` board also occurs in the infinite fiveleaper move graph on `Z^2`.
* So it is enough to determine the maximum induced-cube dimension in the infinite graph.
* For the fiveleaper move set

  ```wl
  {{5,0},{-5,0},{0,5},{0,-5},{3,4},{3,-4},{-3,4},{-3,-4},{4,3},{4,-3},{-4,3},{-4,-3}}
  ```

  there is an induced `Q_6`, for example using

  ```wl
  {{-5,0},{0,-5},{-3,4},{-3,-4},{-4,3},{-4,-3}}
  ```
* But no 7-subset of those 12 possible edge directions gives an induced `Q_7`.

So the maximum cube dimension is exactly 6, hence no `x^7` term can ever appear.

So the answer is simply:

```wl
a7[n] = 0
```

for all `n`.

The fact that your `n = 20` value has coefficient `1` on `x^6` is consistent with this: that is the first board large enough to contain a single minimal `Q_6` footprint.

If you want, I can next rewrite the full fiveleaper formula in a cleaned-up final WL definition with `a0` through `a6` separated out.

FiveleaperCubePolynomial[n_,x_]:=Module[{t},t[k_]:=Max[n-k,0];(n^2)+(2 n t[5]+4 t[3] t[4]) x+(((t[5])^2)+2 t[6] t[8]+4 ((t[7])^2)+4 t[4] t[8]+4 t[3] t[9]) (x^2)+(4 t[8] t[9]+4 t[10] t[11]+2 t[8] t[11]+8 t[7] t[12]+2 t[6] t[13]) (x^3)+(((t[14])^2)+2 t[11] t[13]+4 ((t[12])^2)+4 t[11] t[15]+4 t[10] t[16]) (x^4)+(4 t[15] t[16]+2 t[14] t[19]) (x^5)+((t[19])^2) (x^6)]

Table[FiveleaperCubePolynomial[n,x],{n,21}]//Column

FiveleaperCubePolynomial[n_,x_]:=n^2+(2 n Max[n-5,0]+4 Max[n-3,0] Max[n-4,0]) x+(Max[n-5,0]^2+2 Max[n-6,0] Max[n-8,0]+4 Max[n-7,0]^2+4 Max[n-4,0] Max[n-8,0]+4 Max[n-3,0] Max[n-9,0]) x^2+(4 Max[n-8,0] Max[n-9,0]+4 Max[n-10,0] Max[n-11,0]+2 Max[n-8,0] Max[n-11,0]+8 Max[n-7,0] Max[n-12,0]+2 Max[n-6,0] Max[n-13,0]) x^3+(Max[n-14,0]^2+2 Max[n-11,0] Max[n-13,0]+4 Max[n-12,0]^2+4 Max[n-11,0] Max[n-15,0]+4 Max[n-10,0] Max[n-16,0]) x^4+(4 Max[n-15,0] Max[n-16,0]+2 Max[n-14,0] Max[n-19,0]) x^5+Max[n-19,0]^2 x^6

Table[FiveleaperCubePolynomial[n,x],{n,21}]//Column

FiveleaperCubePolynomial[n_,x_]:=Module[{a1,a2,a3,a4,a5,a6},a1=Piecewise[{{0,n<=4}},6 n^2-38 n+48];
a2=Piecewise[{{0,n<=5},{1,n==6},{4,n==7},{13,n==8}},15 n^2-190 n+553];
a3=Piecewise[{{0,n<=9},{8,n==10},{24,n==11},{64,n==12}},20 n^2-380 n+1732];
a4=Piecewise[{{0,n<=12},{4,n==13},{22,n==14},{53,n==15}},15 n^2-380 n+2358];
a5=Piecewise[{{0,n<=16},{8,n==17},{24,n==18}},6 n^2-190 n+1492];
a6=Piecewise[{{0,n<=19}},(n-19)^2];
n^2+a1 x+a2 x^2+a3 x^3+a4 x^4+a5 x^5+a6 x^6]

FiveleaperCubePolynomial[n_,x_]:=(n^2)+(2 n Ramp[n-5]+4 Ramp[n-3] Ramp[n-4]) x+(((Ramp[n-5])^2)+2 Ramp[n-6] Ramp[n-8]+4 ((Ramp[n-7])^2)+4 Ramp[n-4] Ramp[n-8]+4 Ramp[n-3] Ramp[n-9]) (x^2)+(4 Ramp[n-8] Ramp[n-9]+4 Ramp[n-10] Ramp[n-11]+2 Ramp[n-8] Ramp[n-11]+8 Ramp[n-7] Ramp[n-12]+2 Ramp[n-6] Ramp[n-13]) (x^3)+(((Ramp[n-14])^2)+2 Ramp[n-11] Ramp[n-13]+4 ((Ramp[n-12])^2)+4 Ramp[n-11] Ramp[n-15]+4 Ramp[n-10] Ramp[n-16]) (x^4)+(4 Ramp[n-15] Ramp[n-16]+2 Ramp[n-14] Ramp[n-19]) (x^5)+((Ramp[n-19])^2) (x^6)

Table[FiveleaperCubePolynomial[n,x],{n,21}]//Column

Flower

(poly=Table[GraphData[{"Flower",n},"CubePolynomial"],{n,5,20}]/.f_Function:>f[x])//Column

gf=z^5FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>=5]

FoldedCube

(poly=Factor@Table[GraphData[{"FoldedCube",n},"CubePolynomial"],{n,k0=2,10}]/.f_Function:>f[x])//Column

CoefficientList[DeleteMissing@poly,x]

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Expand@Table[((x+2)^n-2 n x^(n-1)-x^n)/2+KroneckerDelta[n,2] x+24 KroneckerDelta[n,4] x^2,{n,2,10}]//Column

Yes. In the Wolfram/GraphData convention, the exact cube polynomial for the folded cube family is

C_n(x) =
((x + 2)^n - 2 n x^(n - 1) - x^n)/2

* KroneckerDelta[n, 2] x
* 24 KroneckerDelta[n, 4] x^2.

Equivalently, piecewise,

* C_2(x) = 2 + x
* C_4(x) = 8 + 16 x + 36 x^2
* for n = 3 and all n >= 5,
  C_n(x) = Sum[2^(n-k-1) Binomial[n, k] x^k, {k, 0, n - 2}]
  = ((x + 2)^n - 2 n x^(n - 1) - x^n)/2.

This matches your data:
4 + 6 x,
8 + 16 x + 36 x^2,
16 + 40 x + 40 x^2 + 20 x^3,
32 + 96 x + 120 x^2 + 80 x^3 + 30 x^4, etc. The small exceptional cases are consistent with the standard special identifications FoldedCube[2] = P_2, FoldedCube[3] = K_4, and FoldedCube[4] = K_{4,4}. ([MathWorld][1])

A clean way to see the general formula is to use the Cayley-model description. After choosing one representative from each antipodal pair, FoldedCube[n] can be viewed on Z_2^(n-1) with generating set

S_n = {e_1, ..., e_(n-1), u},
u = e_1 + ... + e_(n-1).

This is the folded-hypercube Cayley description, just shifted by one in the dimension/index compared with some graph-theory papers. ([MathWorld][1])

Now fix n >= 5. An induced Q_k through 0 is determined by its k neighbors of 0 inside that cube, hence by a k-subset T of S_n. For k <= n - 2, the only linear dependence among the n generators in S_n is the full sum of all n of them, so no generator outside T lies in span(T). Therefore the induced subgraph on each coset of span(T) is exactly a Q_k. Conversely, every induced Q_k arises this way. There are Binomial[n, k] choices of T, and each gives 2^(n-1-k) cosets, so

a_k = 2^(n-k-1) Binomial[n, k),    0 <= k <= n - 2.

For k = n - 1, the omitted generator does lie in the span, so extra edges appear and the result is not an induced Q_(n-1). That is why the polynomial stops at degree n - 2. The n = 4 case is exceptional because K_{4,4} has many more induced 4-cycles than those coming from this affine-subcube construction. ([MathWorld][1])

A nice side observation is that for n >= 5 these coefficients are exactly half the numbers of k-faces of Q_n, since Q_n has 2^(n-k) Binomial[n, k] k-subcubes. Folding identifies antipodal faces in pairs. 

In WL:

```wl
FoldedCubeCubePolynomial[n_, x_] :=
	((x + 2)^n - 2 n x^(n - 1) - x^n)/2 +
	KroneckerDelta[n, 2] x +
	24 KroneckerDelta[n, 4] x^2
```

This reproduces exactly the values in your list.

[1]: https://mathworld.wolfram.com/FoldedCubeGraph.html "Folded Cube Graph -- from Wolfram MathWorld"

Gear

(poly=Table[GraphData[{"Gear",n},"CubePolynomial"],{n,3,20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>2],x^Range[0,2],Factor]

Giraffe n×n

(poly=Table[GraphData[{"Giraffe",{n,n}},"CubePolynomial"],{n,20}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Yes. Since the giraffe graph is the `(1,4)`-leaper graph, the same kind of `Max[...]` formula as for the zebra case works exactly. ([MathWorld][1])

An exact WL formula matching your values is

```wl
GiraffeCubePolynomial[n_, x_] :=
	n^2
	+ 4 Max[n - 1, 0] Max[n - 4, 0] x
	+ (2 Max[n - 2, 0] Max[n - 8, 0] + 4 Max[n - 5, 0]^2) x^2
	+ 4 Max[n - 6, 0] Max[n - 9, 0] x^3
	+ Max[n - 10, 0]^2 x^4
```

This reproduces exactly

* `n = 5`: `25 + 16 x`
* `n = 6`: `36 + 40 x + 4 x^2`
* `n = 10`: `100 + 216 x + 132 x^2 + 16 x^3`
* `n = 11`: `121 + 280 x + 198 x^2 + 40 x^3 + x^4`
* `n = 20`: `400 + 1216 x + 1332 x^2 + 616 x^3 + 100 x^4`

There are no terms above `x^4`; geometrically this comes from the four independent giraffe move directions `(+/-1,+/-4)` and `(+/-4,+/-1)`. ([MathWorld][1])

If you want the expanded tail once all terms are present, for `n >= 11` this is

```wl
n^2
+ (4 n^2 - 20 n + 16) x
+ (6 n^2 - 60 n + 132) x^2
+ (4 n^2 - 60 n + 216) x^3
+ (n^2 - 20 n + 100) x^4
```

equivalently,

```wl
GiraffeCubePolynomialExpanded[n_, x_] :=
	n^2
	+ (4 n^2 - 20 n + 16) x
	+ (6 n^2 - 60 n + 132) x^2
	+ 4 (n - 6) (n - 9) x^3
	+ (n - 10)^2 x^4
```

[1]: https://mathworld.wolfram.com/GiraffeGraph.html?utm_source=chatgpt.com "Giraffe Graph -- from Wolfram MathWorld"

GiraffeCubePolynomial[n_,x_]:=(n^2)+4 Max[n-1,0] Max[n-4,0] x+(2 Max[n-2,0] Max[n-8,0]+4 ((Max[n-5,0])^2)) (x^2)+4 Max[n-6,0] Max[n-9,0] (x^3)+((Max[n-10,0])^2) (x^4)

Table[GiraffeCubePolynomial[n,x],{n,20}]//Column

Goldberg

(poly=Table[GraphData[{"Goldberg",n},"CubePolynomial"],{n,3,20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>=3]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Grid",{n,n}},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Collect[%,x^Range[0,2],Factor]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["CubePolynomial"]/.f_Function:>f[x]

(m+(m-1) x) (n+(n-1) x)

m n+(2 m n-m-n) x+(m-1) (n-1) x^2

DeleteCases[
Sort@Flatten[Table[{
{"Grid",{m,n}},
GraphData[{"Grid",{m,n}},"CubePolynomial"]/.f_Function:>f[x],
m n+(2 m n-m-n) x+(m-1) (n-1) x^2
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Grid",{n,n,n}},"CubePolynomial"],{n,k0=1,kmax=10}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Collect[%,x^Range[0,3],Factor]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["CubePolynomial"]/.f_Function:>f[x]

(k+(k-1) x) (m+(m-1) x) (n+(n-1) x)

k m n+(3 k m n-k m-k n-m n) x+(3 k m n-2 (k m+k n+m n)+k+m+n) x^2+(k-1) (m-1) (n-1) x^3

DeleteCases[
Sort@Flatten[Table[{
{"Grid",{m,n}},
GraphData[{"Grid",{k,m,n}},"CubePolynomial"]/.f_Function:>f[x],
k m n+(3 k m n-k m-k n-m n) x+(3 k m n-2 (k m+k n+m n)+k+m+n) x^2+(k-1) (m-1) (n-1) x^3
},{n,20},{m,n},{k,m}],2],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

HalvedCube

(poly=Factor@Table[GraphData[{"HalvedCube",n},"CubePolynomial"],{n,k0=1,10}]/.f_Function:>f[x])//Column

CoefficientList[poly,x]

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Table[Sum[2^(n-1-2 k) Factorial[n]/(Factorial[k] Factorial[n-2 k]) x^k,{k,0,Floor[n/2]}],{n,10}]//Column

Table[2^(n-1) (-1)^Floor[n/2] x^Floor[n/2]HypergeometricU[-Floor[n/2],1/2+Mod[n,2],-1/x],{n,10}]//Expand//Column

Hanoi

(poly=Factor@Table[GraphData[{"Hanoi",n},"CubePolynomial"],{n,k0=1,6}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Helm

(poly=Table[GraphData[{"Helm",n},"CubePolynomial"],{n,3,20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Hypercube

Entity["Graph",{"Hypercube",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Hypercube",n},"CubePolynomial"],{n,k0=0,10}]/.f_Function:>f[x])//Column

gf=FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>=0]

Keller

Entity["Graph",{"Keller",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Keller",n},"CubePolynomial"],{n,k0=1,5}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

I do not know a nice closed form for the full cube polynomial of the Keller graph family, and I did not find one in the sources I checked. The standard sources I found define the n-dimensional Keller graph on 4^n vertices in {0,1,2,3}^n, with two vertices adjacent when they differ in at least two coordinates and in at least one coordinate by 2 mod 4, but they do not discuss cube polynomials. ([MathWorld][1])

What does come out cleanly is the first two terms. If K_n is the n-dimensional Keller graph, then

C_{K_n}(x) = 4^n + (4^n (4^n - 3^n - n))/2 x + ...

The reason is:

* a_0 = |V(K_n)| = 4^n by definition. ([MathWorld][1])
* For a fixed vertex, a neighbor is a difference vector in {0,1,2,3}^n with at least one coordinate equal to 2 and at least two nonzero coordinates. There are 4^n - 3^n vectors with at least one 2, and exactly n of those have only one nonzero coordinate, so
  deg(K_n) = 4^n - 3^n - n.
  Hence
  a_1 = |E(K_n)| = 4^n (4^n - 3^n - n)/2.

That matches your data:

* n = 2: a_1 = 16 (16 - 9 - 2)/2 = 40
* n = 3: a_1 = 64 (64 - 27 - 3)/2 = 1088

Beyond that, the coefficients get complicated very fast. Even the square counts already look messy:
a_2 = 0, 40, 57024, 14841600, 2999124480, ...
for n = 1,2,3,4,5. I do not see a simple factorization pattern there.

Structurally, the family also does not behave like the grid or rook families where the cube polynomial factors through a graph product. Splitting by the first coordinate, K_n consists of 4 copies of K_{n-1}; opposite blocks are joined by a complete bipartite graph minus a perfect matching, while adjacent blocks are joined according to the K_{n-1} adjacency rule. So the natural object looks more like a transfer-matrix or state recursion than a tidy closed form.

So my honest answer is:

* I do not see an obvious closed form for the full cube polynomial of Keller_n.
* I do see the clean general beginning
  4^n + (4^n (4^n - 3^n - n))/2 x + ...
* and I would expect any full formula to be recursive/state-based rather than product-factorized.

If you want, I can next try to derive an exact formula for the x^2 coefficient a_2(K_n).

[1]: https://mathworld.wolfram.com/KellerGraph.html "https://mathworld.wolfram.com/KellerGraph.html"

King n×n

(poly=Table[GraphData[{"King",{n,n}},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>=1]

King m×n

KingCubePolynomial[m_,n_,x_]:=m n+(4 m n-3 m-3 n+2) x+Ramp[m-2] Ramp[n-2] x^2

DeleteCases[
Sort@Flatten[Table[{
{"King",{m,n}},
GraphData[{"King",{m,n}},"CubePolynomial"]/.f_Function:>f[x],
m n+(4 m n-3 m-3 n+2) x+Ramp[m-2] Ramp[n-2] x^2
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Yes. For the m x n king graph,
[
\mathrm{King}*{m,n}=P_m \boxtimes P_n,
]
the cube polynomial is
[
C(\mathrm{King}*{m,n},x)
========================

mn+\bigl(4mn-3m-3n+2\bigr)x+\max(m-2,0)\max(n-2,0)x^2.
]
There are no terms of degree >= 3. The king graph is the graph of legal king moves on an m x n chessboard, equivalently the strong product (P_m \boxtimes P_n). The cube polynomial counts induced hypercubes, with the constant and linear coefficients equal to the numbers of vertices and edges. ([MathWorld][1])

Why this formula is right:

Let the vertices be squares ((i,j)), with adjacency
[
(i,j)\sim(i',j')
\quad\Longleftrightarrow\quad
\max(|i-i'|,|j-j'|)=1.
]

For the x term, count edges by direction:

* horizontal edges: (m(n-1)),
* vertical edges: ((m-1)n),
* diagonal edges: (2(m-1)(n-1)).

So
[
|E|=m(n-1)+(m-1)n+2(m-1)(n-1)=4mn-3m-3n+2.
]

For the x^2 term, an induced 2-cube is an induced 4-cycle. For every interior square ((i,j)), the four squares
[
(i-1,j),\ (i+1,j),\ (i,j-1),\ (i,j+1)
]
form an induced (C_4=Q_2). Thus there are at least
[
\max(m-2,0)\max(n-2,0)
]
such 4-cycles.

Conversely, every induced 4-cycle in a king graph is of exactly that form. To see this, take one vertex of the 4-cycle as ((0,0)), and let its two neighbors on the cycle be (u=(a,b)) and (v=(c,d)), where each coordinate is in ({-1,0,1}). Since the 4-cycle is induced, (u) and (v) are not adjacent. If (w) is the fourth vertex, then (w) must be adjacent to both (u) and (v) but not to ((0,0)). For (w) to fail to be adjacent to ((0,0)), one coordinate of (w) must be (\pm 2). That forces (u) and (v) to have the same sign in one coordinate and opposite signs in the other, so up to symmetry
[
u=(1,1),\qquad v=(1,-1),\qquad w=(2,0),
]
which is exactly the translated "cross around an interior center" configuration. Hence the induced 4-cycles are in bijection with interior squares, so
[
c_2=\max(m-2,0)\max(n-2,0).
]

Finally, there are no induced cubes of dimension >= 3. If an induced (Q_d) existed, then at any cube vertex its (d) cube-neighbors would be pairwise nonadjacent in the king graph. But in a king graph, the neighborhood of any vertex has independence number at most 2: among the 8 surrounding squares, an independent set can use at most one square from each of the three rows, and if it uses three rows then the middle-row choice is adjacent to one of the others. So (d\le 2). Hence
[
c_k=0\qquad(k\ge 3).
]

So the closed form is exactly
[
\boxed{
C(\mathrm{King}_{m,n},x)
========================

mn+\bigl(4mn-3m-3n+2\bigr)x+\max(m-2,0)\max(n-2,0)x^2
}.
]

For the n x n case this becomes
[
C(\mathrm{King}_{n,n},x)=n^2+(4n^2-6n+2)x+(n-2)^2x^2,
]
which matches your data:
[
1,\ 4+6x,\ 9+20x+x^2,\ 16+42x+4x^2,\dots
]

In WL form, one clean version is

```wl
KingCubePolynomial[m_, n_, x_] := m n + (4 m n - 3 m - 3 n + 2) x + Ramp[m - 2] Ramp[n - 2] x^2
```

If you want, I can also give a short WL proof-check script comparing this against GraphData for a range of m,n.

[1]: https://mathworld.wolfram.com/KingGraph.html?utm_source=chatgpt.com "King Graph -- from Wolfram MathWorld"

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["CubePolynomial"]/.f_Function:>f[x]

DeleteCases[
Sort@Flatten[Table[{
{"Knight",{m,n}},
GraphData[{"Knight",{m,n}},"CubePolynomial"]/.f_Function:>f[x],
m n+(2 Ramp[m-1] Ramp[n-2]+2 Ramp[m-2] Ramp[n-1]) x+(4 Ramp[m-3] Ramp[n-3]+Ramp[m-4] Ramp[n-2]+Ramp[m-2] Ramp[n-4]) x^2+(2 Ramp[m-5] Ramp[n-4]+2 Ramp[m-4] Ramp[n-5]) x^3+Ramp[m-6] Ramp[n-6] x^4
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Knight",{n,n}},"CubePolynomial"],{n,k0=1,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Collect[m n+(2 Max[m-1,0] Max[n-2,0]+2 Max[m-2,0] Max[n-1,0]) x+(4 Max[m-3,0] Max[n-3,0]+Max[m-4,0] Max[n-2,0]+Max[m-2,0] Max[n-4,0]) x^2+(2 Max[m-5,0] Max[n-4,0]+2 Max[m-4,0] Max[n-5,0]) x^3+Max[m-6,0] Max[n-6,0] x^4/.m->n,{x,x^2,x^3,x^4},FullSimplify]

FullSimplify[%,n>=6]

Collect[%,x^Range[4],Factor]

Ladder

Entity["Graph",{"Ladder",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Ladder",n},"CubePolynomial"],{n,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],{x,x^2},Factor]

FullSimplify[%]

FindLinearRecurrence[DeleteMissing@poly]

LadderRung

(poly=Table[GraphData[{"LadderRung",n},"CubePolynomial"],{n,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

FindLinearRecurrence[DeleteMissing@poly]

LucasCube

A245962

(poly=Factor@Table[GraphData[{"LucasCube",n},"CubePolynomial"],{n,k0=1,15}]/.f_Function:>f[x])//Column

CoefficientList[Take[poly,6],x]

Flatten[%]

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>=0]

FullSimplify[Sum[(2Binomial[n-i,i]-Binomial[n-i-1,i])*Binomial[i,k],{i,k,n/2}]]

Table[(2 Binomial[n-k,k]-Binomial[n-k-1,k]) Hypergeometric2F1[k-(n/2),(1/2)+k-(n/2),1+k-n,-4],{n,0,10},{k,0,n/2}]

CoefficientList[Expand@Table[(2^(-n)) ((((1-(Sqrt[5+4 x])))^n)+(((1+(Sqrt[5+4 x])))^n)),{n,10}],x]

MengerSponge

(poly=Table[GraphData[{"MengerSponge",n},"CubePolynomial"],{n,3}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Table[20^n+2*4^n*(5^n-2^n)*x+(16*(5*20^n-17*8^n+12*3^n)/85)*x^2,{n,4}]//Column

Yes. If M_n denotes the order-n Menger sponge graph in the GraphData indexing, then I get

C_{M_n}(x) = 20^n + 2*4^n*(5^n - 2^n) x + (16/85)*(5*20^n - 17*8^n + 12*3^n) x^2.

There is no x^3 term. MathWorld gives the first two counts directly: the n-Menger sponge graph has 20^n vertices and 2*4^n*(5^n - 2^n) edges. Also, each face of the Menger sponge is a Sierpinski carpet, which is what drives the square count below. ([MathWorld][1])

Why degree 2 only

M_n is an induced subgraph of the 3D grid on the retained 3^n x 3^n x 3^n voxels, so an induced hypercube can only be Q_0, Q_1, Q_2, or Q_3. A Q_3 would be a filled 2x2x2 block of retained voxels.

That never happens. At level 1, the 20 retained cubes contain no 2x2 square and no 2x2x2 block. Inductively, any candidate 2x2x2 block in M_n either lies inside one of the 20 copies of M_{n-1}, or else projects to a 2x2 square or 2x2x2 block among the 20 level-1 macro-cubes. Since the level-1 pattern has neither, M_n has no induced Q_3. So the cube polynomial stops at x^2.

Counting the x^2 coefficient

Let s_n be the number of induced squares Q_2 in M_n.

A square in M_n is either:

1. entirely inside one of the 20 copies of M_{n-1}, contributing 20 s_{n-1}, or
2. split across one interface between two adjacent level-1 cubes.

There are 24 such level-1 adjacencies, because the order-1 Menger sponge graph has 24 edges. Across one interface, every edge in the order-(n-1) face graph gives exactly one spanning square. Since each face is an order-(n-1) Sierpinski carpet, if h_r is the number of edges in the order-r carpet graph, then

s_n = 20 s_{n-1} + 24 h_{n-1},
s_1 = 0.

Now h_r satisfies

h_r = 8 h_{r-1} + 8*3^(r-1),
h_1 = 8,

because the carpet consists of 8 copies of the previous stage, with 8 adjacencies between copies, and each such adjacency contributes 3^(r-1) interface edges. Solving gives

h_r = (8/5) (8^r - 3^r).

Therefore

s_n = 20 s_{n-1} + (192/5) (8^(n-1) - 3^(n-1)),
s_1 = 0,

and solving this recurrence gives

s_n = (16/85) (5*20^n - 17*8^n + 12*3^n).

So the full cube polynomial is exactly

C_{M_n}(x) = 20^n + 2*4^n*(5^n - 2^n) x + (16/85)*(5*20^n - 17*8^n + 12*3^n) x^2.

Checks:

* n = 1:
  20 + 24 x
* n = 2:
  400 + 672 x + 192 x^2

which matches your data.

In WL:

```wl
MengerSpongeCubePolynomial[n_, x_] :=
	20^n +
	2*4^n*(5^n - 2^n)*x +
	(16*(5*20^n - 17*8^n + 12*3^n)/85)*x^2
```

If you want, I can also write the analogous closed form for the Sierpinski carpet graph.

[1]: https://mathworld.wolfram.com/MengerSpongeGraph.html?utm_source=chatgpt.com "Menger Sponge Graph -- from Wolfram MathWorld"

MiddleLayer

(poly=Table[GraphData[{"MiddleLayer",n},"CubePolynomial"],{n,5}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Table[Binomial[2n+2,n+1]+(2n+1)!/n!^2x,{n,5}]//Column

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"MoebiusLadder",n},"CubePolynomial"],{n,3,25}]/.f_Function:>f[x])//Column

gf=z^3FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>3]

Mycielski

Entity["Graph",{"Mycielski",n}]["CubePolynomial"]

(poly=Table[GraphData[{"Mycielski",n},"CubePolynomial"],{n,11}]/.f_Function:>f[x])//Column

Length@DeleteMissing@poly

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Not an obvious one.

If M_n denotes the n-Mycielski graph in the usual indexing
M_1 = K_1, M_2 = P_2, M_3 = C_5, M_4 = Gr"otzsch,
then the only part of the cube polynomial that has an immediate clean closed form is the first two coefficients. By definition,
C(G,x) = Sum_k alpha_k(G) x^k
with alpha_0(G) = |V(G)| and alpha_1(G) = |E(G)|. For Mycielski graphs one has, for n >= 2,
|V(M_n)| = 3*2^(n-2) - 1
and
|E(M_n)| = (7*3^(n-2) + 1)/2 - 3*2^(n-2),
and the family is triangle-free. So at once

C(M_n,x) = (3*2^(n-2) - 1) + ((7*3^(n-2) + 1)/2 - 3*2^(n-2)) x + O(x^2).  ([ResearchGate][1])

This matches your list:
2 + x, 5 + 5 x, 11 + 20 x + ..., 23 + 71 x + ..., 47 + 236 x + ..., 95 + 755 x + ....  ([ResearchGate][1])

What makes the full polynomial hard is that a Mycielski step does not just "lift" old cubes in one uniform way. Even starting from M_3 = C_5, each induced 3-vertex path a-b-c creates two distinct squares in mu(C_5):
{a,b,c,u_b} and {u_a,b,u_c,w}.
Since C_5 has 5 induced P_3's, this gives the 10 x^2 term of M_4 immediately:
C(M_4,x) = 11 + 20 x + 10 x^2.
After that, once squares already exist, the next Mycielski step produces many additional squares and then actual 3-cubes as well, which is exactly the combinatorial explosion visible in your data:
180 x^2 + 5 x^3 for M_5,
2080 x^2 + 800 x^3 for M_6,
19734 x^2 + 71985 x^3 + 10 x^4 for M_7.

So my take is:

C(M_n,x) does not appear to have a simple one-line closed form analogous to the CCC_n case.

What does seem to exist is:

1. a clean closed form for the constant and linear terms, and
2. a much more complicated recursive description for higher coefficients, which would need extra statistics beyond just C(M_{n-1},x) itself.

In other words, the "right" object here is probably a multivariate recursion tracking induced P_3's, C_4's, 3-cubes, etc., rather than a tidy closed form in n alone.

[1]: https://www.researchgate.net/publication/220342165_The_Cube_Polynomial_and_its_Derivatives_the_Case_of_Median_Graphs "(PDF) The Cube Polynomial and its Derivatives: the Case of Median Graphs"

Necklace

(poly=Table[GraphData[{"Necklace",n},"CubePolynomial"],{n,k0=1,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Odd

Entity["Graph",{"Odd",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Odd",n},"CubePolynomial"],{n,7}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Table[Binomial[2n-1,n-1]+(1-KroneckerDelta[n,1])(n/2)Binomial[2n-1,n-1]x,{n,7}]//Column

Pan

(poly=Table[GraphData[{"Pan",n},"CubePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Path

Entity["Graph",{"Path",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Path",n},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],x,Factor]

PathComplement

(poly=Table[GraphData[{"PathComplement",n},"CubePolynomial"],{n,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Simplify[%,n>2]

Pell

(poly=Factor@Table[GraphData[{"Pell",n},"CubePolynomial"],{n,k0=1,9}]/.f_Function:>f[x])//Column

CoefficientList[Take[DeleteMissing@poly,5],x]

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

PermutationStar

(poly=Table[GraphData[{"PermutationStar",n},"CubePolynomial"],{n,5}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

PlummerToft

(poly=Table[GraphData[{"PlummerToft",n},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

coef=FindLinearRecurrence[DeleteMissing@poly]

gf=z FindGeneratingFunction[poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],{x,x^2},Factor]

Prism

Entity["Graph",{"Prism",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Prism",n},"CubePolynomial"],{n,k0=3,kmax=25}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Simplify[%,n>4]

Queen n×n

(poly=Table[GraphData[{"Queen",{n,n}},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

Length@DeleteMissing@poly

CoefficientList[DeleteMissing@poly,x]//Column

FindLinearRecurrence[poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

a0=Coefficient[DeleteMissing@poly,x,0]

FindSequenceFunction[a0,n]

a1=Coefficient[DeleteMissing@poly,x,1]

FindSequenceFunction[a1,n]//Factor

a2=Coefficient[DeleteMissing@poly,x,2]

FindGeneratingFunction[a2,x,ValidationLength->2]//Head//Timing

a3=Coefficient[DeleteMissing@poly,x,3]

FindGeneratingFunction[a3,x,ValidationLength->2]//Head//Timing

a4=Coefficient[DeleteMissing@poly,x,4]

FindGeneratingFunction[a4,x,ValidationLength->2]//Head//Timing

Table[n^2+(1/3) (n-1) n (5 n-1)x+If[n<3,0,O[x]^2],{n,20}]//Column

And no, I cannot rename your browser tab.

On the queen graph, I can say something exact, but I do not yet have a clean closed form for all coefficients.

If Q_n is the n x n queen graph, then

C_{Q_n}(x) = n^2 + n (n - 1) (5 n - 1) / 3 x + a_2(n) x^2 + a_3(n) x^3 + a_4(n) x^4,

and there are no higher terms.

The degree bound is easy: in an induced cube, each vertex can have at most one cube-neighbor in each of the four line families through that square (row, column, main diagonal, antidiagonal), so the cube dimension is at most 4.

So your vertex and edge terms are exactly right:
n^2 + 1/3 (n - 1) n (5 n - 1) x.

The remaining coefficients begin

a_2(n): 0, 0, 12, 192, 768, 2184, 4840, 9452, 16692, 27440, 42640, 63468, ...
for n = 1, 2, ..., 12,

a_3(n): 0, 0, 0, 0, 32, 332, 1520, 5508, 15996, 39204, 81784, ...
for n = 1, 2, ..., 11,

a_4(n): 0, 0, 0, 0, 0, 0, 0, 2, 32, 230, 874, ...
for n = 1, 2, ..., 11.

So the exact values I checked are

* n = 8: 64 + 728 x + 9452 x^2 + 5508 x^3 + 2 x^4
* n = 9: 81 + 1056 x + 16692 x^2 + 15996 x^3 + 32 x^4
* n = 10: 100 + 1450 x + 27440 x^2 + 39204 x^3 + 230 x^4
* n = 11: 121 + 1910 x + 42640 x^2 + 81784 x^3 + 874 x^4

What I do not yet have is a trustworthy simple formula for a_2, a_3, a_4. I was able to verify by direct search that the x^4 term really is nonzero starting at n = 8, but the patterns are much less rigid than for grids, rooks, folded cubes, etc.

The best empirical fits I currently have are:

a_3(n) = -(235 n^6 - 10941 n^5 + 204565 n^4 - 2001535 n^3 + 10875640 n^2 - 31179164 n + 36860400) / 60

for n = 5, ..., 11,

and

a_4(n) = (139 n^3 - 3501 n^2 + 29444 n - 82650) / 3

for n = 8, 9, 10, 11,

but I am not claiming either as proved.

So my honest status is:

* exact:
  C_{Q_n}(x) = n^2 + n (n - 1) (5 n - 1) / 3 x + a_2(n) x^2 + a_3(n) x^3 + a_4(n) x^4,
  with no terms above x^4

* checked exactly by computation through n = 11:
  the coefficient lists above

* not yet solved cleanly:
  a closed form for a_2(n), a_3(n), a_4(n)

The next thing I would try is a direct classification of induced Q_2, Q_3, and Q_4 by the four queen-line families. That looks doable, but I have not finished it yet.

In an n x n queen graph, fix any square v. Every neighbor of v lies in exactly one of the four attack lines through v:

* same row
* same column
* same main diagonal
* same anti-diagonal

Moreover, each of those four sets is a clique, because any two squares on the same such line attack each other.

Now suppose an induced Q_d occurred in a queen graph. Pick a vertex v of that cube. Inside Q_d, the d neighbors of v are pairwise nonadjacent. Therefore, in the queen graph, those d neighbors must come from d different cliques in the neighborhood of v. But the neighborhood of v is covered by only 4 such cliques, so

d <= 4.

Hence an induced 5-cube cannot occur in any queen graph. Therefore

a_5 = 0

for every queen graph, and in fact all coefficients a_k with k >= 5 are 0.

So your data stopping at x^4 is not just a small-n phenomenon; x^5 can never appear.

Rook m×n

DeleteCases[
Sort@Flatten[Table[{
{"Rook",{m,n}},
GraphData[{"Rook",{m,n}},"CubePolynomial"]/.f_Function:>f[x],
m n+m n(m+n-2)/2x+Binomial[m,2]Binomial[n,2](x^2)
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Rook n×n

(poly=Table[GraphData[{"Rook",{n,n}},"CubePolynomial"],{n,k0=1,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Collect[%,{x,x^2},Factor]

RookComplement m×n

DeleteCases[
Sort@Flatten[Table[{
{"RookComplement",{m,n}},
GraphData[{"RookComplement",{m,n}},"CubePolynomial"]/.f_Function:>f[x],
m n+2Binomial[m,2]Binomial[n,2]x+(Binomial[m,2] Binomial[n,2] (m+n-5)(m+n-4))/2 x^2+(Binomial[m,2] Binomial[n,4]+Binomial[m,4] Binomial[n,2]) x^3
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

RookComplement n×n

(poly=Factor@Table[GraphData[{"RookComplement",{n,n}},"CubePolynomial"],{n,k0=1,20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

SierpinskiCarpet

(poly=Factor@Table[GraphData[{"SierpinskiCarpet",n},"CubePolynomial"],{n,k0=1,3}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Table[8^n+(8 (8^n-3^n)/5) x+(8 (2*8^n-7*3^n+5)/35) x^2,{n,5}]//Column

Yes. If we write

SC_n = GraphData[{"SierpinskiCarpet", n}],

then the cube polynomial is

C_SC_n(x) = 8^n + (8/5) (8^n - 3^n) x + (8/35) (2*8^n - 7*3^n + 5) x^2.

This gives

* n = 1: 8 + 8 x
* n = 2: 64 + 88 x + 16 x^2
* n = 3: 512 + 776 x + 192 x^2

which is exactly what I get from the self-similar construction. The MathWorld definition says the n-th Sierpinski carpet graph is the adjacency graph of the black squares in the n-th carpet, with n = 1 equal to C_8, while the carpet itself is built from 8 copies at each stage in a 3 x 3 pattern with the center removed and has 8^n black cells. ([MathWorld][1])

The reason the polynomial stops at x^2 is that SC_n is an induced subgraph of the 3^n x 3^n grid graph on the retained cells. Any induced hypercube in an induced subgraph is also an induced hypercube in the ambient graph, and a 2-dimensional grid graph has no induced cubes above dimension 2. So only the vertex, edge, and square counts can occur. ([MathWorld][1])

Let e_n and q_n be the coefficients of x and x^2. From the 8-copy construction,

e_n = 8 e_(n-1) + 8*3^(n-1), with e_1 = 8,

because there are 8 copies of SC_(n-1) plus 8 interfaces between adjacent copies, and each interface contributes a full strip of 3^(n-1) edges. Solving gives

e_n = (8/5) (8^n - 3^n). ([MathWorld][1])

Similarly,

q_n = 8 q_(n-1) + 8 (3^(n-1) - 1), with q_1 = 0,

because each of the same 8 interfaces is a path of length 3^(n-1), hence contributes 3^(n-1) - 1 spanning 2 x 2 squares. Solving gives

q_n = (8/35) (2*8^n - 7*3^n + 5). ([MathWorld][1])

In WL:

```wl
SierpinskiCarpetCubePolynomial[n_, x_] :=
	8^n +
	(8 (8^n - 3^n)/5) x +
	(8 (2*8^n - 7*3^n + 5)/35) x^2
```

And if you want the 3D analogue written in the same style as a recurrence/proof note, I can format that too.

[1]: https://mathworld.wolfram.com/SierpinskiCarpetGraph.html "Sierpiński Carpet Graph -- from Wolfram MathWorld"

SierpinskiGasket

(poly=Factor@Table[GraphData[{"SierpinskiGasket",n},"CubePolynomial"],{n,k0=1,7}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

SierpinskiTetrahedron

(poly=Factor@Table[GraphData[{"SierpinskiTetrahedron",n},"CubePolynomial"],{n,k0=1,6}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>=1]

StackedBook n×n

(poly=Factor@Table[GraphData[{"StackedBook",{n,n}},"CubePolynomial"],{n,k0=1,10}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

StackedPrism m×n

StackedPrismCubePolynomial[m_,n_,x_]:=Piecewise[{{4 n+(8 n-4) x+(5 n-4) x^2+(n-1) x^3,m==4}},m n+m (2 n-1) x+m (n-1) x^2]

DeleteCases[
Sort@Flatten[Table[{
{"StackedPrism",{m,n}},
GraphData[{"StackedPrism",{m,n}},"CubePolynomial"]/.f_Function:>f[x],
StackedPrismCubePolynomial[m,n,x]
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Star

Entity["Graph",{"Star",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Star",n},"CubePolynomial"],{n,k0=1,kmax=25}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>0],x,Factor]

Sun

(poly=Table[GraphData[{"Sun",n},"CubePolynomial"],{n,k0=3,kmax=20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Collect[Simplify[SeriesCoefficient[gf,{z,0,n}],n>2],{x,x^2},Factor]

Sunlet

(poly=Table[GraphData[{"Sunlet",n},"CubePolynomial"],{n,k0=3,kmax=20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>2]

Tetrahedral

(poly=Table[GraphData[{"Tetrahedral",n},"CubePolynomial"],{n,k0=6,kmax=10}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Table[({1,6,15,15}x^Range[0,3]).Binomial[n,Range[3,6]],{n,6,10}]//Expand//Column

TorusGrid n×n

(poly=Table[GraphData[{"TorusGrid",{n,n}},"CubePolynomial"],{n,k0=3,kmax=20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>2]

TorusGridCubePolynomial[m_,n_,x_]:=(m+m x+Boole[m==4] x^2) (n+n x+Boole[n==4] x^2)

TorusGridCubePolynomial[n,n,x]

TorusGrid m×n

TorusGridCubePolynomial[m_,n_,x_]:=(m+m x+Boole[m==4] x^2) (n+n x+Boole[n==4] x^2)

DeleteCases[
Sort@Flatten[Table[{
{"TorusGrid",{m,n}},
GraphData[{"TorusGrid",{m,n}},"CubePolynomial"]/.f_Function:>f[x],
Expand@TorusGridCubePolynomial[m,n,x]
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

If by "trous grid" you mean the MathWorld torus grid graph, then
[
T_{m,n}=C_m \square C_n,
]
and MathWorld explicitly notes "m x n trous grid graph" as an alternate name. ([MathWorld][1])

Its cube polynomial is
[
C(T_{m,n},x)=C(C_m,x),C(C_n,x),
]
using the product property of the cube polynomial together with the fact that the torus grid graph is the Cartesian product (C_m \square C_n). The original cube-polynomial paper lists product as one of its basic properties. ([MathWorld][1])

Since
[
C(C_r,x)=
\begin{cases}
r+rx, & r\ne 4,\
4+4x+x^2, & r=4,
\end{cases}
]
you get the closed form
[
C(T_{m,n},x)=
\begin{cases}
mn+2mn,x+mn,x^2, & m\ne 4,\ n\ne 4,[4pt]
4n+8n,x+5n,x^2+n,x^3, & m=4,\ n\ne 4,[4pt]
4m+8m,x+5m,x^2+m,x^3, & n=4,\ m\ne 4,[4pt]
16+32x+24x^2+8x^3+x^4, & m=n=4.
\end{cases}
]
The last case is (C_4 \square C_4 \cong Q_4), which MathWorld lists as the tesseract graph. ([MathWorld][1])

A compact equivalent form is
[
C(T_{m,n},x)=\bigl(m+mx+\delta_{m,4}x^2\bigr)\bigl(n+nx+\delta_{n,4}x^2\bigr).
]

In WL:

```wl
TorusGridCubePolynomial[m_, n_, x_] := Piecewise[
    {
        {16 + 32 x + 24 x^2 + 8 x^3 + x^4, m == 4 && n == 4},
        {4 n + 8 n x + 5 n x^2 + n x^3, m == 4},
        {4 m + 8 m x + 5 m x^2 + m x^3, n == 4}
    },
    m n + 2 m n x + m n x^2
]
```

Or more compactly:

```wl
TorusGridCubePolynomial[m_, n_, x_] := (m + m x + Boole[m == 4] x^2) (n + n x + Boole[n == 4] x^2)
```

[1]: https://mathworld.wolfram.com/TorusGridGraph.html "Torus Grid Graph -- from Wolfram MathWorld"

Transposition

Entity["Graph",{"Transposition",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Transposition",n},"CubePolynomial"],{n,k0=1,kmax=6}]/.f_Function:>f[x])//Column

Length@DeleteMissing@poly

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Yes, at least for the first several coefficients.

`GraphData[{"Transposition", n}]` is the complete transposition graph on `S_n`: its vertices are the `n!` permutations, and two vertices are adjacent when they differ by a single transposition. Hence it has `n!` vertices and degree `Binomial[n,2]`, so the linear term is `n! Binomial[n,2]/2`. ([Wolfram Documentation][1])

I do not yet have a compact all-k closed form, but I do have exact formulas for the coefficients through `x^5`. They match your `n=1..4` data exactly, and also the direct counts I computed for `n=5,6`.

If `T_n = GraphData[{"Transposition", n}]`, then

```wl
TranspositionCubePolynomial[n_, x_] :=
	n!
	+ (n! Binomial[n, 2]/2) x
	+ (n! (6 Binomial[n, 3] + 3 Binomial[n, 4])/4) x^2
	+ (n! (72 Binomial[n, 4] + 60 Binomial[n, 5] + 15 Binomial[n, 6])/8) x^3
	+ (n! (6 Binomial[n, 4] + 1320 Binomial[n, 5] + 1440 Binomial[n, 6] + 630 Binomial[n, 7] + 105 Binomial[n, 8])/16) x^4
	+ (n! (480 Binomial[n, 5] + 32850 Binomial[n, 6] + 42840 Binomial[n, 7] + 25200 Binomial[n, 8] + 7560 Binomial[n, 9] + 945 Binomial[n, 10])/32) x^5
```

So the first coefficients are

`a0(n) = n!`

`a1(n) = n! Binomial[n,2]/2`

`a2(n) = n! (6 Binomial[n,3] + 3 Binomial[n,4])/4`

`a3(n) = n! (72 Binomial[n,4] + 60 Binomial[n,5] + 15 Binomial[n,6])/8`

`a4(n) = n! (6 Binomial[n,4] + 1320 Binomial[n,5] + 1440 Binomial[n,6] + 630 Binomial[n,7] + 105 Binomial[n,8])/16`

`a5(n) = n! (480 Binomial[n,5] + 32850 Binomial[n,6] + 42840 Binomial[n,7] + 25200 Binomial[n,8] + 7560 Binomial[n,9] + 945 Binomial[n,10])/32`

These reproduce your listed values:

* `n=3`: `6 + 9 x + 9 x^2`
* `n=4`: `24 + 72 x + 162 x^2 + 216 x^3 + 9 x^4`

and they give

* `n=5`: `120 + 600 x + 2250 x^2 + 6300 x^3 + 10125 x^4 + 1800 x^5`
* `n=6`: `720 + 5400 x + 29700 x^2 + 130950 x^3 + 425250 x^4 + 803925 x^5 + ...`

So this is not the whole polynomial yet, but it is an exact closed form for the first six terms.

The structural pattern is that the `x^k` coefficient is `n!/2^k` times a polynomial in binomial terms `Binomial[n,m]`, coming from choosing disjoint symbol sets that support connected `k`-cube components. That is why the formulas naturally come out in the `Binomial[n,m]` basis.

The next natural step is to derive `a6(n)` exactly. I can do that next.

[1]: https://reference.wolfram.com/language/ref/GraphData.html?utm_source=chatgpt.com "GraphData - Wolfram Language Documentation"

Yes - there is no fixed cutoff as n grows.

`GraphData[{"Transposition", n}]` is the transposition graph `CT_n`, and cube polynomials count induced `Q_k` subgraphs. Also, the literature explicitly notes that the transposition graph of a graph consisting of `m` independent edges is exactly the `m`-cube `Q_m`, and that the complete transposition graph is the transposition graph of `K_n`. ([Wolfram Documentation][1])

So if `K_n` contains a matching of size

```wl
Floor[n/2]
```

then `CT_n` contains at least an induced `Q_Floor[n/2]`: just use those disjoint transpositions. On that `2^Floor[n/2]`-vertex set, two vertices differ by a transposition iff they differ in exactly one chosen matching edge, because a product of 2 or more disjoint transpositions is not itself a transposition. So this really is an induced hypercube.

Therefore

```wl
MaxCubeDimension[GraphData[{"Transposition", n}]] >= Floor[n/2]
```

and in particular the maximum induced-cube dimension is unbounded in `n`.

So the answer to your question is:

```wl
There is no n-independent cutoff.
```

What I do *not* yet have is the exact top degree of `CubePolynomial[GraphData[{"Transposition", n}], x]` for general `n`. The matching argument gives a rigorous lower bound `Floor[n/2]`, but your `n=4` data already shows the true maximum can be larger than that.

If you want, the next useful step is for me to compute the actual top degree for `n=5,6` and try to guess/prove the exact formula.

[1]: https://reference.wolfram.com/language/ref/GraphData.html "GraphData—Wolfram Documentation"

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Trapezohedron",n},"CubePolynomial"],{n,k0=3,kmax=20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>2]

Collect[Simplify[%,n>3],{x,x^2},Factor]

Triangular

(poly=Table[GraphData[{"Triangular",n},"CubePolynomial"],{n,k0=3,kmax=20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>2]

TriangularGrid

(poly=Table[GraphData[{"TriangularGrid",n},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

TriangularHoneycombAcuteKnight

(poly=Factor@Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

TriangularHoneycombBishop

(poly=Factor@Table[GraphData[{"TriangularHoneycombBishop",n},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

TriangularHoneycombObtuseKnight

(poly=Factor@Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

TriangularHoneycombQueen

(poly=Factor@Table[GraphData[{"TriangularHoneycombQueen",n},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

TriangularHoneycombQueenCubePolynomial[n_,x_]:=Module[{a2,a3},a2=(3 n^4-10 n^3+3 n^2+10 n-3+3 (-1)^n)/8;
a3=Piecewise[{{((n-1) (n-3) (n-5) (41 n^2-66 n-507))/1280,Mod[n,2]==1},{-((n-2) (n-4) (5 n^4-732 n^3+6388 n^2-24576 n+57600))/15360,Mod[n,2]==0}}];
n (n+1)/2+n (n-1) (n+1)/2 x+a2 x^2+a3 x^3]

Table[TriangularHoneycombQueenCubePolynomial[n,x],{n,20}]//Column

Yes. Using the standard triangular-honeycomb queen definition - vertices are the points of a triangular honeycomb board with `n` vertices on each side, and two vertices are adjacent when they lie on a common horizontal, `+60` degree, or `-60` degree line - this is exactly `GraphData[{"TriangularHoneycombQueen", n}]`. ([MathWorld][1])

If you write the vertices in barycentric coordinates as triples `(a,b,c)` with `a,b,c >= 0` and `a + b + c = n - 1`, then adjacency means "share one coordinate." That gives 3 edge colors. In an induced cube, two incident edges at a vertex cannot have the same color, or you immediately get a triangle. So there are no induced `Q_k` with `k >= 4`, hence the cube polynomial has degree at most 3.

The exact formula matching your values is:

```wl
TriangularHoneycombQueenCubePolynomial[n_, x_] :=
	Module[{a2, a3},
		a2 = (3 n^4 - 10 n^3 + 3 n^2 + 10 n - 3 + 3 (-1)^n)/8;

		a3 = Piecewise[
			{
				{
					((n - 1) (n - 3) (n - 5) (41 n^2 - 66 n - 507))/1280,
					Mod[n, 2] == 1
				},
				{
					-((n - 2) (n - 4) (5 n^4 - 732 n^3 + 6388 n^2 - 24576 n + 57600))/15360,
					Mod[n, 2] == 0
				}
			}
		];

		n (n + 1)/2 + n (n - 1) (n + 1)/2 x + a2 x^2 + a3 x^3
	]
```

Equivalently, coefficientwise:

* `a0(n) = n (n + 1)/2`
* `a1(n) = n (n - 1) (n + 1)/2 = 3 Binomial[n + 1, 3]`
* `a2(n) = (3 n^4 - 10 n^3 + 3 n^2 + 10 n - 3 + 3 (-1)^n)/8`
* `a3(n) =`

  * `((n - 1) (n - 3) (n - 5) (41 n^2 - 66 n - 507))/1280` for odd `n`
  * `-((n - 2) (n - 4) (5 n^4 - 732 n^3 + 6388 n^2 - 24576 n + 57600))/15360` for even `n`

This reproduces exactly your listed values:

* `n=6`: `21 + 105 x + 237 x^2 + 6 x^3`
* `n=10`: `55 + 495 x + 2550 x^2 + 723 x^3`
* `n=14`: `105 + 1365 x + 11067 x^2 + 6648 x^3`

A slightly cleaner parity-split form for `a2(n)` is:

* even `n`:
  `a2(n) = n (n - 2) (3 n^2 - 4 n - 5)/8`
* odd `n`:
  `a2(n) = (n - 1) (n + 1) (3 n^2 - 10 n + 6)/8`

If you want, I can next do `TriangularHoneycombRook[n]` and `TriangularHoneycombBishop[n]`, which should also be clean.

[1]: https://mathworld.wolfram.com/TriangularHoneycombQueenGraph.html?utm_source=chatgpt.com "Triangular Honeycomb Queen Graph -- from Wolfram MathWorld"

TriangularHoneycombRook

(poly=Factor@Table[GraphData[{"TriangularHoneycombRook",n},"CubePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

TriangularSnake

(poly=Table[GraphData[{"TriangularSnake",n},"CubePolynomial"],{n,k0=1,kmax=20,2}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

TruncatedSquareLattice n×n

(poly=Table[GraphData[{"TruncatedSquareLattice",{n,n}},"CubePolynomial"],{n,k0=1,kmax=10,2}]/.f_Function:>f[x])//Column

TruncatedSquareLatticeCubePolynomial[m_,n_,x_]:=4 m n+6 m n x+Piecewise[{{m n x^2,m>1&&n>1}},0]

TruncatedSquareLatticeCubePolynomial[n,n,x]

gf=z FindGeneratingFunction[poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]

TruncatedSquareLattice m×n

TruncatedSquareLatticeCubePolynomial[m_,n_,x_]:=4 m n+6 m n x+Piecewise[{{m n x^2,m>1&&n>1}},0]

DeleteCases[
Sort@Flatten[Table[{
{"TruncatedSquareLattice",{m,n}},
GraphData[{"TruncatedSquareLattice",{m,n}},"CubePolynomial"]/.f_Function:>f[x],
TruncatedSquareLatticeCubePolynomial[m,n,x]
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Using the MathWorld definition of the m x n truncated square lattice graph, let T[m,n] denote that graph. MathWorld describes it as a cubic graph coming from the finite truncated square lattice with wraparound, with special cases such as (1,1) = K4 and (1,n) = the n-necklace graph. The standard cube polynomial convention is
C(G,x) = Sum_{k >= 0} c_k(G) x^k,
where c_k(G) counts induced Q_k subgraphs, with c_0(G) = |V(G)| and c_1(G) = |E(G)|.  ([MathWorld][1])

For this family, the closed form is

C(T[m,n], x) = 4 m n + 6 m n x + Piecewise[{{m n x^2, m > 1 && n > 1}}, 0].

Equivalently,

C(T[m,n], x) =
4 m n + 6 m n x,                    if m == 1 || n == 1,
4 m n + 6 m n x + m n x^2,         if m > 1 && n > 1.

There are no terms of degree >= 3.

Here is the derivation.

Model the vertices as the 4 "darts" at each of the m n square-lattice sites: E, N, W, S. So there are 4 m n vertices. Since the graph is cubic, the number of edges is (3 * 4 m n)/2 = 6 m n. That already gives the constant and linear terms.  ([MathWorld][1])

For the x^2 term, each lattice site gives one obvious 4-cycle, namely the cycle through its four darts in cyclic order. If m > 1 && n > 1, that 4-cycle is induced, so this gives m n induced Q_2's.

These are the only induced 4-cycles. To see why, split the edges into two types: local edges inside one dart-square, and transit edges that connect opposite ends of one lattice edge. A 4-cycle containing a transit edge would have to use another transit edge after one local step, but one local step changes direction while a transit edge preserves the direction class needed to cross the same lattice displacement, so the cycle cannot close in 4 steps. Hence no induced 4-cycle uses a transit edge, and every induced 4-cycle is one of the m n local dart-squares.

When m == 1 or n == 1, each such local 4-cycle gets a chord from the wraparound identification, so none of them is induced. Hence c_2 = 0 in those cases. This agrees with the MathWorld special cases: for (1,1) you get K4, whose cube polynomial is 4 + 6 x.  ([MathWorld][1])

Finally, c_3 = 0. In an induced Q_3, every edge lies in exactly two induced 4-cycles. But in T[m,n], every transit edge lies in no 4-cycle, and every local edge lies in at most one induced 4-cycle. So an induced cube Q_3 cannot occur. Therefore all higher coefficients are also 0.

In WL form:

```wl
TruncatedSquareLatticeCubePolynomial[m_, n_, x_] := 4 m n + 6 m n x + Piecewise[{{m n x^2, m > 1 && n > 1}}, 0]
```

A few checks are:

* (1,1): 4 + 6 x
* (1,n): 4 n + 6 n x
* (2,2): 16 + 24 x + 4 x^2
* (4,4): 64 + 96 x + 16 x^2

If you want, I can also write this in your preferred Ramp form.

[1]: https://mathworld.wolfram.com/TruncatedSquareLatticeGraph.html "Truncated Square Lattice Graph -- from Wolfram MathWorld"

Web

(poly=Table[GraphData[{"Web",n},"CubePolynomial"],{n,k0=3,kmax=20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>2]

Wheel

Entity["Graph",{"Wheel",n}]["CubePolynomial"]/.f_Function:>f[x]

(poly=Table[GraphData[{"Wheel",n},"CubePolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[x])//Column

gf=z^4FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>3]

Collect[Simplify[%,n>5],{x},Factor]

WheelComplement

(poly=Table[GraphData[{"WheelComplement",n},"CubePolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[x])//Column

gf=(z^4)FindGeneratingFunction[poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>=4]

WhiteBishop n×n

(poly=Table[GraphData[{"WhiteBishop",{n,n}},"CubePolynomial"],{n,2,20}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Yes.

For `GraphData[{"WhiteBishop",{n,n}}]`, the cube polynomial is always quadratic:

```wl
CubePolynomial[GraphData[{"WhiteBishop",{n,n}}], x] = a0[n] + a1[n] x + a2[n] x^2
```

with no terms above `x^2`.

A clean exact WL form is:

```wl
WhiteBishopCubePolynomial[n_, x_] :=
	Piecewise[
		{
			{
				n^2/2
				+ n (n - 1) (2 n - 1)/6 x
				+ n (n - 2) (n - 1)^2/24 x^2,
				EvenQ[n]
			},
			{
				(n^2 - 1)/2
				+ (n^2 - 1) (2 n - 3)/6 x
				+ (n - 1) (n + 1) (n^2 - 4 n + 6)/24 x^2,
				OddQ[n]
			}
		}
	]
```

Equivalently, if you prefer `n = 2 m` / `n = 2 m + 1`:

For `n = 2 m`,

```wl
2 m^2
+ m (2 m - 1) (4 m - 1)/3 x
+ m (m - 1) (2 m - 1)^2/6 x^2
```

For `n = 2 m + 1`,

```wl
2 m (m + 1)
+ 2 m (m + 1) (4 m - 1)/3 x
+ m (m + 1) (4 m^2 - 4 m + 3)/6 x^2
```

This matches your values:

* `n=2`: `2 + x`
* `n=3`: `4 + 4 x + x^2`
* `n=4`: `8 + 14 x + 3 x^2`
* `n=5`: `12 + 28 x + 11 x^2`
* `n=6`: `18 + 55 x + 25 x^2`
* `n=10`: `50 + 285 x + 270 x^2`
* `n=20`: `200 + 2470 x + 5415 x^2`

Reason in brief: the white-bishop graph is the rook graph on the incidence board of the chosen-color diagonals, and that incidence board is a staircase board. Vertices are cells, edges come from sharing one of the two diagonal directions, and induced `Q_2`'s are exactly rectangles in that board. Since there are only two coordinate types, no induced cubes of dimension `>= 3` can occur.

If you want, I can do the black-bishop case next, though it should just be the parity-complementary version of this one.

Certainly. Here is the same formula using `Mod[n, 2] == 0` and `Mod[n, 2] == 1`:

```wl
WhiteBishopCubePolynomial[n_, x_] :=
	Piecewise[
		{
			{
				n^2/2
				+ n (n - 1) (2 n - 1)/6 x
				+ n (n - 2) (n - 1)^2/24 x^2,
				Mod[n, 2] == 0
			},
			{
				(n^2 - 1)/2
				+ (n^2 - 1) (2 n - 3)/6 x
				+ (n - 1) (n + 1) (n^2 - 4 n + 6)/24 x^2,
				Mod[n, 2] == 1
			}
		}
	]
```

A slightly more compact equivalent is:

```wl
WhiteBishopCubePolynomial[n_, x_] :=
	Piecewise[
		{
			{
				n^2/2
				+ n (n - 1) (2 n - 1)/6 x
				+ n (n - 2) (n - 1)^2/24 x^2,
				Mod[n, 2] == 0
			}
		},
		(n^2 - 1)/2
		+ (n^2 - 1) (2 n - 3)/6 x
		+ (n - 1) (n + 1) (n^2 - 4 n + 6)/24 x^2
	]
```

WhiteBishopCubePolynomial[n_, x_] :=
	Piecewise[
		{
			{
				n^2/2
				+ n (n - 1) (2 n - 1)/6 x
				+ n (n - 2) (n - 1)^2/24 x^2,
				Mod[n, 2] == 0
			},
			{
				(n^2 - 1)/2
				+ (n^2 - 1) (2 n - 3)/6 x
				+ (n - 1) (n + 1) (n^2 - 4 n + 6)/24 x^2,
				Mod[n, 2] == 1
			}
		}
	]

poly=Table[WhiteBishopCubePolynomial[n,x],{n,30}];

Zebra n×n

(poly=Table[GraphData[{"Zebra",{n,n}},"CubePolynomial"],{n,20}]/.f_Function:>f[x])//Column

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Yes. The `n x n` zebra graph has a very clean exact formula, and the cube polynomial stops at `x^4`.

A convenient WL form is

```wl
ZebraCubePolynomial[n_, x_] :=
	n^2
	+ 4 Max[n - 2, 0] Max[n - 3, 0] x
	+ (2 Max[n - 4, 0] Max[n - 6, 0] + 4 Max[n - 5, 0]^2) x^2
	+ 4 Max[n - 7, 0] Max[n - 8, 0] x^3
	+ Max[n - 10, 0]^2 x^4
```

This matches your values exactly:

* `n = 6`: `36 + 48 x + 4 x^2`
* `n = 9`: `81 + 168 x + 94 x^2 + 8 x^3`
* `n = 11`: `121 + 288 x + 214 x^2 + 48 x^3 + x^4`
* `n = 20`: `400 + 1224 x + 1348 x^2 + 624 x^3 + 100 x^4`

If you want the expanded polynomial valid once all terms are present (`n >= 11`), it is

```wl
n^2
+ (4 n^2 - 20 n + 24) x
+ (6 n^2 - 60 n + 148) x^2
+ (4 n^2 - 60 n + 224) x^3
+ (n^2 - 20 n + 100) x^4
```

Equivalently,

```wl
ZebraCubePolynomialExpanded[n_, x_] :=
	n^2
	+ (4 n^2 - 20 n + 24) x
	+ (6 n^2 - 60 n + 148) x^2
	+ (4 n - 28) (n - 8) x^3
	+ (n - 10)^2 x^4
```

with the understanding that this expanded form is only valid after the corresponding cubes can occur; the `Max[...]` form is exact for all `n`.

The coefficient structure comes from the four independent move directions of the zebra `(2,3)` leaper, so there are no terms above `x^4`.

ZebraCubePolynomial[n_,x_]:=n^2+4 Ramp[n-2] Ramp[n-3] x+(2 Ramp[n-4] Ramp[n-6]+4 Ramp[n-5]^2) x^2+4 Ramp[n-7] Ramp[n-8] x^3+Ramp[n-10]^2 x^4

Table[ZebraCubePolynomial[n,x],{n,20}]//Column