Knight Graph

Author

Eric W. Weisstein
August 2, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/KnightGraph.nb.

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

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

Usage

Built-in

?KnightTourGraph

Graphs.m

?KnightGraph

Graphic

Built-in

GraphicsGrid[Partition[Table[KnightTourGraph[n,n,VertexSize->If[n==1,.01,{"Scaled",.04}],System`VertexStyle->Red,System`EdgeStyle->Black],{n,6}],UpTo[3]],Dividers->All]

Graphs.m

GraphicsGrid[Partition[Table[KnightGraph[n,n,VertexSize->If[n==1,.01,{"Scaled",.04}],System`VertexStyle->Red,System`EdgeStyle->Black],{n,6}],UpTo[3]],Dividers->All]

GraphData

GraphicsGrid[Partition[Table[GraphData[{"Knight",{n,n}},"Graph","Grid"][[1]]/.g_System`Graph:>SetProperty[g,{VertexSize->If[n==1,.01,{"Scaled",.04}],System`VertexStyle->Red,System`EdgeStyle->Black}],{n,6}],UpTo[3]],Dividers->All]

Special cases

With[{cl="Knight"},TextGrid[Sort[{cl/.GraphData[#,"NotationRules"],GraphData[#,"Name"]}&/@DeleteCases[GraphData[cl],{cl,_}]],Dividers->All]]

Complements

Grid[DeleteCases[GraphData[#,{"#","ComplementGraphName"}]&/@GraphData["Knight"],{_,_Missing}],Alignment->Left,Dividers->All]

StandardNames

rules=Sort@Flatten[Table[{m,n}->CanonicalName@ToEntity@KnightGraph[m,n],{n,10},{m,n}]]

Grid[Sort[{
#,
With[{cc=GraphData[#,"ConnectedComponents","Name"]},
Check[
StringJoin@@Riffle[Reverse@SortBy[Reverse/@Tally[cc],GraphData[#[[2]],"V"]&]/.{
{n_,"SingletonGraph"}:>ToString[n]<>"K1",
{n_,{"Path",k_}}:>ToString[n]<>"P"<>ToString[k],
{n_,{"Cycle",k_}}:>If[n==1,"",ToString[n]]<>"C"<>ToString[k]
},"+"],
cc]//Quiet
]
}&/@GraphData[{"Knight","Disconnected","Nonempty"}]],Dividers->All,Alignment->Left]

Embeddings

<<MathWorld`Graphs`

e[l__Integer]:=Sequence@@Partition[{l},2,1]

All

With[{cl="Knight"},SlideView[Sort@{Column[Union@{#,{cl,cl/.GraphData[#,"NotationRules"]}},Alignment->Center],GetGraphData[#,"File"],Grid[Transpose[{GraphData[#,"Graph","All"],GraphData[#,"EmbeddingClasses"]}],Dividers->All]}&/@Sort@GraphData@cl]]

{"Knight", {4, 4}}

GraphData[{"Knight",{4,4}},"StandardName"]

All

GraphData[{"Knight",{4,4}},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Knight",{4,4}},"LCFSignature"]

GraphData[{"Knight",{4,4}},"Graph","LCF"]//StyleGraphs

UnitDistance

UnitDistanceGraphQ[GraphData[{"Knight",{4,4}}],Debug->True]

GraphData[{"Knight",{4,4}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Knight",{4,4}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

l=FindSubgraphIsomorphism[GraphData[{"Knight",{4,4}}],"Results"->All]//Timing

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Knight",{4,4}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Knight",{4,4}},{"RCN","CN"}]

GraphData[{"Knight",{4,4}},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Knight",{4,4}},"Edges"]]

Default embedding

g=GraphPlot@GraphData[{"Knight",{4,4}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@MinimalCrossingGraph[GraphData[{"Knight",{4,4}}],"CrossingNumber"->2]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Knight", {4, 5}}

GraphData[{"Knight",{4,5}},"StandardName"]

All

GraphData[{"Knight",{4,5}},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Knight",{4,5}},"LCFSignature"]

GraphData[{"Knight",{4,5}},"Graph","LCF"]//StyleGraphs

UnitDistance

UnitDistanceGraphQ[GraphData[{"Knight",{4,5}}],Debug->True]

GraphData[{"Knight",{4,5}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Knight",{4,5}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

l=FindSubgraphIsomorphism[GraphData[{"Knight",{4,5}}],"Results"->All]//Timing

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Knight",{4,5}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Knight",{4,5}},{"RCN","CN"}]

GraphData[{"Knight",{4,5}},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Knight",{4,5}},"Edges"]]

Default embedding

GraphData[{"Knight",{4,5}},"V"]

GraphPlot@GraphData[{"Knight",{4,5}},"Edges"]

v={{0,0},{2,0},{4,0},{6,0},{1,1},{3,1},{5,1},{3,2},{0,3},{2,3},{4,3},{6,3},{3,4},{1,5},{3,5},{5,5},{0,6},{2,6},{4,6},{6,6}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,12,20,19,18,17,9,1],e[2,5,9,14,18,10,2],e[3,11,19,16,12,7,3],e[9,15,16],e[12,6,5],e[9,8,7],e[14,13],e[6,10,13,12],e[8,11,15]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Knight",{4,5}}],"CrossingNumber"->4],{14,12}]

v={{-1,0},{4,0},{8,0},{1,1},{4,1},{5,1},{7,1},{2,2},{3,2},{6,2},{3,3},{4,3},{6,3},{1,4},{3,4},{4,4},{5,4},{-1,10},{3,10},{8,10}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,20,19,18,1,11,12,13,3,7,6,5,4,2,6],e[4,14],e[1,14,19,7],e[5,8,15,19,16,12],e[16,17,13],e[5,9,11],{12,15},e[5,10,13],{8,11},{17,5}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

HamiltonianCycles

3×n

Flatten[{Last[#],
GeometricallyDistinct[hp=GetGraphData[#,"HP"],Last[#]]//Length,
Length[hp],
GeometricallyDistinct[hc=GetGraphData[#,"HC"],Last[#]]//Length,
Length[hc]
}]&/@Cases[GraphData["KnightsTour"],{_,{3,_}|{_,3}}]//Column

HamiltonianCycles[KnightsTourGraph[3,10],All]//Length//Timing

HamiltonianCycles[KnightsTourGraph[3,11],All]//Length//Timing

HamiltonianCycles[KnightsTourGraph[3,12],All]//Length//Timing

HamiltonianCycles[KnightsTourGraph[3,13],All]//Length//Timing

HamiltonianCycles[KnightsTourGraph[3,14],All]//Length//Timing

HamiltonianCycles[KnightsTourGraph[3,16],All]//Length//Timing

HamiltonianCycles[KnightsTourGraph[3,18],All]//Length//Timing

HamiltonianCycles[KnightsTourGraph[3,20],All]//Length//Timing

l={32,352,3072,30848,295456,2896832}/32

FindSequenceFunction[l]

FindSequenceFunction/@Transpose[Partition[l,2]]

FindLinearRecurrence[l]

FindLinearRecurrence/@Transpose[Partition[l,2]]

g=32(z^5+5*z^6-34*z^7-116*z^8+505*z^9+616*z^10-3179*z^11-4*z^12+9536*z^13-8176*z^14-13392*z^15+15360*z^16+13888*z^17+2784*z^18-3328*z^19-22016*z^20+5120*z^21+2048*z^22)/(1-6*z-64*z^2+200*z^3+1000*z^4-3016*z^5-3488*z^6+24256*z^7-23776*z^8-104168*z^9+203408*z^10+184704*z^11-443392*z^12-14336*z^13+151296*z^14-145920*z^15+263424*z^16-317440*z^17-36864*z^18+966656*z^19-573440*z^20-131072*z^21);

Numerator[g]//TraditionalForm

Denominator[g]//TraditionalForm

Series[g,{z,0,10}]

CoefficientList[%,z]

r=FindLinearRecurrence[CoefficientList[Series[g,{z,0,50}],z]]

TraditionalForm[Total[MapIndexed[Subscript[a,n+#2[[1]]]#&,r]]]

TraditionalForm[HoldForm[6 (Subscript[a, n+1])+64 (Subscript[a, n+2])-200 (Subscript[a, n+3])-1000 (Subscript[a, n+4])+3016 (Subscript[a, n+5])+3488 (Subscript[a, n+6])-24256 (Subscript[a, n+7])+23776 (Subscript[a, n+8])+104168 (Subscript[a, n+9])-203408 (Subscript[a, n+10])-184704 (Subscript[a, n+11])+443392 (Subscript[a, n+12])+14336 (Subscript[a, n+13])-151296 (Subscript[a, n+14])+145920 (Subscript[a, n+15])-263424 (Subscript[a, n+16])+317440 (Subscript[a, n+17])+36864 (Subscript[a, n+18])-966656 (Subscript[a, n+19])+573440 (Subscript[a, n+20])+131072 (Subscript[a, n+21])]/.(Subscript[a, n+k_]):>(Subscript[a, n-k])]

SeriesCoefficient[2*(z^5+5*z^6-34*z^7-116*z^8+505*z^9+616*z^10-3179*z^11-4*z^12+9536*z^13-8176*z^14-13392*z^15+15360*z^16+13888*z^17+2784*z^18-3328*z^19-22016*z^20+5120*z^21+2048*z^22)/(1-6*z-64*z^2+200*z^3+1000*z^4-3016*z^5-3488*z^6+24256*z^7-23776*z^8-104168*z^9+203408*z^10+184704*z^11-443392*z^12-14336*z^13+151296*z^14-145920*z^15+263424*z^16-317440*z^17-36864*z^18+966656*z^19-573440*z^20-131072*z^21),{z,0,n}]

Refine[%,n>4]

expr=%5;

ByteCount[expr]

Hamiltonian Paths

3×n

(h=HamiltonianPaths[KnightsTourGraph[3,9],All])//Length//Timing

GeometricallyDistinct[h,{3,9}]//Length

(h=HamiltonianPaths[KnightsTourGraph[3,10],All])//Length//Timing

GeometricallyDistinct[h,{3,10}]//Length

(h=HamiltonianPaths[KnightsTourGraph[3,11],All])//Length//Timing

GeometricallyDistinct[h,{3,11}]//Length

(h=HamiltonianPaths[KnightsTourGraph[3,12],All])//Length//Timing

GeometricallyDistinct[h,{3,12}]//Length

(h=HamiltonianPaths[KnightsTourGraph[3,13],All])//Length//Timing

GeometricallyDistinct[h,{3,13}]//Length

l={0,0,16,0,0,104,792,1120,6096,21344,114496,257728};

FindSequenceFunction[l]

FindSequenceFunction[Drop[l,5]]

FindSequenceFunction/@Transpose[Partition[l,2]]

FindSequenceFunction/@Transpose[Partition[Drop[l,5],2]]

FindLinearRecurrence[l]

FindLinearRecurrence[Drop[l,5]]

FindLinearRecurrence/@Transpose[Partition[Drop[l,5],2]]

FindPolynomialRecurrence[l,5]

FindPolynomialRecurrence[Drop[l,5],2]

FindPolynomialRecurrence[#,3]&/@Transpose[Partition[l,2]]

FindPolynomialRecurrence[#,3]&/@Transpose[Partition[Drop[l,5],2]]

4×n

{8,0,82,744,6378,31088,189688,1213112}2

Flatten[{Last[#],
GeometricallyDistinct[hp=GetGraphData[#,"HP"],Last[#]]//Length,
Length[hp],
GeometricallyDistinct[hc=GetGraphData[#,"HC"],Last[#]]//Length,
Length[hc]
}]&/@Cases[GraphData["KnightsTour"],{_,{4,_}|{_,4}}]//Column

l={0,0,32,0,328,2976,25512,124352,758752,4852448,26735408,145945312,805129880,4334341216,22824469832,119276925152,617722010896,3163151197504,16059782780784,80965219241952,405344545960912};

FindLinearRecurrence[l]

FindLinearRecurrence[Drop[l,4]]

FindLinearRecurrence/@Transpose[Partition[l,2]]

FindLinearRecurrence/@Transpose[Partition[Drop[l,4],2]]

FindPolynomialRecurrence[#,4]&/@Transpose[Partition[l,2]]

FindPolynomialRecurrence[#,3]&/@Transpose[Partition[Drop[l,4],2]]

n×n

Flatten[{Last[#],GraphData[#,"|HP|","|HC|"}]}]&/@Cases[GraphData["KnightsTour"],{_,{n_,n_}}]//Column

Properties 3×n

Circumference

c3=Table[Circumference[KnightTourGraph[3,n]],{n,30}]

Position[Equal@@@Transpose[{c3,3Range[30]}],True,1]//Flatten

Position[Equal@@@Transpose[{c3,3Range[30]-1}],True,1]//Flatten

Position[Equal@@@Transpose[{c3,3Range[30]-2}],True,1]//Flatten

HamiltonianPathCount

A118067

seq=Table[GraphData[{"Knight",Sort[{3,n}]},"HamiltonianPathCount"],{n,10}]

Properties m×n

Acyclic

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{Min[m,n]<3,True}},False],GraphData[#,"Acyclic"]}]&/@GraphData["Knight"],{_,x_,x_}]

AdjacencyMatrixCount

Entity["Graph",{"Knight",{n,n}}]["AdjacencyMatrixCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],(m n)!/Piecewise[{{Max[m,n]!,Min[m,n]==1},{24,m==n==2},{16,m==n==3||(Min[m,n]==2&&Max[m,n]==3)||(Min[m,n]==3&&Max[m,n]==6)},{64,m==n==4||(Min[m,n]==2&&Mod[Max[m,n],2]==1)},{8,m==n||(Min[m,n]==3&&(Max[m,n]==5||Max[m,n]==7))},{384,(Min[m,n]==2&&Mod[Max[m,n],2]==0)}},4],GraphData[#,"AdjacencyMatrixCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

Multinomial[n,n]

Arboricity

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"Arboricity"]}]&/@GraphData["Knight"],{_,x_,x_}]

ArcTransitive

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],False,GraphData[#,"ArcTransitive"]}]&/@GraphData["Knight"],{_,x_,x_}]

ArcTransitivity

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]==1||m==n==2}},Missing["NotApplicable"]],GraphData[#,"ArcTransitivity"]}]&/@GraphData["Knight"],{_,x_,x_}]

AutomorphismCount

Entity["Graph",{"Knight",{n,n}}]["AutomorphismCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{Max[m,n]!,Min[m,n]==1},{24,m==n==2},{16,m==n==3||(Min[m,n]==2&&Max[m,n]==3)||(Min[m,n]==3&&Max[m,n]==6)},{64,m==n==4||(Min[m,n]==2&&Mod[Max[m,n],2]==1)},{8,m==n||(Min[m,n]==3&&(Max[m,n]==5||Max[m,n]==7))},{384,(Min[m,n]==2&&Mod[Max[m,n],2]==0)}},4],GraphData[#,"AutomorphismCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

Table[GroupOrder[GraphAutomorphismGroup[KnightGraph[m,n]]],{n,20}]

Table[n!,{n,20}]

Table[GroupOrder[GraphAutomorphismGroup[KnightGraph[2,n]]],{n,2,20}]

Table[GroupOrder[GraphAutomorphismGroup[KnightGraph[3,n]]],{n,3,20}]

Table[GroupOrder[GraphAutomorphismGroup[KnightGraph[4,n]]],{n,4,20}]

Table[GroupOrder[GraphAutomorphismGroup[KnightGraph[5,n]]],{n,5,20}]

Table[GroupOrder[GraphAutomorphismGroup[KnightGraph[6,n]]],{n,6,20}]

Table[GroupOrder[GraphAutomorphismGroup[KnightGraph[7,n]]],{n,7,20}]

Subtract@@@Flatten[Table[{GroupOrder[GraphAutomorphismGroup[KnightGraph[m,n]]],Piecewise[{{Max[m,n]!,Min[m,n]==1},{24,m==n==2},{16,m==n==3||(Min[m,n]==2&&Max[m,n]==3)||(Min[m,n]==3&&Max[m,n]==6)},{64,m==n==4||(Min[m,n]==2&&Mod[Max[m,n],2]==1)},{8,m==n||(Min[m,n]==3&&(Max[m,n]==5||Max[m,n]==7))},{384,(Min[m,n]==2&&Mod[Max[m,n],2]==0)}},4]},{m,20},{n,20}],1]//Union

PiecewiseExpand[Piecewise[{{Max[m,n]!,Min[m,n]==1},{24,m==n==2},{16,m==n==3||(Min[m,n]==2&&Max[m,n]==3)||(Min[m,n]==3&&Max[m,n]==6)},{64,m==n==4||(Min[m,n]==2&&Mod[Max[m,n],2]==1)},{8,m==n||(Min[m,n]==3&&(Max[m,n]==5||Max[m,n]==7))},{384,(Min[m,n]==2&&Mod[Max[m,n],2]==0)}},4]]

BalabanIndex

Entity["Graph",{"Knight",{n,n}}]["BalabanIndex"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"BalabanIndex"]^2}]&/@GraphData["Knight"],{_,x_,x_}]

Table[GraphData[{"Knight",{2,n}},"BalabanIndex"]^2,{n,2,10}]

FindSequenceFunction[%,n]

Table[GraphData[{"Knight",{3,n}},"BalabanIndex"]^2,{n,3,10}]

FindSequenceFunction[%,n]

Bandwidth

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"Bandwidth"]}]&/@GraphData["Knight"],{_,x_,x_}]

BridgeCount

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{2Max[m,n]-4,Min[m,n]==2}},0],GraphData[#,"BridgeCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

Table[GraphData[{"Knight",Sort@{2,n}},"Graph","Grid"],{n,7}]

BurningNumber

Entity["Graph",{"Knight",{n,n}}]["BurningNumber"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"BurningNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

CharacteristicPolynomial

Entity["Graph",{"Knight",{n,n}}]["CharacteristicPolynomial"]

DeleteCases[{#1,FullSimplify[#2/#3]}&@@@(Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],((#^2-m n) #^(m+n-2)&)[x],GraphData[#,"CharacteristicPolynomial"][x]}]&/@GraphData["Knight"]),{_,-1|1}]

ChordCount

Entity["Graph",{"Knight",{n,n}}]["ChordCount"]

GraphData[{"Knight",{3,4}},"Graph","Labeled"]

Chords[GraphData[{"Knight",{3,4}}]]

GraphData[{"Knight",{3,4}},"Chords"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]<3}},8+4 m n-6 (m+n)-4],GraphData[#,"ChordCount"]}&/@GraphData["Knight"]],{_,x_,x_}]

ChordlessCycleCount

Entity["Graph",{"Knight",{n,n}}]["ChordlessCycleCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Binomial[m,2]Binomial[n,2],GraphData[#,"ChordlessCycleCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

ChromaticInvariant

Entity["Graph",{"Knight",{n,n}}]["ChromaticInvariant"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Sum[k!l! StirlingS2[m-1,k]StirlingS2[n-1,l],{k,0,m-1},{l,0,n-1}],GraphData[#,"ChromaticInvariant"]}]&/@GraphData["Knight"],{_,x_,x_}]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Sum[k! StirlingS2[m-1,k],{k,0,m-1}]Sum[l! StirlingS2[n-1,l],{l,0,n-1}],GraphData[#,"ChromaticInvariant"]}]&/@GraphData["Knight"],{_,x_,x_}]

53030348046942317338336489609/9762238510837560633366673993

Table[GraphData[{"Knight",{1,n}},"ChromaticInvariant"],{n,1,10}]

Table[GraphData[{"Knight",{2,n}},"ChromaticInvariant"],{n,2,10}]

Table[GraphData[{"Knight",{3,n}},"ChromaticInvariant"],{n,3,10}]

(2^n)-3

Table[StirlingS2[n+1,2]-2,{n,3,10}]

Table[GraphData[{"Knight",{4,n}},"ChromaticInvariant"],{n,4,10}]

12StirlingS2[n,3]+1

Table[12StirlingS2[n,3]+1,{n,4,10}]

Table[GraphData[{"Knight",{5,n}},"ChromaticInvariant"],{n,5,10}]

4!

3!

Table[36StirlingS2[n+2,4],{n,4,10}]

ChromaticNumber

Entity["Graph",{"Knight",{n,n}}]["ChromaticNumber"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{1,Min[m,n]==1||m==n==2}},2],GraphData[#,"ChromaticNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

ChromaticPolynomial

Entity["Graph",{"Knight",{n,n}}]["ChromaticPolynomial"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"ChromaticPolynomial"][x]}]&/@GraphData["Knight"],{_,x_,x_}]

Take[poly,5]//Expand//Column

coef=Factor/@FindLinearRecurrence[(poly/(x(x-1)))]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

Circumference

Entity["Graph",{"Knight",{n,n}}]["Circumference"]

FullSimplify[Piecewise[{
{Missing["NotApplicable"],Min[m,n]<3},
{m n-4,Min[m,n]==3&&Max[m,n]==6},
{m n-3,Min[m,n]==3&&Max[m,n]==5},
{m n-2,(Min[m,n]==3&&(Max[m,n]==4||Max[m,n]==8))||Min[m,n]==4},
{m n-1,Mod[m n,2]==1}
},m n]/.m->n]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{
{Missing["NotApplicable"],Min[m,n]<3},
{m n-4,Min[m,n]==3&&Max[m,n]==6},
{m n-3,Min[m,n]==3&&Max[m,n]==5},
{m n-2,(Min[m,n]==3&&(Max[m,n]==4||Max[m,n]==8))||Min[m,n]==4},
{m n-1,Mod[m n,2]==1}
},m n],GraphData[#,"Circumference"]}]&/@GraphData["Knight"],{_,x_,x_}]

Subtract@@@Flatten[Monitor[Table[{
Circumference[KnightTourGraph@@(i={m,n})]/.{}->Missing["NotApplicable"],
Piecewise[{
{Missing["NotApplicable"],Min[m,n]<3},
{m n-4,Min[m,n]==3&&Max[m,n]==6},
{m n-3,Min[m,n]==3&&Max[m,n]==5},
{m n-2,(Min[m,n]==3&&(Max[m,n]==4||Max[m,n]==8))||Min[m,n]==4},
{m n-1,Mod[m n,2]==1}
},m n]},{m,12},{n,12}],i],1]//Union

Select[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],GraphData[#,"Circumference"]}]&/@GraphData["Knight"],#[[2]]===Times@@#[[1]]&][[All,1]]

Select[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],GraphData[#,"Circumference"]}]&/@GraphData["Knight"],#[[2]]+1===Times@@#[[1]]&][[All,1]]

Select[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],GraphData[#,"Circumference"]}]&/@GraphData["Knight"],#[[2]]+2===Times@@#[[1]]&][[All,1]]

Classes

Intersection@@(GraphData[#,"Classes"]&/@GraphData["Knight"])

CliqueCount

Entity["Graph",{"Knight",{n,n}}]["CliqueCount"]

9-12 n+5 (n^2)

9-6 m-6 n+5 m n/.m->n

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],9-6 m-6 n+5 m n,GraphData[#,"CliqueCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

seq=Table[GraphData[{"Knight",{2,n}},"CliqueCount"],{n,2,10}]

FindSequenceFunction[seq,n-1]//Factor

seq=Table[GraphData[{"Knight",{3,n}},"CliqueCount"],{n,3,10}]

FindSequenceFunction[seq,n-2]//Factor

seq=Table[GraphData[{"Knight",{4,n}},"CliqueCount"],{n,4,10}]

FindSequenceFunction[seq,n-3]//Factor

Table[6m-9,{m,4}]

Table[5m-6,{m,4}]

Expand[-(6m-9)+(5m-6)n]

CliqueCoveringNumber

Entity["Graph",{"Knight",{n,n}}]["CliqueCoveringNumber"]

Simplify[(1/4) (1+(((-1))^(1+n))+2 (n^2)),Mod[n,2]==#]&/@{0,1}

Sort[DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{
{Max[m,n],Min[m,n]==1},
{Max[m,n]+1,Min[m,n]==2&&Mod[Max[m,n],2]==1},
{Max[m,n]+2,Min[m,n]==2&&Mod[Max[m,n],2]==0},
{(m n+1)/2,Mod[m n,2]==1}
},m n/2],GraphData[#,"CliqueCoveringNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]]

?CliqueCoveringNumber

Table[CliqueCoveringNumber[KnightTourGraph[2,n]],{n,2,7}]

CliqueNumber

Entity["Graph",{"Knight",{n,n}}]["CliqueNumber"]

Piecewise[{{1,Min[m,n]==1||m==n==2}},2]/.m->n

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{1,Min[m,n]==1||m==n==2}},2],GraphData[#,"CliqueNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

CliquePolynomial

Entity["Graph",{"Knight",{n,n}}]["CliquePolynomial"][x]

FullSimplify[Piecewise[{{1+Max[m,n]x,Min[m,n]==1}},1+m n x+2 x^2 (2 m n-3 m-3 n+4)]/.m->n]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Expand[Piecewise[{{1+Max[m,n]x,Min[m,n]==1}},1+m n x+2 x^2 (2 m n-3 m-3 n+4)]-GraphData[#,"CliquePolynomial"][x]]}]&/@GraphData["Knight"],{_,0}]

ComplementOddChordlessCycleCount

Entity["Graph",{"Knight",{n,n}}]["ComplementOddChordlessCycleCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],0,GraphData[#,"ComplementOddChordlessCycleCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

ConnectedComponentCount

Entity["Graph",{"Knight",{n,n}}]["ConnectedComponentCount"]

FullSimplify[Piecewise[{{Max[m,n],Min[m,n]==1},{4,Min[m,n]==2},{2,m==n==3}},1]/.m->n]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{Max[m,n],Min[m,n]==1},{4,Min[m,n]==2},{2,m==n==3}},1],GraphData[#,"ConnectedComponentCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

Subtract@@@Flatten[Table[{Length[System`ConnectedComponents[KnightTourGraph[m,n]]],Piecewise[{{Max[m,n],Min[m,n]==1},{4,Min[m,n]==2},{2,m==n==3}},1]},{m,20},{n,20}],1]//Union

ConnectedDominatingSetCount

Entity["Graph",{"Knight",{n,n}}]["ConnectedDominatingSetCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"ConnectedDominatingSetCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

ConnectedDominationNumber

Entity["Graph",{"Knight",{n,n}}]["ConnectedDominationNumber"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{1,Min[m,n]==1}},2],GraphData[#,"ConnectedDominationNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

ConnectedDominationPolynomial

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Expand[Piecewise[{{2 x+x^2,m==n==1},{x+((x+1)^m-1) ((x+1)^n-1),Min[m,n]==1}},((x+1)^m-1) ((x+1)^n-1)]-GraphData[#,"ConnectedDominationPolynomial"][x]]}]&/@GraphData["Knight"],{_,0}]

ConnectedInducedSubgraphCount

Entity["Graph",{"Knight",{n,n}}]["ConnectedInducedSubgraphCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],(2^m-1) (2^n-1)+m+n,GraphData[#,"ConnectedInducedSubgraphCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

ConnectedInducedSubgraphPolynomial

Entity["Graph",{"Knight",{n,n}}]["ConnectedInducedSubgraphPolynomial"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Expand[((x+1)^m-1) ((x+1)^n-1)+(m+n) x-GraphData[#,"ConnectedInducedSubgraphPolynomial"][x]]}]&/@GraphData["Knight"],{_,0}]

CrossingNumber

Entity["Graph",{"Knight",{n,n}}]["CrossingNumber"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Floor[n/2]Floor[(n-1)/2]Floor[m/2]Floor[(m-1)/2],GraphData[#,"CrossingNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

CycleCount

Entity["Graph",{"Knight",{n,n}}]["CycleCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],1/2 Sum[k! l! Binomial[m,k]Binomial[n,l],{k,2,m},{l,2,n}],GraphData[#,"CycleCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

Table[GraphData[{"Knight",{m,n}},"CycleCount"],{n,10},{m,n}]//Column

Table[GraphData[{"Knight",{2,n}},"CycleCount"],{n,2,10}]

FindSequenceFunction[%,n-1]

Table[GraphData[{"Knight",{3,n}},"CycleCount"],{n,3,10}]

FindSequenceFunction[%,n-2]//FullSimplify

Table[GraphData[{"Knight",{4,n}},"CycleCount"],{n,4,10}]

FindSequenceFunction[%,n-3]//Factor

CyclePolynomial

Entity["Graph",{"Knight",{n,n}}]["CyclePolynomial"]

Cyclic

Entity["Graph",{"Knight",{n,n}}]["Cyclic"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{False,Min[m,n]<3}},True],GraphData[#,"Cyclic"]}]&/@GraphData["Knight"],{_,x_,x_}]

CyclomaticNumber

Entity["Graph",{"Knight",{n,n}}]["CyclomaticNumber"]

FullSimplify[Piecewise[{{0,Min[m,n]==1},{12+3 m n-6 (m+n),Min[m,n]==2},{10+3 m n-6 (m+n),m==n==3}},9+3 m n-6 (m+n)]/.m->n,n>0]

FullSimplify[Subtract@@Entity["Graph",{"Knight",{m,n}}][{"EdgeCount","VertexCount"}]+Piecewise[{{Max[m,n],Min[m,n]==1},{4,Min[m,n]==2},{2,m==n==3}},1]]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]==1},{12+3 m n-6 (m+n),Min[m,n]==2},{10+3 m n-6 (m+n),m==n==3}},9+3 m n-6 (m+n)],GraphData[#,"CyclomaticNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

DetourIndex

Entity["Graph",{"Knight",{n,n}}]["DetourIndex"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{n (2-5 n+4 (n^2)),m==n}},Missing["NotAvailable"]],GraphData[#,"DetourIndex"]}]&/@GraphData["Knight"],{_,x_,x_}]

DetourMatrix

Entity["Graph",{"Knight",{n,n}}]["DetourMatrix"]

MatrixForm/@(d1=Table[GraphData[{"Knight",{n,n}},"DetourMatrix"],{n,5}])

MatrixForm/@(d2=Table[SparseArray[{{i_,i_}->0,{i_,j_}/;((i≤n&&j≤n)||(i>n&&j>n))->2 n-2},2 n,2 n-1],{n,5}])

d1-d2

DetourPolynomial

Entity["Graph",{"Knight",{n,n}}]["DetourPolynomial"]

Diameter

Entity["Graph",{"Knight",{n,n}}]["Diameter"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{Infinity,Min[m,n]<3||m==n==3}}],GraphData[#,"Diameter"]}]&/@GraphData["Knight"],{_,x_,x_}]

DistanceMatrix

Entity["Graph",{"Knight",{n,n}}]["DistanceMatrix"]

MatrixForm/@Table[GraphData[{"Knight",{n,n}},"DistanceMatrix"],{n,5}]

MatrixForm/@Table[With[{z=ConstantArray[2,n {1,1}],o=ConstantArray[1,n {1,1}]},ArrayFlatten[{{z,o},{o,z}}]]-2 IdentityMatrix[2 n],{n,5}]

DistancePolynomial

Entity["Graph",{"Knight",{n,n}}]["DistancePolynomial"]

DistinguishingNumber

Entity["Graph",{"Knight",{n,n}}]["DistinguishingNumber"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{n+1,m==n}},Max[m,n]],GraphData[#,"DistinguishingNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

DomaticNumber

Block[{m,n},Sort[{{m,n}="Knight"/.GraphData[#,"NotationRules"],GraphData[#,"DomaticNumber"],XXX}&/@GraphData["Knight"]]]

DeleteCases[%,{_,x_,x_}]

DominatingSetCount

Entity["Graph",{"Knight",{n,n}}]["DominatingSetCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],3-(2^m)-(2^n)+(2^(m+n)),GraphData[#,"DominatingSetCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

DomaticNumber

DeleteCases[Block[{m,n},Sort[{{m,n}="Knight"/.GraphData[#,"NotationRules"],GraphData[#,"DomaticNumber"],Piecewise[{{1,Min[m,n]==1||m==n==2||m==n==3||(Min[m,n]==2&&Max[m,n]==3)},{2,Min[m,n]==2}},3]}&/@GraphData["Knight"]]],{_,x_,x_}]

DominationPolynomial

Entity["Graph",{"Knight",{n,n}}]["DominationPolynomial"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Expand[(((1+#)^m-1) ((1+#)^n-1)+#^m+#^n&)[x]-GraphData[#,"DominationPolynomial"][x]]}]&/@GraphData["Knight"],{_,0}]

EdgeChromaticNumber

Entity["Graph",{"Knight",{n,n}}]["EdgeChromaticNumber"]

FullSimplify[Piecewise[{{0,Min[m,n]==1||m==n==2},{1,Min[m,n]==2&&Max[m,n]==3},{2,Min[m,n]==2||m==n==3},{3,Min[m,n]==3&&Max[m,n]==4},{4,Min[m,n]==3||m==n==4},{6,Min[m,n]==4}},8]/.m->n]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]==1||m==n==2},{1,Min[m,n]==2&&Max[m,n]==3},{2,Min[m,n]==2||m==n==3},{3,Min[m,n]==3&&Max[m,n]==4},{4,Min[m,n]==3||m==n==4},{6,Min[m,n]==4}},8],GraphData[#,"EdgeChromaticNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

Combinatorica:

Table[EdgeChromaticNumber[KnightsTourGraph[m,n]],{m,4},{n,4}]//Timing

Built-in:

Table[EdgeChromaticNumber[KnightTourGraph[m,n]],{m,4},{n,4}]//Timing

EdgeConnectivity

Entity["Graph",{"Knight",{n,n}}]["EdgeConnectivity"]

FullSimplify[Piecewise[{{Missing["NotApplicable"],m==n==1},{0,Min[m,n]<3||m==n==3}},2]/.m->n]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{Missing["NotApplicable"],m==n==1},{0,Min[m,n]<3||m==n==3}},2],GraphData[#,"EdgeConnectivity"]}]&/@GraphData["Knight"],{_,x_,x_}]

EdgeCount

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

FullSimplify[8+4 m n-6 (m+n)/.m->n]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],8+4 m n-6 (m+n),GraphData[#,"EdgeCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

EdgeCoverCount

Entity["Graph",{"Knight",{n,n}}]["EdgeCoverCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],m n,GraphData[#,"EdgeCoverCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

EdgeCoverNumber

Entity["Graph",{"Knight",{n,n}}]["EdgeCoverNumber"]

FullSimplify[Piecewise[{
{0,Min[m,n]==1||(Min[m,n]==2&&Max[m,n]<4)||m==n==3},
{Max[m,n]+1,Min[m,n]==2&&Mod[Max[m,n],2]==1},
{4Round[(Max[m,n]+1)/4],Min[m,n]==2&&Mod[Max[m,n],2]==0}
},
Ceiling[m n/2]]/.m->n]

Sort@DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{
{0,Min[m,n]==1||(Min[m,n]==2&&Max[m,n]<4)||m==n==3},
{Max[m,n]+1,Min[m,n]==2&&Mod[Max[m,n],2]==1},
{4Round[(Max[m,n]+1)/4],Min[m,n]==2&&Mod[Max[m,n],2]==0}
},
Ceiling[m n/2]],GraphData[#,"EdgeCoverNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

Table[Round[(n-1)/4],{n,30}]

Table[Length@Flatten@FindEdgeCover[KnightTourGraph[2,n]],{n,50}]

Table[Piecewise[{{0,n<4},{n+1,Mod[n+1,2]==0}},4Round[(n+1)/4]],{n,50}]

%==%%

EdgeCoverPolynomial

Entity["Graph",{"Knight",{n,n}}]["EdgeCoverPolynomial"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Expand[(Sum[(-1)^\[FormalK] Binomial[m,\[FormalK]] ((#+1)^(m-\[FormalK])-1)^n,{\[FormalK],0,m}]&)[x]-GraphData[#,"EdgeCoverPolynomial"][x]]}]&/@GraphData["Knight"],{_,0}]

EulerianCycleCount

Entity["Graph",{"Knight",{n,n}}]["EulerianCycleCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],0,GraphData[#,"EulerianCycleCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

KnightTourGraph[3,3]

FaceCount

Entity["Graph",{"Knight",{n,n}}]["FaceCount"]

FullSimplify[Piecewise[{{0,Min[m,n]<3},{1,m==n==3},{4,Min[m,n]==3&&Max[m,n]==4},{7,Min[m,n]==3&&Max[m,n]==5}},Missing["NotApplicable"]]/.m->n]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]<3},{1,m==n==3},{4,Min[m,n]==3&&Max[m,n]==4},{7,Min[m,n]==3&&Max[m,n]==5}},Missing["NotApplicable"]],GraphData[#,"FaceCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

FibonacciCube

Entity["Graph",{"Knight",{m,n}}]["FibonacciCube"]

GraphData[{"Knight","FibonacciCube"}]

FlowPolynomial

Entity["Graph",{"Knight",{n,n}}]["FlowPolynomial"]

FractionalChromaticNumber

Entity["Graph",{"Knight",{n,n}}]["FractionalChromaticNumber"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{1,Min[m,n]==1||m==n==2}},2],GraphData[#,"FractionalChromaticNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

FractionalEdgeChromaticNumber

Entity["Graph",{"Knight",{n,n}}]["FractionalEdgeChromaticNumber"]

Sort@DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]==1||m==n==2},{1,Min[m,n]==2&&Max[m,n]==3},{2,Min[m,n]==2||m==n==3},{3,Min[m,n]==3&&Max[m,n]==4},{4,Min[m,n]==3||m==n==4},{6,Min[m,n]==4}},8],GraphData[#,"FractionalEdgeChromaticNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

Girth

Entity["Graph",{"Knight",{n,n}}]["Girth"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{Infinity,Min[m,n]<3},{6,Min[m,n]==3&&Max[m,n]==4},{8,m==n==3||(Min[m,n]==3&&Max[m,n]==4)}},4],GraphData[#,"Girth"]}]&/@GraphData["Knight"],{_,x_,x_}]

Gonality

Entity["Graph",{"Knight",{n,n}}]["Gonality"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Min[m,n],GraphData[#,"Gonality"]}]&/@GraphData["Knight"],{_,x_,x_}]

HamiltonConnected

Entity["Graph",{"Knight",{n,n}}]["HamiltonConnected"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{True,m==n==1}},False],GraphData[#,"HamiltonConnected"]}]&/@GraphData["Knight"],{_,x_,x_}]

HamiltonDecompositionCount

Entity["Graph",{"Knight",{n,n}}]["HamiltonDecompositionCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{1,m==n==1}},Missing["NotApplicable"]],GraphData[#,"HamiltonDecompositionCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

Hamiltonian

Entity["Graph",{"Knight",{n,n}}]["Hamiltonian"]

Sort@DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{True,m==n==1},{False,Min[m,n]<3||(Min[m,n]==3&&Max[m,n]>3)||(m==n&&Mod[n,2]==1)}},True],GraphData[#,"Hamiltonian"]}]&/@GraphData["Knight"],{_,x_,x_}]

HamiltonianCycleCount

Entity["Graph",{"Knight",{n,n}}]["HamiltonianCycleCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{n! (n-1)!/2,m>1&&m==n}},0],GraphData[#,"HamiltonianCycleCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

HamiltonianPathCount

2×n

seq=Table[GraphData[{"Knight",Sort[{n,2}]},"HamiltonianPathCount"],{n,10}]

3×n

A118067

Table[GraphData[{"Knight",Sort[{n,3}]},"HamiltonianPathCount"],{n,10}]

seq={0,0,0,16,0,0,104,792,1120,6096,21344,114496,257728,1292544,3677568,17273760,46801984,211731376,611507360,2645699504,7725948608,32451640000,97488160384,397346625760,1214082434112,4835168968464,15039729265856,58641619298000}/2

FindLinearRecurrence[seq]

FindLinearRecurrence[Drop[seq,3]]

FindLinearRecurrence[Drop[seq,5]]

FindLinearRecurrence[Drop[seq,10]]

FindSequenceFunction[Drop[seq,3],n-3]

gf=(x^4) FindGeneratingFunction[Drop[seq,3],x]

4×n

A079137

seq=Table[GraphData[{"Knight",Sort[{n,4}]},"HamiltonianPathCount"],{n,10}]

seq=Import["https://oeis.org/A079137/b079137.txt","Table"][[All,2]]

FindLinearRecurrence[Drop[seq,3]]//Head

FindLinearRecurrence[Drop[seq,5]]//Head

FindLinearRecurrence[Drop[seq,10]]//Head

FindSequenceFunction[Drop[seq,3],n-3]

gf=(x^4) FindGeneratingFunction[Drop[seq,3],x]

5×n

A083386

Table[GraphData[{"Knight",Sort[{n,5}]},"HamiltonianPathCount"],{n,10}]

seq=Import["https://oeis.org/A083386/b083386.txt","Table"][[All,2]]

FindLinearRecurrence[seq]

FindLinearRecurrence[Drop[seq,3]]

FindLinearRecurrence[Drop[seq,5]]

FindLinearRecurrence[Drop[seq,10]]

FindSequenceFunction[Drop[seq,3]]

gf=x FindGeneratingFunction[seq,x]

6×n

seq=Table[GraphData[{"Knight",Sort[{n,6}]},"HamiltonianPathCount"],{n,10}]

2{744,18784}

HamiltonianNumber

Entity["Graph",{"Knight",{n,n}}]["HamiltonianNumber"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{2n,m ==n||Min[m,n]==1},{m n,Min[m,n]==2}},m+n+Abs[m-n]],GraphData[#,"HamiltonianNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

HamiltonianPathCount

Entity["Graph",{"Knight",{n,n}}]["HamiltonianPathCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{n!^2,m==n},{n!m!/2,n==m+1}},0],GraphData[#,"HamiltonianPathCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

Table[GraphData[{"Knight",{n,n+1}},"HamiltonianPathCount"],{n,9}]

FindSequenceFunction[%,n]//FunctionExpand

Table[n!(n+1)!/2,{n,9}]

HamiltonianWalkCount

Entity["Graph",{"Knight",{n,n}}]["HamiltonianWalkCount"]

HararyIndex

Entity["Graph",{"Knight",{n,n}}]["HararyIndex"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],(1/4)((m^2)+(n^2)-(m+n))+m n,GraphData[#,"HararyIndex"]}]&/@GraphData["Knight"],{_,x_,x_}]

HexagonCount

Entity["Graph",{"Knight",{n,n}}]["HexagonCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"HexagonCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

Table[GraphCycleCount[KnightTourGraph[2,n],6],{n,20}]

Table[GraphCycleCount[KnightTourGraph[3,n],6],{n,20}]

FindSequenceFunction[Drop[%,4],n-4]//Simplify

Table[GraphCycleCount[KnightTourGraph[4,n],6],{n,20}]

FindSequenceFunction[Drop[%,5],n-5]//Simplify

Table[GraphCycleCount[KnightTourGraph[5,n],6],{n,20}]

FindSequenceFunction[Drop[%,5],n-5]//Simplify

Table[GraphCycleCount[KnightTourGraph[6,n],6],{n,20}]

FindSequenceFunction[Drop[%,5],n-5]//Simplify

Table[GraphCycleCount[KnightTourGraph[7,n],6],{n,20}]

FindSequenceFunction[Drop[%,5],n-5]//Simplify

Table[GraphCycleCount[KnightTourGraph[8,n],6],{n,20}]

FindSequenceFunction[Drop[%,5],n-5]//Expand

Table[GraphCycleCount[KnightTourGraph[9,n],6],{n,20}]

FindSequenceFunction[Drop[%,5],n-5]//Expand

Table[GraphCycleCount[KnightTourGraph[10,n],6],{n,20}]

FindSequenceFunction[Drop[%,5],n-5]//Expand

Table[GraphCycleCount[KnightTourGraph[11,n],6],{n,20}]

FindSequenceFunction[Drop[%,5],n-5]//Expand

Table[GraphCycleCount[KnightTourGraph[12,n],6],{n,20}]

FindSequenceFunction[Drop[%,5],n-5]//Expand

FindSequenceFunction[Drop[{42,250,660,1172,1690,2208,2726,3244,3762,4280},0],n]//FullSimplify

FindSequenceFunction[Drop[{10,61,164,298,434,570,706,842,978,1114},0],n]//FullSimplify

FunctionExpand[%]

IdiosyncraticPolynomial

Entity["Graph",{"Knight",{n,n}}]["IdiosyncraticPolynomial"]

Expand[(x+y+n (1-y)) (x+y-n (1+y))]

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

FullSimplify[(x+y)^(-2+2 n) (x+y+n (1-y)) (x+y-n (1+y))-(((x+y))^(-2+2 n)) (n+x+y-n y) (x+y-n (1+y))]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],FullSimplify@Expand[(x+y)^(m+n-2) (x^2+(2-m-n)x y+y^2(m-1)(n-1)-m n)/GraphData[#,"IdiosyncraticPolynomial"][x,y]]}]&/@GraphData["Knight"],{_,x_,x_}]

IncidenceMatrix

Entity["Graph",{"Knight",{n,n}}]["IncidenceMatrix"]

MatrixForm/@Table[GraphData[{"Knight",{n,n}},"IncidenceMatrix"],{n,5}]

IndependenceNumber

A287797

Entity["Graph",{"Knight",{n,n}}]["IndependenceNumber"]

FullSimplify[%,Mod[n,2]==#]&/@{0,1}

(seq=Table[IndependenceNumber[KnightTourGraph[m,n]],{n,11},{m,n}])//Column

Flatten[seq]

A030978

seq[[All,-1]]

Table[IndependenceNumber[KnightTourGraph[n,n]],{n,10}]

A201629

Rest[seq][[All,2]]

Table[IndependenceNumber[KnightTourGraph[2,n]],{n,10}]

Sort@DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{
{Max[m,n],Min[m,n]==1},
{Max[m,n]+1,Min[m,n]==2&&Mod[Max[m,n],2]==1},
{4Round[(Max[m,n]+1)/4],Min[m,n]==2&&Mod[Max[m,n],2]==0},
{m n/2,Mod[m n,2]==0},
{(m n+1)/2,Mod[m n,2]==1}}],GraphData[#,"IndependenceNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

Table[IndependenceNumber[KnightTourGraph[2,n]],{n,20}]

Table[Piecewise[{{n+1,Mod[n,2]==1}},4Round[(n+1)/4]],{n,20}]

DeleteCases[Flatten[Table[{{m,n},Piecewise[{
{Max[m,n],Min[m,n]==1},
{Max[m,n]+1,Min[m,n]==2&&Mod[Max[m,n],2]==1},
{4Round[(Max[m,n]+1)/4],Min[m,n]==2&&Mod[Max[m,n],2]==0},
{m n/2,Mod[m n,2]==0},
{(m n+1)/2,Mod[m n,2]==1}}],IndependenceNumber[KnightTourGraph[m,n]]},{m,20},{n,20}],1],{_,x_,x_}]

Table[Piecewise[{
{Max[m,n],Min[m,n]==1},
{Max[m,n]+1,Min[m,n]==2&&Mod[Max[m,n],2]==1},
{4Round[(Max[m,n]+1)/4],Min[m,n]==2&&Mod[Max[m,n],2]==0},
{m n/2,Mod[m n,2]==0},
{(m n+1)/2,Mod[m n,2]==1}}],{n,10},{m,n}]//Flatten

Table[IndependenceNumber[KnightTourGraph[m,n]],{n,10},{m,n}]//Flatten

IndependencePolynomial

Entity["Graph",{"Knight",{n,n}}]["IndependencePolynomial"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Expand[(1+x)^m+(1+x)^n-1-GraphData[#,"IndependencePolynomial"][x]]}]&/@GraphData["Knight"],{_,0}]

IndependenceRatio

Entity["Graph",{"Knight",{n,n}}]["IndependenceRatio"]

Entity["Graph",{"Knight",{m,n}}]["EdgeCount"]

Sort@DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{
{Max[m,n],Min[m,n]==1},
{Max[m,n]+1,Min[m,n]==2&&Mod[Max[m,n],2]==1},
{4Round[(Max[m,n]+1)/4],Min[m,n]==2&&Mod[Max[m,n],2]==0},
{m n/2,Mod[m n,2]==0},
{(m n+1)/2,Mod[m n,2]==1}}]/(m n),GraphData[#,"IndependenceRatio"]}]&/@GraphData["Knight"],{_,x_,x_}]

IndependentEdgeSetCount

Entity["Graph",{"Knight",{n,n}}]["IndependentEdgeSetCount"]

Table[GraphData[{"Knight",{m,n}},"IndependentEdgeSetCount"],{n,10},{m,n}]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],m!LaguerreL[m,n-m,-1],GraphData[#,"IndependentEdgeSetCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

IndependentVertexSetCount

Entity["Graph",{"Knight",{n,n}}]["IndependentVertexSetCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],(2^m)+(2^n)-1,GraphData[#,"IndependentVertexSetCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

IntersectionNumber

Entity["Graph",{"Knight",{n,n}}]["IntersectionNumber"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"IntersectionNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

KirchhoffIndex

Entity["Graph",{"Knight",{n,n}}]["KirchhoffIndex"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],((((m^2)+(n^2))(m+n-1))/(m n))-1,GraphData[#,"KirchhoffIndex"]}]&/@GraphData["Knight"],{_,x_,x_}]

KirchhoffSumIndex

Entity["Graph",{"Knight",{n,n}}]["KirchhoffSumIndex"]

LaplacianMatrix

Entity["Graph",{"Knight",{n,n}}]["LaplacianMatrix"]

MatrixForm/@Table[GraphData[{"Knight",{n,n}},"LaplacianMatrix"],{n,5}]

MatrixForm/@Table[With[{z=ConstantArray[0,n {1,1}],o=ConstantArray[-1,n {1,1}]},ArrayFlatten[{{z,o},{o,z}}]]+n IdentityMatrix[2 n],{n,5}]

LaplacianPolynomial

Entity["Graph",{"Knight",{n,n}}]["LaplacianPolynomial"]

FullSimplify[(x-m-n)(((x-m))^(n-1))(((x-n))^(m-1))x/.m->n]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Expand[(x-m-n)(((x-m))^(n-1))(((x-n))^(m-1))x/GraphData[#,"LaplacianPolynomial"][x]]}]&/@GraphData["Knight"],{_,-1|1}]

LeafCount

Entity["Graph",{"Knight",{n,n}}]["LeafCount"]

Sort@DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,m==n==2},{4,Min[m,n]==2&&Max[m,n]==3},{8,Min[m,n]==2}},0],GraphData[#,"LeafCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

LongestCycleCount

Entity["Graph",{"Knight",{n,n}}]["LongestCycleCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]==1}},(((Min[m,n]-1)! Max[m,n]!)/(2 Abs[n-m]!))],GraphData[#,"LongestCycleCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

LovaszNumber

Entity["Graph",{"Knight",{n,n}}]["LovaszNumber"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Max[m,n],GraphData[#,"LovaszNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

LucasCube

Entity["Graph",{"Knight",{m,n}}]["LucasCube"]

GraphData[{"Knight","LucasCube"}]

MatchingGeneratingPolynomial

Entity["Graph",{"Knight",{n,n}}]["MatchingGeneratingPolynomial"]

Factor[Table[(x^m)m!LaguerreL[m,n-m,-1/x],{n,5},{m,n}]]

Expand[Table[GraphData[{"Knight",{m,n}},"MatchingGeneratingPolynomial"][x]-(x^m)m!LaguerreL[m,n-m,-1/x],{n,10},{m,n}]]

MatchingNumber

Entity["Graph",{"Knight",{n,n}}]["MatchingNumber"]

(seq=Table[MatchingNumber[KnightTourGraph[m,n]],{n,11},{m,n}])//Column

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]==1},{Max[m,n]-1,Min[m,n]==2&&Mod[Max[m,n],2]==1},{Max[m,n]-2,Min[m,n]==2&&Mod[Max[m,n],4]==2},{m n/2,Mod[m n,2]==0},{(m n-1)/2,Mod[m n,2]==1}}],GraphData[#,"MatchingNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

DeleteCases[Flatten[Table[{
{m,n},
Piecewise[{{0,Min[m,n]==1},{Max[m,n]-1,Min[m,n]==2&&Mod[Max[m,n],2]==1},{Max[m,n]-2,Min[m,n]==2&&Mod[Max[m,n],4]==2},{m n/2,Mod[m n,2]==0},{(m n-1)/2,Mod[m n,2]==1}}],
MatchingNumber[KnightTourGraph[m,n]]},{m,20},{n,20}],1],{_,x_,x_}]

MatchingPolynomial

Entity["Graph",{"Knight",{n,n}}]["MatchingPolynomial"]

Table[GraphData[{"Knight",{m,n}},"MatchingPolynomial"][x],{n,5},{m,n}]

Table[Expand[GraphData[{"Knight",{m,n}},"MatchingPolynomial"][x]-(((-1))^m)(x^(n-m))m!LaguerreL[m,n-m,(x^2)]],{n,10},{m,n}]

MaximalCliqueCount

Entity["Graph",{"Knight",{n,n}}]["MaximalCliqueCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],m n,GraphData[#,"MaximalCliqueCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

MaximalIndependentEdgeSetCount

Entity["Graph",{"Knight",{n,n}}]["MaximalIndependentEdgeSetCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],((Max[m,n]!)/(Abs[n-m]!)),GraphData[#,"MaximalIndependentEdgeSetCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

MaximalIndependentVertexSetCount

Entity["Graph",{"Knight",{n,n}}]["MaximalIndependentVertexSetCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],2,GraphData[#,"MaximalIndependentVertexSetCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

MaximumCliqueCount

Entity["Graph",{"Knight",{n,n}}]["MaximumCliqueCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],m n,GraphData[#,"MaximumCliqueCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

MaximumIndependentEdgeSetCount

Entity["Graph",{"Knight",{n,n}}]["MaximumIndependentEdgeSetCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],((Max[m,n]!)/(Abs[n-m]!)),GraphData[#,"MaximumIndependentEdgeSetCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

MaximumIndependentVertexSetCount

Entity["Graph",{"Knight",{n,n}}]["MaximumIndependentVertexSetCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{2,m==n}},1],GraphData[#,"MaximumIndependentVertexSetCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

MaximumLeafNumber

Entity["Graph",{"Knight",{n,n}}]["MaximumLeafNumber"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{2,m==n==1},{m+n-1,Min[m,n]==1}},m+n-2],GraphData[#,"MaximumLeafNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

MaximumVertexDegree

Entity["Graph",{"Knight",{n,n}}]["MaximumVertexDegree"]

Sort@DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{
{0,Min[m,n]==1||m==n==2},
{1,Min[m,n]==2&&(Max[m,n]==3||Max[m,n]==4)},
{2,Min[m,n]==2||m==n==3},
{3,m==n==3||(Min[m,n]==3&&Max[m,n]==4)},
{4,m==n==4||Min[m,n]==3},
{6,Min[m,n]==4}
},8],GraphData[#,"MaximumVertexDegree"]}]&/@GraphData["Knight"],{_,x_,x_}]

DeleteCases[Flatten[Table[{
{m,n},
Piecewise[{
{0,Min[m,n]==1||m==n==2},
{1,Min[m,n]==2&&(Max[m,n]==3||Max[m,n]==4)},
{2,Min[m,n]==2||m==n==3},
{3,m==n==3||(Min[m,n]==3&&Max[m,n]==4)},
{4,m==n==4||Min[m,n]==3},
{6,Min[m,n]==4}
},8],
Max@VertexDegree[KnightTourGraph[m,n]]},{m,20},{n,20}],1],{_,x_,x_}]

MeanDistance

Entity["Graph",{"Knight",{n,n}}]["MeanDistance"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],2 (m^2+n^2+m n-(m+n))/(m+n)^2,GraphData[#,"MeanDistance"]}]&/@GraphData["Knight"],{_,x_,x_}]

MinimalDominatingSetCount

Block[{m,n},Sort[{{m,n}="Knight"/.GraphData[#,"NotationRules"],GraphData[#,"MinimalDominatingSetCount"],XXX}&/@GraphData["Knight"]]]

DeleteCases[%,{_,x_,x_}]

MinimumCliqueCoveringCount

Entity["Graph",{"Knight",{n,n}}]["MinimumCliqueCoveringCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Min[m,n]!StirlingS2[Max[m,n],Min[m,n]],GraphData[#,"MinimumCliqueCoveringCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

MinimumConnectedDominatingSetCount

Entity["Graph",{"Knight",{n,n}}]["MinimumConnectedDominatingSetCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{2,m==n==1},{1,Min[m,n]==1}},m n],GraphData[#,"MinimumConnectedDominatingSetCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

MinimumDistinguishingLabelingCount

Entity["Graph",{"Knight",{n,n}}]["MinimumDistinguishingLabelingCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{2,m==n==1},{1,Min[m,n]==1}},m n],GraphData[#,"MinimumDistinguishingLabelingCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

MinimumDominatingSetCount

Entity["Graph",{"Knight",{n,n}}]["MinimumDominatingSetCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{2,m==n==1},{6,m==n==2},{1,Min[m,n]==1},{m n+1,Min[m,n]==2}},m n],GraphData[#,"MinimumDominatingSetCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

MinimumEdgeCoverCount

Entity["Graph",{"Knight",{n,n}}]["MinimumEdgeCoverCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Min[m,n]!StirlingS2[Max[m,n],Min[m,n]],GraphData[#,"MinimumEdgeCoverCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

MinimumVertexDegree

Entity["Graph",{"Knight",{n,n}}]["MinimumVertexDegree"]

Sort@DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]==1||m==n==2||m==n==3||(Min[m,n]==2&&Max[m,n]==3)},{1,Min[m,n]==2}},2],GraphData[#,"MinimumVertexDegree"]}]&/@GraphData["Knight"],{_,x_,x_}]

DeleteCases[Flatten[Table[{
{m,n},
Piecewise[{{0,Min[m,n]==1||m==n==2||m==n==3||(Min[m,n]==2&&Max[m,n]==3)},{1,Min[m,n]==2}},2],
Min@VertexDegree[KnightTourGraph[m,n]]},{m,20},{n,20}],1],{_,x_,x_}]

MolecularTopologicalIndex

Entity["Graph",{"Knight",{n,n}}]["MolecularTopologicalIndex"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],4m n(m +n-1),GraphData[#,"MolecularTopologicalIndex"]}]&/@GraphData["Knight"],{_,x_,x_}]

Nonhamiltonian

Entity["Graph",{"Knight",{n,n}}]["Nonhamiltonian"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"Nonhamiltonian"]}]&/@GraphData["Knight"],{_,x_,x_}]

NormalizedLaplacianMatrix

Entity["Graph",{"Knight",{n,n}}]["NormalizedLaplacianMatrix"]

MatrixForm/@Table[GraphData[{"Knight",{n,n}},"NormalizedLaplacianMatrix"],{n,5}]

MatrixForm/@Table[With[{i=IdentityMatrix[n],c=ConstantArray[-1/n,{n,n}]},ArrayFlatten[{{i,c},{c,i}}]],{n,5}]

OddChordlessCycleCount

Entity["Graph",{"Knight",{n,n}}]["OddChordlessCycleCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],0,GraphData[#,"OddChordlessCycleCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

PathCount

Entity["Graph",{"Knight",{n,n}}]["PathCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"PathCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

Table[GraphData[{"Knight",{m,n}},"CycleCount"],{n,10},{m,n}]//Column

Table[GraphData[{"Knight",{2,n}},"CycleCount"],{n,2,10}]

FindSequenceFunction[%,n-1]

Table[GraphData[{"Knight",{3,n}},"CycleCount"],{n,3,10}]

FindSequenceFunction[%,n-2]//FullSimplify

Table[GraphData[{"Knight",{4,n}},"CycleCount"],{n,4,10}]

FindSequenceFunction[%,n-3]//Factor

PathPolynomial

Entity["Graph",{"Knight",{n,n}}]["PathPolynomial"]

Pell

Entity["Graph",{"Knight",{m,n}}]["Pell"]

GraphData[{"Knight","Pell"}]

PentagonCount

Entity["Graph",{"Knight",{n,n}}]["PentagonCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],0,GraphData[#,"PentagonCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

Perfect

Entity["Graph",{"Knight",{n,n}}]["Perfect"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],True,GraphData[#,"Perfect"]}]&/@GraphData["Knight"],{_,x_,x_}]

ProjectivePlaneCrossingNumber

Entity["Graph",{"Knight",{n,n}}]["ProjectivePlaneCrossingNumber"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]<3}},Missing["NotAvailable"]],GraphData[#,"ProjectivePlaneCrossingNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

Radius

Entity["Graph",{"Knight",{n,n}}]["Radius"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,m==n==1},{Infinity,Min[m,n]<3||m==n==3},{Floor[((2+n)/2)]-Floor[((2+n)/6)],m==n&&Min[m,n]>7}},4],GraphData[#,"Radius"]}]&/@GraphData["Knight"],{_,x_,x_}]

RankPolynomial

Entity["Graph",{"Knight",{n,n}}]["RankPolynomial"]

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"RankPolynomial"][x,y],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

RectilinearCrossingNumber

Entity["Graph",{"Knight",{n,n}}]["RectilinearCrossingNumber"]

seq=Table[GraphData[{"Knight",{n,n}},"RectilinearCrossingNumber"],{n,20}]

ReliabilityPolynomial

Entity["Graph",{"Knight",{n,n}}]["ReliabilityPolynomial"]

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"ReliabilityPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

ResistanceMatrix

Entity["Graph",{"Knight",{n,n}}]["ResistanceMatrix"]

MatrixForm/@Table[GraphData[{"Knight",{n,n}},"ResistanceMatrix"],{n,6}]

SigmaPolynomial

Entity["Graph",{"Knight",{n,n}}]["SigmaPolynomial"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Expand[Subtract@@{(x^(m+n)) BellB[m,1/x] BellB[n,1/x],GraphData[#,"SigmaPolynomial"][x]}]}]&/@GraphData["Knight"],{_,0}]

SpanningTreeCount

Entity["Graph",{"Knight",{n,n}}]["SpanningTreeCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],m^(n-1)*n^(m-1),GraphData[#,"SpanningTreeCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

SquareCount

Entity["Graph",{"Knight",{n,n}}]["SquareCount"]

Factor/@Simplify[Piecewise[{{0,m<3||m==n==3},{n-4,m==3}},6(m-3)(n-3)-2]/.m->n]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]<3}}],GraphData[#,"SquareCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

Table[GraphCycleCount[KnightGraph[3,n],4],{n,3,20}]

FindSequenceFunction[%,n-2]//Factor

Table[GraphCycleCount[KnightGraph[4,n],4],{n,20}]

FindSequenceFunction[Drop[%,3],n]//Factor

Table[GraphCycleCount[KnightGraph[5,n],4],{n,20}]

FindSequenceFunction[Drop[%,3],n]//Factor

Table[GraphCycleCount[KnightGraph[6,n],4],{n,20}]

FindSequenceFunction[Drop[%,3],n]//Factor

Table[9k-26,{k,4,6}]

Table[3k,{k,5}]

FullSimplify[2(3 (m-3) (n-3)-1)]

(t1=Table[Piecewise[{{0,m<3||m==n==3},{n-4,m==3}},6(m-3)(n-3)-2],{n,15},{m,n}])//Column

(t2=Table[GraphCycleCount[KnightGraph[m,n],4],{n,15},{m,n}])//Column

DeleteCases[Flatten[Table[{{m,n},GraphCycleCount[KnightGraph[m,n],4],Piecewise[{{0,Min[m,n]<3||m==n==3},{Max[m,n]-4,Min[m,n]==3}},6(m-3)(n-3)-2]},{n,15},{m,15}],1],{_,x_,x_}]

t1==t2

StabilityIndex

Entity["Graph",{"Knight",{n,n}}]["StabilityIndex"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{m n+1,m==n||Mod[m,2]==Mod[n,2]}},0],GraphData[#,"StabilityIndex"]}]&/@GraphData["Knight"],{_,x_,x_}]

TopologicalIndex

Entity["Graph",{"Knight",{n,n}}]["TopologicalIndex"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],(((-2))^(m+n))(1-m-n),GraphData[#,"TopologicalIndex"]}]&/@GraphData["Knight"],{_,x_,x_}]

ToroidalCrossingNumber

Entity["Graph",{"Knight",{n,n}}]["ToroidalCrossingNumber"]

seq=Table[GraphData[{"Knight",{n,n}},"ToroidalCrossingNumber"],{n,20}]

Traceable

Entity["Graph",{"Knight",{n,n}}]["Traceable"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"Traceable"]}]&/@GraphData["Knight"],{_,x_,x_}]

TriangleCount

Entity["Graph",{"Knight",{n,n}}]["TriangleCount"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],0,GraphData[#,"TriangleCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

TuttePolynomial

Untraceable

Entity["Graph",{"Knight",{n,n}}]["Untraceable"]

Table[GraphData[{"Knight",{n,n}},"Untraceable"],{n,20}]

VertexConnectivity

Entity["Graph",{"Knight",{n,n}}]["VertexConnectivity"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]<3||m==n==3}},2],GraphData[#,"VertexConnectivity"]}]&/@GraphData["Knight"],{_,x_,x_}]

VertexCount

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

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],m n,GraphData[#,"VertexCount"]}]&/@GraphData["Knight"],{_,x_,x_}]

VertexCoverNumber

Entity["Graph",{"Knight",{n,n}}]["VertexCoverNumber"]

Sort@DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]==1}}],GraphData[#,"VertexCoverNumber"]}]&/@GraphData["Knight"],{_,x_,x_}]

Table[m n-Piecewise[{
{Max[m,n],Min[m,n]==1},
{Max[m,n]+1,Min[m,n]==2&&Mod[Max[m,n],2]==1},
{4Round[(Max[m,n]+1)/4],Min[m,n]==2&&Mod[Max[m,n],2]==0},
{m n/2,Mod[m n,2]==0},
{(m n+1)/2,Mod[m n,2]==1}}],{n,11},{m,n}]//Column

(seq=Table[VertexCoverNumber[KnightTourGraph[m,n]],{n,11},{m,n}])//Column

VertexCoverPolynomial

Entity["Graph",{"Knight",{n,n}}]["VertexCoverPolynomial"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Expand[(#^m (#+1)^n+#^n (#+1)^m-#^(m+n)&)[x]-GraphData[#,"VertexCoverPolynomial"][x]]}]&/@GraphData["Knight"],{_,0}]

VertexDegrees

Entity["Graph",{"Knight",{n,n}}]["VertexDegrees"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Join[ConstantArray[n,m],ConstantArray[m,n]],GraphData[#,"VertexDegrees"]}]&/@GraphData["Knight"],{_,x_,x_}]

VertexTransitive

Entity["Graph",{"Knight",{n,n}}]["VertexTransitive"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],Piecewise[{{True,Min[m,n]==1||m==n==2}},False],GraphData[#,"VertexTransitive"]}]&/@GraphData["Knight"],{_,x_,x_}]

WienerIndex

Entity["Graph",{"Knight",{n,n}}]["WienerIndex"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],(m^2)+(n^2)+m n-(m+n),GraphData[#,"WienerIndex"]}]&/@GraphData["Knight"],{_,x_,x_}]

WienerSumIndex

Entity["Graph",{"Knight",{n,n}}]["WienerSumIndex"]

DeleteCases[Block[{m,n},{{m,n}="Knight"/.GraphData[#,"NotationRules"],((m n ((m^2)+(n^2)+4 m n-3 (m+n)+2))/(2 (m+n-1))),GraphData[#,"WienerSumIndex"]}]&/@GraphData["Knight"],{_,x_,x_}]

Properties n×n

Acyclic

Table[GraphData[{"Knight",{n,n}},"Acyclic"],{n,20}]

AdjacencyMatrixCount

seq=Table[GraphData[{"Knight",{n,n}},"AdjacencyMatrixCount"],{n,10}]

FindSequenceFunction[seq,n]

Table[((((n^2))!)/(Piecewise[{{1,n==1},{24,n==2},{16,n==3},{64,n==4}},8])),{n,10}]

Arboricity

Table[GraphData[{"Knight",{n,n}},"Arboricity"],{n,20}]

ArcTransitive

Table[GraphData[{"Knight",{n,n}},"ArcTransitive"],{n,20}]

ArcTransitivity

Table[GraphData[{"Knight",{n,n}},"ArcTransitivity"],{n,20}]

AutomorphismCount

seq=Table[GraphData[{"Knight",{n,n}},"AutomorphismCount"],{n,20}]

Table[Piecewise[{{1,n==1},{24,n==2},{16,n==3},{64,n==4}},8],{n,20}]

%==seq

BalabanIndex

Table[GraphData[{"Knight",{n,n}},"BalabanIndex"],{n,6}]

Bandwidth

Table[GraphData[{"Knight",{n,n}},"Bandwidth"],{n,20}]

BridgeCount

seq=Table[GraphData[{"Knight",{n,n}},"BridgeCount"],{n,20}]

BurningNumber

seq=Table[GraphData[{"Knight",{n,n}},"BurningNumber"],{n,20}]

CharacteristicPolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"CharacteristicPolynomial"][x],{n,k0=1,kmax=12}]);

coef=Factor/@FindLinearRecurrence[Drop[poly,2]]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

ChordCount

seq=Table[GraphData[{"Knight",{n,n}},"ChordCount"],{n,20}]

FindSequenceFunction[DeleteMissing[seq],n]

Do[Print[{n,Length[Chords[KnightTourGraph[n,n]]]//Timing}],{n,7}]

Factor[4 (-2+n) (-1+n)-8]

Table[4 (-2+n) (-1+n)-8,{n,10}]

GraphData[{"Knight",{3,3}},"Graph",{"All","Labeled"}]

GraphData[{"Knight",{4,4}},"Graph",{"All","Labeled"}]

GraphData[{"Knight",{4,4}},"Chords"]

ChordlessCycleCount

seq=Table[GraphData[{"Knight",{n,n}},"ChordlessCycleCount"],{n,20}]

FindSequenceFunction[DeleteMissing[seq],n]

ChromaticInvariant

seq=Table[GraphData[{"Knight",{n,n}},"ChromaticInvariant"],{n,20}]

FindSequenceFunction[Drop[seq,2],n]

ChromaticNumber

seq=Table[GraphData[{"Knight",{n,n}},"ChromaticNumber"],{n,20}]

ChromaticPolynomial

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

CoefficientList[DeleteCases[poly,_Missing[x]],x]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

Circumference

Entity["Graph",{"Knight",{n,n}}]["Circumference"]

seq=Table[GraphData[{"Knight",{n,n}},"Circumference"],{n,20}]

Table[Piecewise[{{Missing["NotApplicable"], n == 1 || n == 2}, {14, n == 4}, {n^2, Mod[n, 2] == 0}, {-1 + n^2, Mod[n, 2] == 1}}, 0],{n,20}]

FindSequenceFunction[Drop[seq,3],n-4]

gf=(x^3)FindGeneratingFunction[Drop[seq,2],x]

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

Classes

Intersection@@(GraphData[#,"Classes"]&/@(Cases[("Knight"/.GraphData[#,"NotationRules"])&/@GraphData["Knight"],{n_,n_}:>{"Knight",{n,n}}]))

CliqueCount

seq=Table[GraphData[{"Knight",{n,n}},"CliqueCount"],{n,20}]

FindSequenceFunction[seq,n]//Factor

CliqueCoveringNumber

seq=Table[GraphData[{"Knight",{n,n}},"CliqueCoveringNumber"],{n,20}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

InputForm[%]

CliqueNumber

seq=Table[GraphData[{"Knight",{n,n}},"CliqueNumber"],{n,20}]

CliquePolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"CliquePolynomial"][x],{n,k0=1,kmax=20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[1+x ((n^2)+4 (-2+n) (-1+n) x),{n,k0,kmax}]

FullSimplify[poly2-poly]

ComplementOddChordlessCycleCount

seq=Table[GraphData[{"Knight",{n,n}},"ComplementOddChordlessCycleCount"],{n,20}]

ConnectedComponentCount

seq=Table[GraphData[{"Knight",{n,n}},"ConnectedComponentCount"],{n,20}]

ConnectedDominatingSetCount

A291705

seq=Table[GraphData[{"Knight",{n,n}},"ConnectedDominatingSetCount"],{n,20}]

ConnectedDominationNumber

seq=Table[GraphData[{"Knight",{n,n}},"ConnectedDominationNumber"],{n,20}]

ConnectedDominationPolynomial

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

ConnectedInducedSubgraphCount

A290765

seq=Table[GraphData[{"Knight",{n,n}},"ConnectedInducedSubgraphCount"],{n,6}]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

ConnectedInducedSubgraphPolynomial

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,6}]

FullSimplify[poly2-poly]

CrossingNumber

seq=Table[GraphData[{"Knight",{n,n}},"CrossingNumber"],{n,20}]

CycleCount

A234623

Table[Length[System`FindCycle[KnightTourGraph[n,n],Infinity,All]],{n,5}]

seq=Table[GraphData[{"Knight",{n,n}},"CycleCount"],{n,20}]

FindLinearRecurrence[DeleteMissing[Drop[seq,3]]]

FindSequenceFunction[DeleteMissing[Drop[seq,3]],n-4]

gf=(x^3)FindGeneratingFunction[DeleteMissing[Drop[seq,2]],x]

CyclePolynomial

(poly=Table[GraphData[{"Knight",{n,n}},"CyclePolynomial"][x],{n,k0=1,kmax=20}])//Column

Table[CoefficientList[Total[x^Length[#]&/@System`FindCycle[KnightTourGraph[n,n],Infinity,All]],x],{n,5}]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

Cyclic

Table[GraphData[{"Knight",{n,n}},"Cyclic"],{n,20}]

CyclomaticNumber

seq=Table[GraphData[{"Knight",{n,n}},"CyclomaticNumber"],{n,20}]

FindSequenceFunction[Drop[seq,2],n-2]//FullSimplify

gf=x FindGeneratingFunction[seq,x]

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

DetourIndex

seq=Table[GraphData[{"Knight",{n,n}},"DetourIndex"],{n,20}]

DetourMatrix

MatrixForm/@Table[GraphData[{"Rook",{n,n}},"DetourMatrix"],{n,10}]

MatrixForm/@Table[SparseArray[{i_,j_}:>Abs[i-j],n],{n,10}]

DetourPolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"DetourPolynomial"][x],{n,k0=1,kmax=20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

Diameter

A232007

Entity["Graph",{"Knight",{n,n}}]["Diameter"]

FullSimplify[Floor[((2 (1+n))/3)]-Ceiling[((2n)/3)],n∈Integers&&n>0]

Table[Floor[((2 (1+n))/3)]-Ceiling[((2n)/3)],{n,100}]//Union

seq=Table[GraphData[{"Knight",{n,n}},"Diameter"],{n,20}]

(seq=Table[GraphDiameter[KnightTourGraph[n,n]],{n,50}])//Timing

Replace[Table[GraphDiameter[KnightTourGraph[n,n]],{n,20}],Infinity->-1]

FindLinearRecurrence[Drop[seq,4]]

Join[{0,-1,-1,5},LinearRecurrence[{1,0,1,-1},{4,4,5,6},20]]

FindSequenceFunction[Drop[seq,4],n-5]//FullSimplify

Join[{0,-1,-1,5},Table[Ceiling[2n/3],{n,5,20}]]

Table[Piecewise[{{0,n==1},{Infinity,n==2||n==3},{5,n==4}},Floor[2(n+1)/3]],{n,20}]

-x-x^2+5x^3+(x^4)FindGeneratingFunction[Drop[seq,4],x]

Factor[%]

CoefficientList[Series[-1-x+5 (x^2)+(((x^3)(4+(x^2)-3 (x^3)))/((((-1+x))^2) (1+x+(x^2)))),{x,0,20}],x]

DistanceMatrix

MatrixForm/@Table[GraphData[{"Knight",{n,n}},"DistanceMatrix"],{n,4}]

MatrixForm/@Table[SparseArray[{i_,j_}:>Abs[i-j],n],{n,10}]

DistanceHereditary

Entity["Graph",{"Knight",{n,n}}]["DistanceHereditary"]

seq=Table[GraphData[{"Knight",{n,n}},"DistanceHereditary"],{n,20}]

DistancePolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"DistancePolynomial"][x],{n,k0=1,kmax=20}])//Column

coef=Factor/@FindLinearRecurrence[Drop[poly,3]]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

DistinguishingNumber

seq=Table[GraphData[{"Knight",{n,n}},"DistinguishingNumber"],{n,20}]

DomaticNumber

seq=Table[GraphData[{"Knight",{n,n}},"DomaticNumber"],{n,20}]

Table[GraphData[{"Knight",{n,n}},"DominatingSetCount"],{n,10}]

Table[GraphData[{"Knight",{n,n}},"MinimalDominatingSetCount"],{n,10}]

Table[Floor[Divide@@GraphData[{"Knight",{n,n}},{"VertexCount","DominationNumber"}]],{n,10}]

DominatingSetCount

A287071

seq=Table[GraphData[{"Knight",{n,n}},"DominatingSetCount"],{n,20}]

GraphData[{"Knight",{2,2}}]

FindLinearRecurrence[seq]

FindLinearRecurrence[Drop[DeleteMissing[seq],2]]

FindSequenceFunction[DeleteMissing[Drop[seq,2]],n-2]

gf=x FindGeneratingFunction[DeleteMissing[seq],x]

DominationNumber

A006075

seq=Table[GraphData[{"Knight",{n,n}},"DominationNumber"],{n,20}]

Do[Print[{n,DominationNumber[KnightTourGraph[n,n]]//Timing}],{n,15}]

gf=x FindGeneratingFunction[seq,x]

DominationPolynomial

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

EdgeChromaticNumber

seq=Table[GraphData[{"Knight",{n,n}},"EdgeChromaticNumber"],{n,20}]

EdgeConnectivity

Table[GraphData[{"Knight",{n,n}},"EdgeConnectivity"],{n,20}]

EdgeCount

seq=Table[GraphData[{"Knight",{n,n}},"M"],{n,20}]

FindSequenceFunction[seq,n]

8Binomial[n-1,2]

EdgeCoverCount

seq=Table[GraphData[{"Knight",{n,n}},"EdgeCoverCount"],{n,20}]

EdgeCoverNumber

A000982 for n > 3

seq=Table[GraphData[{"Knight",{n,n}},"EdgeCoverNumber"],{n,20}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

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

Table[Piecewise[{{0,n==1||n==2||n==3}},Ceiling[n^2/2]],{n,20}]

%==seq

EdgeCoverPolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"EdgeCoverPolynomial"][x],{n,k0=1,kmax=20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

EulerianCycleCount

seq=Table[GraphData[{"Knight",{n,n}},"EulerianCycleCount"],{n,20}]

FaceCount

seq=Table[GraphData[{"Knight",{n,n}},"FaceCount"],{n,20}]

FibonacciCube

Entity["Graph",{"Knight",{n,n}}]["FibonacciCube"]

seq=Table[GraphData[{"Knight",{n,n}},"FibonacciCube"],{n,20}]

FlowPolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"FlowPolynomial"][x],{n,k0=1,kmax=20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

FractionalChromaticNumber

seq=Table[GraphData[{"Knight",{n,n}},"FractionalChromaticNumber"],{n,20}]

FractionalEdgeChromaticNumber

seq=Table[GraphData[{"Knight",{n,n}},"FractionalEdgeChromaticNumber"],{n,20}]

Girth

seq=Table[GraphData[{"Knight",{n,n}},"Girth"],{n,20}]

Gonality

seq=Table[GraphData[{"Knight",{n,n}},"Gonality"],{n,20}]

HamiltonConnected

seq=Table[GraphData[{"Knight",{n,n}},"HamiltonConnected"],{n,20}]

HamiltonDecompositionCount

seq=Table[GraphData[{"Knight",{n,n}},"HamiltonDecompositionCount"],{n,20}]

Hamiltonian

Conrad et al. (2004) showed that an nxn knight graph is Hamiltonain iff n >= 6 and n is even

And@@Table[GraphData[{"Knight",{n,n}},"Hamiltonian"]===(n≥6&&Mod[n,2]==0),{n,20}]

seq=Table[GraphData[{"Knight",{n,n}},"Hamiltonian"],{n,20}]

Table[Piecewise[{{True,n==1||(n>5&&Mod[n,2]==0)}},False],{n,20}]

%==seq

HamiltonianCycleCount

even terms of below are A001230

Table[Length[FindHamiltonianCycle[KnightTourGraph[2n,2n],All]],{n,3}]

seq=Table[GraphData[{"Knight",{n,n}},"HamiltonianCycleCount"],{n,20}]

seq[[2;;All;;2]]

HamiltonianNumber

seq=Table[GraphData[{"Knight",{n,n}},"HamiltonianNumber"],{n,20}]

HamiltonianPathCount

seq=Table[GraphData[{"Knight",{n,n}},"HamiltonianPathCount"],{n,20}]

HamiltonianWalkCount

seq=Table[GraphData[{"Knight",{n,n}},"HamiltonianWalkCount"],{n,20}]

HararyIndex

seq=Table[GraphData[{"Knight",{n,n}},"HararyIndex"],{n,20}]

(seq=Table[HararyIndex[KnightGraph[n,n]],{n,40}])//Timing

FindSequenceFunction[seq,n]

FindSequenceFunction[Drop[seq,2],n-2]

HexagonCount

A289181

Table[Length[System`FindCycle[KnightTourGraph[n,n],{6},All]],{n,20}]

seq=Table[GraphData[{"Knight",{n,n}},"HexagonCount"],{n,20}]

(seq=Monitor[Table[CycleCount[KnightGraph[n,n],6],{n,100}],n])//Timing

FindLinearRecurrence[seq]

FindLinearRecurrence[Drop[seq,5]]

LinearRecurrence[{3,-3,1},{616,1348,2352},{-4,20}]

Join[{0,0,0,20,164},LinearRecurrence[{3,-3,1},{1036,408,52},{6,20}]]

FindSequenceFunction[Drop[seq,5],n-5]//Factor

Table[Piecewise[{{0,n<4},{20,n==4},{164,n==5}},4 (34 (n^2)-259n+484)],{n,100}]==seq

gf=x FindGeneratingFunction[seq,x]

wrong: bug(333165)

gf=(x^6) FindGeneratingFunction[Drop[seq,5],x]

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

gf=Factor[20(x^4)+164(x^5)-((4 (x^6) (154-125 x+39 (x^2)))/(((-1+x))^3))]

ToString[gf,InputForm]

Series[((4 (x^4) (-5-26 x-46 (x^2)+7 (x^3)+2 (x^4)))/(((-1+x))^3)),{x,0,20}]

CoefficientList[Series[((4 (x^3) (-5-26 x-46 (x^2)+7 (x^3)+2 (x^4)))/(((-1+x))^3)),{x,0,20}],x]

IdiosyncraticPolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"IdiosyncraticPolynomial"][x,y],{n,k0=1,kmax=8}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

IndependenceNumber

A030978

Table[Length[FindIndependentVertexSet[KnightTourGraph[n,n]][[1]]],{n,20}]

seq=Table[GraphData[{"Knight",{n,n}},"IndependenceNumber"],{n,20}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

Table[If[n==2,4,(1-(-1)^n+2n^2)/4],{n,20}]

IndependencePolynomial

A244081

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"IndependencePolynomial"][x],{n,k0=1,kmax=20}])//Column

Take[poly,5]//Expand//InputForm

coef=Factor/@FindLinearRecurrence[DeleteCases[poly,_Missing[x]]]

coef=Factor/@FindLinearRecurrence[Drop[DeleteCases[poly,_Missing[x]],3]]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[DeleteCases[poly,_Missing[x]],z]]

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

Compute

Clear[b,T]

b[n_,l_]:=b[n,l]=Module[{d,f,g,k},d=Length[l]/3;f=False;Which[n==0,1,l[[1;;d]]==Array[f&,d],b[n-1,Join[l[[d+1;;3*d]],Array[True&,d]]],True,For[k=1,!l[[k]],k++];g=ReplacePart[l,k->f];
If[k>1,g=ReplacePart[g,2*d-1+k->f]];
If[k<d,g=ReplacePart[g,2*d+1+k->f]];
If[k>2,g=ReplacePart[g,d-2+k->f]];
If[k<d-1,g=ReplacePart[g,d+2+k->f]];
Expand[b[n,ReplacePart[l,k->f]]+b[n,g]*x]]];
T[n_]:=T[n]=Function[p,Table[Coefficient[p,x,i],{i,0,Exponent[p,x]}]][b[n,Array[True&,n*3]]];

Do[Print[{n,T[n];//Timing}],{n,11}];

Do[Print[{n,T[n];//Timing}],{n,12,13}];

poly2=Table[T[n].x^Range[0,Length[T[n]]-1],{n,9}]

FullSimplify[poly2-Most@poly]

Compute dumbly

Table[Count[IndependentVertexSetQ[KnightTourGraph[n,n],#]&/@Subsets[Range[n^2],{k}],True],{n,4},{k,0,If[n==2,4,(1-(-1)^n+2n^2)/4]}]//Timing

Table[Total[Boole[IndependentVertexSetQ[KnightTourGraph[n,n],#]&/@Subsets[Range[n^2],{k}]]],{n,4},{k,0,If[n==2,4,(1-(-1)^n+2n^2)/4]}]//Timing

Table[Count[Subsets[Range[n^2],{k}],_?(IndependentVertexSetQ[KnightTourGraph[n,n],#]&)],{n,4},{k,0,If[n==2,4,(1-(-1)^n+2n^2)/4]}]//Timing

IndependenceRatio

seq=Table[GraphData[{"Knight",{n,n}},"IndependenceRatio"],{n,20}]

FullSimplify[(({{\[Piecewise], ({{4, n==2}, {(1/4) (1+(((-1))^(1+n))+2 (n^2)), True}})}})/(n^2))]

Table[(({{\[Piecewise], ({{4, n==2}, {(1/4) (1+(((-1))^(1+n))+2 (n^2)), True}})}})/(n^2)),{n,20}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

IndependentEdgeSetCount

A287225

seq=Table[GraphData[{"Knight",{n,n}},"IndependentEdgeSetCount"],{n,20}]

seq={1,1,47,8617,4437215,18283403428,478131755555352,65146261730656227552,51516890628947512147926356,244151636345172523021724077440553,6697138334086551576618194527162685383161};

FindLinearRecurrence[Drop[seq,2]]

FindSequenceFunction[Drop[seq,2],n-2]

gf=x FindGeneratingFunction[seq,x]

IndependentVertexSetCount

A141243

seq=Table[GraphData[{"Knight",{n,n}},"IndependentVertexSetCount"],{n,20}]

FindLinearRecurrence[DeleteMissing[Rest@seq]]

FindSequenceFunction[DeleteMissing[Rest@seq],n-1]

gf=x FindGeneratingFunction[DeleteMissing[seq],x]

Total/@Table[Count[IndependentVertexSetQ[KnightTourGraph[n,n],#]&/@Subsets[Range[n^2],{k}],True],{n,4},{k,0,If[n==2,4,(1-(-1)^n+2n^2)/4]}]//Timing

Table[Count[IndependentVertexSetQ[KnightTourGraph[n,n],#]&/@Subsets[Range[n^2],{0,If[n==2,4,(1-(-1)^n+2n^2)/4]}],True],{n,4}]//Timing

IntersectionNumber

seq=Table[GraphData[{"Knight",{n,n}},"IntersectionNumber"],{n,20}]

IrredundantSetCount

A290785

Table[GraphData[{"Knight",{n,n}},"IrredundantSetCount"],{n,10}]

KirchhoffIndex

seq=Table[GraphData[{"Knight",{n,n}},"KirchhoffIndex"],{n,20}]

FindSequenceFunction[Drop[seq,3],n-4]

KirchhoffSumIndex

seq=Table[GraphData[{"Knight",{n,n}},"KirchhoffSumIndex"],{n,20}]

LaplacianMatrix

MatrixForm/@Table[GraphData[{"Knight",{n,n}},"LaplacianMatrix"],{n,10}]

LaplacianPolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"LaplacianPolynomial"][x],{n,k0=1,kmax=20}])//Column

coef=Factor/@FindLinearRecurrence[Drop[poly,2]]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

LeafCount

seq=Table[GraphData[{"Knight",{n,n}},"LeafCount"],{n,20}]

LongestCycleCount

seq=Table[GraphData[{"Knight",{n,n}},"LongestCycleCount"],{n,20}]

LovaszNumber

seq=Table[GraphData[{"Knight",{n,n}},"LovaszNumber"],{n,20}]

LucasCube

Entity["Graph",{"Knight",{n,n}}]["LucasCube"]

seq=Table[GraphData[{"Knight",{n,n}},"LucasCube"],{n,20}]

MatchingGeneratingPolynomial

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

CoefficientList[Take[poly,5],x]

coef=Factor/@FindLinearRecurrence[DeleteCases[Drop[poly,2],_Missing[x]]]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

MatchingNumber

A007590 for n > 2

Table[Length[FindIndependentEdgeSet[KnightTourGraph[n,n]]],{n,20}]

seq=Table[GraphData[{"Knight",{n,n}},"MatchingNumber"],{n,20}]

Table[Piecewise[{{0,n==2}},Floor[n^2/2]],{n,20}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

MatchingPolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"MatchingPolynomial"][x],{n,k0=1,kmax=20}])//Column

CoefficientList[Take[poly,5],x]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

MaximalCliqueCount

seq=Table[GraphData[{"Knight",{n,n}},"MaximalCliqueCount"],{n,20}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

MaximalIndependentEdgeSetCount

A289200

seq=Table[GraphData[{"Knight",{n,n}},"MaximalIndependentEdgeSetCount"],{n,20}]

Table[Length[FindIndependentVertexSet[System`LineGraph[KnightTourGraph[n,n]],Infinity,All]],{n,5}]

MaximalIndependentVertexSetCount

A289201

seq=Table[GraphData[{"Knight",{n,n}},"MaximalIndependentVertexSetCount"],{n,20}]

Table[Length[FindIndependentVertexSet[KnightTourGraph[n,n],Infinity,All]],{n,7}]

FindLinearRecurrence[Drop[seq,3]]

FindLinearRecurrence[Drop[seq,4]]

FindSequenceFunction[DeleteMissing[Drop[seq,3]],n-3]

gf=x FindGeneratingFunction[DeleteMissing[seq],x]

Table[Length[FindIndependentVertexSet[KnightTourGraph[n,n],Infinity,All]],{n,7}]//Timing

MaximumCliqueCount

seq=Table[GraphData[{"Knight",{n,n}},"MaximumCliqueCount"],{n,20}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

SeriesCoefficient[gf,{x,0,n}]//FullSimplify

MaximumIndependentEdgeSetCount

A289202

seq=Table[GraphData[{"Knight",{n,n}},"MaximumIndependentEdgeSetCount"],{n,20}]

seq={1,1,2,16,644,10304,65113608,2849759680,118928612871184,58888109421793792};

FindLinearRecurrence[Drop[seq,2]]

FindSequenceFunction[Drop[seq,2],n-2]

gf=x FindGeneratingFunction[DeleteMissing[seq],x]

Join[{1,1},Table[Length[With[{g=System`LineGraph[KnightTourGraph[n,n]]},FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],All]]],{n,3,5}]]//Timing

MaximumIndependentVertexSetCount

A289203

seq=Table[GraphData[{"Knight",{n,n}},"MaximumIndependentVertexSetCount"],{n,20}]

Length/@Table[FindIndependentVertexSet[KnightTourGraph[n,n],{If[n==2,4,(1-(-1)^n+2n^2)/4]},All],{n,8}]

Table[((-1)^n+3)/2,{n,10}]

seq=Table[Piecewise[{{1,n==2},{2,n==3},{6,n==4},{2,Mod[n,2]==0},{1,Mod[n,2]==1}}],{n,100}]

Table[Piecewise[{{1,n==2},{2,n==3},{6,n==4}},((-1)^n+3)/2],{n,100}]==seq

Table[Length[With[{g=KnightTourGraph[n,n]},FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],All]]],{n,8}]//Timing

gf=x FindGeneratingFunction[seq,x]

ToString[gf,InputForm]

CoefficientList[Series[((-1-x-(x^2)-5 (x^3)+(x^4)+4 (x^5))/(-1+(x^2))),{x,0,20}],x]

MaximumLeafNumber

seq=Table[GraphData[{"Knight",{n,n}},"MaximumLeafNumber"],{n,20}]

MaximumVertexDegree

seq=Table[GraphData[{"Knight",{n,n}},"MaximumVertexDegree"],{n,20}]

MeanDistance

seq=Table[GraphData[{"Knight",{n,n}},"MeanDistance"],{n,20}]

(seq=Monitor[Table[MeanDistance[KnightGraph[n,n]],{n,50}],n])//Timing

FindLinearRecurrence[Drop[seq,3]]

FindSequenceFunction[Drop[seq,3],n-3]

gf=(x^4)FindGeneratingFunction[Drop[seq,3],x]

Meyniel

Entity["Graph",{"Knight",{n,n}}]["Meyniel"]

seq=Table[GraphData[{"Knight",{n,n}},"Meyniel"],{n,20}]

MinimalDominatingSetCount

A286882

seq=Table[GraphData[{"Knight",{n,n}},"MinimalDominatingSetCount"],{n,20}]

MinimalDominatingSetSignature

seq=Table[GraphData[{"Knight",{n,n}},"MinimalDominatingSetSignature"],{n,20}]//Column

MinimumCliqueCoveringCount

seq=Table[GraphData[{"Knight",{n,n}},"MinimumCliqueCoveringCount"],{n,20}]

MinimumConnectedDominatingSetCount

seq=Table[GraphData[{"Knight",{n,n}},"MinimumConnectedDominatingSetCount"],{n,10}]

FindSequenceFunction[seq,n]

MinimumDistinguishingLabelingCount

seq=Table[GraphData[{"Knight",{n,n}},"MinimumDistinguishingLabelingCount"],{n,20}]

MinimumDominatingSetCount

A103315

seq=Table[GraphData[{"Knight",{n,n}},"MinimumDominatingSetCount"],{n,20}]

MinimumEdgeCoverCount

seq=Table[GraphData[{"Knight",{n,n}},"MinimumEdgeCoverCount"],{n,20}]

MinimumVertexDegree

seq=Table[GraphData[{"Knight",{n,n}},"MinimumVertexDegree"],{n,20}]

MolecularTopologicalIndex

seq=Table[GraphData[{"Knight",{n,n}},"MolecularTopologicalIndex"],{n,20}]

FindSequenceFunction[Drop[seq,3],n-4]

gf=(x^4)FindGeneratingFunction[Drop[seq,3],x]

Nonhamiltonian

Table[GraphData[{"Knight",{n,n}},"Nonhamiltonian"],{n,20}]

NormalizedLaplacianMatrix

MatrixForm/@Table[GraphData[{"Knight",{n,n}},"NormalizedLaplacianMatrix"],{n,10}]

OddChordlessCycleCount

seq=Table[GraphData[{"Knight",{n,n}},"OddChordlessCycleCount"],{n,20}]

PathCount

A289204

seq=Table[GraphData[{"Knight",{n,n}},"PathCount"],{n,20}]

seq={0,0,56,14980,19005336,278982789260};

FindLinearRecurrence[DeleteMissing[Drop[seq,3]]]

FindSequenceFunction[DeleteMissing[Drop[seq,3]],n-3]

gf=(x^3) FindGeneratingFunction[DeleteMissing@Drop[seq,2],x]

PathPolynomial

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

Pell

Entity["Graph",{"Knight",{n,n}}]["Pell"]

seq=Table[GraphData[{"Knight",{n,n}},"Pell"],{n,20}]

PentagonCount

seq=Table[GraphData[{"Knight",{n,n}},"PentagonCount"],{n,20}]

Perfect

Table[GraphData[{"Knight",{n,n}},"Perfect"],{n,20}]

ProjectivePlaneCrossingNumber

seq=Table[GraphData[{"Knight",{n,n}},"ProjectivePlaneCrossingNumber"],{n,20}]

Radius

A123919

Entity["Graph",{"Knight",{n,n}}]["Radius"]

seq=Table[GraphData[{"Knight",{n,n}},"Radius"],{n,20}]

(seq=Table[GraphRadius[KnightTourGraph[n,n]],{n,100}])//Timing

FindLinearRecurrence[Drop[seq,7]]

gf=(x^8) FindGeneratingFunction[Drop[seq,7],x]

Series[gf,{x,0,20}]

CoefficientList[Series[(( (4+(x^4)-3 (x^6)))/((((-1+x))^2) (1+x+(x^2)+(x^3)+(x^4)+(x^5)))),{x,0,50}],x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n∈Integers&&n>7]

Subtract@@@Table[{(1/6) (5+(((-1))^n)+2 n+ChebyshevU[n,-(1/2)]-Cos[((n π)/3)]+(Sqrt[3]) Sin[((n π)/3)]),Floor[(n+2)/2]-Floor[(n+2)/6]},{n,7,100}]

RectilinearCrossingNumber

seq=Table[GraphData[{"Knight",{n,n}},"RectilinearCrossingNumber"],{n,20}]

ReliabilityPolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"ReliabilityPolynomial"][x],{n,k0=1,kmax=20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

SigmaPolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"SigmaPolynomial"][x],{n,k0=1,kmax=20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

SpanningTreeCount

seq=Table[GraphData[{"Knight",{n,n}},"SpanningTreeCount"],{n,20}]

FindSequenceFunction[Drop[seq,4],n-5]

gf=(x^5)FindGeneratingFunction[Drop[seq,4],x]

SquareCount

A163433

Table[Length[System`FindCycle[KnightTourGraph[n+2,n+2],{4},All]],{n,20}]

seq=Table[GraphData[{"Knight",{n,n}},"SquareCount"],{n,20}]

gf=(x^4) FindGeneratingFunction[Drop[seq,3],x]

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

Factor[52+6 (-6+n) n]

Table[2 (26-18 n+3 (n^2)),{n,10}]

Table[Piecewise[{{0,n==1||n==2||n==3}},2 (26-18 n+3 (n^2))],{n,20}]

%==seq

Length/@Table[System`FindCycle[KnightTourGraph[n+2,n+2],{4},All],{n,20}]

StabilityIndex

seq=Table[GraphData[{"Knight",{n,n}},"StabilityIndex"],{n,20}]

seq[[1;;All;;2]]

seq[[2;;All;;2]]

FindLinearRecurrence[seq[[2;;All;;2]]]

FindSequenceFunction[seq[[2;;All;;2]],n]

gf=x FindGeneratingFunction[seq[[2;;All;;2]],x]

TopologicalIndex

seq=Table[GraphData[{"Knight",{n,n}},"TopologicalIndex"],{n,20}]

FindSequenceFunction[seq,n-1]

FindGeneratingFunction[seq,x]

ToroidalCrossingNumber

seq=Table[GraphData[{"Knight",{n,n}},"ToroidalCrossingNumber"],{n,20}]

Traceable

Conrad et al. (2004) showed that an nxn knight graph is traceable iff n >= 5

And@@Table[GraphData[{"Knight",{n,n}},"Traceable"]===(n≥5),{n,20}]

Table[GraphData[{"Knight",{n,n}},"Traceable"],{n,20}]

TriangleCount

seq=Table[GraphData[{"Knight",{n,n}},"TriangleCount"],{n,20}]

TuttePolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"TuttePolynomial"][x,y],{n,k0=1,kmax=20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

Untraceable

Table[GraphData[{"Knight",{n,n}},"Untraceable"],{n,20}]

VertexConnectivity

Table[GraphData[{"Knight",{n,n}},"VertexConnectivity"],{n,20}]

VertexCount

seq=Table[GraphData[{"Knight",{n,n}},"VertexCount"],{n,20}]

FindSequenceFunction[seq,n-1]//FullSimplify

VertexCoverNumber

Related to but not the same as IndependenceNumber

seq=Table[GraphData[{"Knight",{n,n}},"VertexCoverNumber"],{n,20}]

FindSequenceFunction[seq,n-1]//FullSimplify

gf=(x^3) FindGeneratingFunction[Drop[seq,2],x]

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

VertexCoverPolynomial

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"VertexCoverPolynomial"][x],{n,k0=1,kmax=20}])//Column

CoefficientList[Take[poly,5],x]

coef=Factor/@FindLinearRecurrence[DeleteCases[Drop[poly,2],_Missing[x]]]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

VertexDegrees

seq=Table[GraphData[{"Knight",{n,n}},"VertexDegrees"],{n,5}]

WienerIndex

A292054

seq=Table[GraphData[{"Knight",{n,n}},"WienerIndex"],{n,20}]

(seq=Monitor[Table[WienerIndex[KnightGraph[n,n]],{n,100}],n])//Timing

seq={0,∞,∞,288,708,1580,3144,5804,9996,16388,25660,38808,56808,81048,112856,154080,206448,272332,353920,454172,575784,722372,897196,1104592,1348436,1633848,1965376,2348992,2789964,3295180,3870688,4524356,5263060,6095716,7030084,8076192,9242736,10540920,11980432,13573720,15331512,17267564,19393704,21725060,24274608,27058916,30092164,33392424,36975132,40859928,45063560,49607304,54509268,59792428,65476312,71585660,78141468,85170308,92694700,100743112,109339640,118514712,128294056,138710128,149790336,161569228,174075952,187347212,201413944,216315076,232083388,248760096,266379876,284986296,304615984,325314928,347121756,370084940,394245168,419653460,446352612,474396260,503829364,534708240,567080064,601003896,636529184,673717800,712621512,753305068,795822616,840241844,886619328,935025764,985520212,1038176440,1093056044,1150235928,1209780280,1271769208};

FindSequenceFunction[Drop[seq,3],n-2]

FindSequenceFunction[Drop[seq,4],n-3]

FindLinearRecurrence[Drop[seq,3]]

coef=FindLinearRecurrence[Drop[seq,4]]

Length@coef

Take[Drop[seq,4],Length@coef]

Join[{288},LinearRecurrence[{2,1,-3,0,-1,2,2,-1,0,-3,1,2,-1},{708,1580,3144,5804,9996,16388,25660,38808,56808,81048,112856,154080,206448},20]]

gf=(x^4)FindGeneratingFunction[Drop[seq,4],x]

gf=(x^4)FindGeneratingFunction[Take[Drop[seq,4],20],x]

WienerSumIndex

seq=Table[GraphData[{"Knight",{n,n}},"WienerSumIndex"],{n,10}]

FindSequenceFunction[Drop[seq,4],n-5]

gf=(x^4)FindGeneratingFunction[Drop[seq,3],x]

Symmetry

GraphData[{"KnightsTour",{3,6}},"LabeledImage"]

FlipLR[l_,{m_,n_}]:=Module[{c1=Range[n],cm=Range[(m-1)n+1,m n]},l/.Join[Thread[c1->cm],Thread[cm->c1]]
]
FlipTB[l_,{m_,n_}]:=Module[{i},
l/.Table[i->n-Mod[i-1,n]+n Floor[(i-1)/n],{i,m n}]
]

MinimalShift[l_]:=If[Last[l]<First[l],Reverse[l],l]

FlipReduce[l_,{m_,n_}]:=Module[{lr},
MinimalShift/@{
l,
lr=FlipLR[l,{m,n}],
FlipTB[l,{m,n}],
FlipTB[lr,{m,n}]
}]/;m≠n

GeometricallyDistinct[l_,{m_,n_}]:=Union[Sort[FlipReduce[#,{m,n}]][[1]]&/@l]

Table[i->6-Mod[i-1,6]+6 Floor[(i-1)/6],{i,18}]

Length[hc=GraphData[{"Knight",{3,7}},"HamiltonianPaths"]]

GeometricallyDistinct[hc,{3,7}]//Length

FlipReduce[hc,{3,6}]

GraphData[{"Knight",{3,7}},"AutomorphismCount"]

Tours

Show[GraphicsArray[Table[TourPlot[improvedWarnsdorff[n],DisplayFunction->Identity],
{n,5,8}]]]

EulersKnightsTour={
	{30,21,6,15,28,19},
		{7,16,29,20,5,14},
		{22,31,8,35,18,27},
		{9,36,17,26,13,4},
		{32,23,2,11,34,25},
		{1,10,33,24,3,12}};
TourPlot[EulersKnightsTour]

DeMoivreTour={
		{34,49,22,11,36,39,24,1},
		{21,10,35,50,23,12,37,40},
		{48,33,62,57,38,25,2,13},
		{9,20,51,54,63,60,41,26},
		{32,47,58,61,56,53,14,3},
		{19,8,55,52,59,64,27,42},
		{46,31,6,17,44,29,4,15},
		{7,18,45,30,5,16,43,28}};
LegendreTour={
		{22,25,50,39,52,35,60,57},
		{27,40,23,36,49,58,53,34},
		{24,21,26,51,38,61,56,59},
		{41,28,37,48,3,54,33,62},
		{20,47,42,13,32,63,4,55},
		{29,16,19,46,43,2,7,10},
		{18,45,14,31,12,9,64,5},
		{15,30,17,44,1,6,11,8}};
EulerTour={
		{58,43,60,37,52,41,62,35},
		{49,46,57,42,61,36,53,40},
		{44,59,48,51,38,55,34,63},
		{47,50,45,56,33,64,39,54},
		{22,7,32,1,24,13,18,15},
		{31,2,23,6,19,16,27,12},
		{8,21,4,29,10,25,14,17},
		{3,30,9,20,5,28,11,26}};
RogetsTour={
		{50,45,62,41,60,39,54,35},
		{63,42,51,48,53,36,57,38},
		{46,49,44,61,40,59,34,55},
		{43,64,47,52,33,56,37,58},
		{26,5,24,1,20,15,32,11},
		{23,2,27,8,29,12,17,14},
		{6,25,4,21,16,19,10,31},
		{3,22,7,28,9,30,13,18}};
RogetsTour2={
		{34,51,32,15,38,53,18,3},
		{31,14,35,52,17,2,39,54},
		{50,33,16,29,56,37,4,19},
		{13,30,49,36,1,20,55,40},
		{48,63,28,9,44,57,22,5},
		{27,12,45,64,21,8,41,58},
		{62,47,10,25,60,43,6,23},
		{11,26,61,46,7,24,59,42}};
JaenischsMagicTour={
	{63,22,15,40,1,42,59,18},
		{14,39,64,21,60,17,2,43},
		{37,62,23,16,41,4,19,58},
		{24,13,38,61,20,57,44,3},
		{11,36,25,52,29,46,5,56},
		{26,51,12,33,8,55,30,45},
		{35,10,49,28,53,32,47,6},
		{50,27,34,9,48,7,54,31}};
					
Show[GraphicsArray[
	{{TourPlot[DeMoivreTour,DisplayFunction->Identity],
				TourPlot[LegendreTour,DisplayFunction->Identity],
			TourPlot[EulerTour,DisplayFunction->Identity]},
			{TourPlot[RogetsTour,DisplayFunction->Identity],
			TourPlot[RogetsTour2,DisplayFunction->Identity],
			TourPlot[JaenischsMagicTour,DisplayFunction->Identity]}}],
	DisplayFunction->$DisplayFunction
]