King Graph

Author

Eric W. Weisstein
December 11, 2024

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

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

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

Figure

1x1

g=KingGraph[1,1,VertexLabels->Automatic]

EdgeLengths[g]//Tally

v=GraphEmbedding[g]

g1=Graphics[{
EdgeForm[Black],{FaceForm[If[EvenQ[Total[#]],LightGray,White]],Polygon[CirclePoints[#,1/(Sqrt[2]),4]]}&/@v,
FaceForm[White],Disk[v,.04]
},
PlotLabel->"1×1 king graph",
LabelStyle->Directive[Black,FontFamily->"Times",14,Italic]]

2x2

g=KingGraph[2,2,VertexLabels->Automatic]

EdgeLengths[g]//Tally

v=GraphEmbedding[g];

edges=List@@@EdgeList[g];

g2=Graphics[{
EdgeForm[Black],{FaceForm[If[EvenQ[Total[#]],LightGray,White]],Polygon[CirclePoints[#,1/(Sqrt[2]),4]]}&/@v,
Thick,Line[v,edges],
FaceForm[White],Disk[v,.06]
},
PlotLabel->"2×2 king graph",
LabelStyle->Directive[Black,FontFamily->"Times",14,Italic]]

3x3

g=KingGraph[3,3]

EdgeLengths[g]//Tally

v=GraphEmbedding[g];

edges=List@@@EdgeList[g];

g3=Graphics[{
EdgeForm[Black],{FaceForm[If[EvenQ[Total[#]],LightGray,White]],Polygon[CirclePoints[#,1/(Sqrt[2]),4]]}&/@v,
Thick,Line[v,edges],
FaceForm[White],Disk[v,.1]
},
PlotLabel->"3×3 king graph",
LabelStyle->Directive[Black,FontFamily->"Times",14,Italic]]

4x4

g=KingGraph[4,4]

EdgeLengths[g]//Tally

v=GraphEmbedding[g];

edges=List@@@EdgeList[g];

g4=Graphics[{
EdgeForm[Black],{FaceForm[If[EvenQ[Total[#]],LightGray,White]],Polygon[CirclePoints[#,1/(Sqrt[2]),4]]}&/@v,
Thick,Line[v,edges],
FaceForm[White],Disk[v,.1]
},
PlotLabel->"4×4 king graph",
LabelStyle->Directive[Black,FontFamily->"Times",14,Italic]]

Combined

GraphicsRow[{g1,g2,g3,g4},ImageSize->750,Alignment->Top]

Layouts

Graphs.m "GridEmbedding"

GraphicsRow[Table[KingGraph[n,n],{n,5}]//StyleGraphs,Dividers->All,ImageSize->500]

Graphs.m "PlanarEmbedding"

GraphicsRow[Table[KingGraph[2,n,GraphLayout->"PlanarEmbedding"],{n,5}]//StyleGraphs,Dividers->All,ImageSize->500]

GraphData

GraphicsRow[Table[GraphData[{"King",{n,n}},"Graph","Grid"][[1]],{n,5}]//StyleGraphs,Dividers->All,ImageSize->500]

GraphicsGrid[Partition[Table[GraphData[{"King",{n,n}},"Graph","Grid"][[1]]//StyleGraphs,{n,20}],5],Dividers->All,ImageSize->500]

Special Cases

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

Construction via strong product

bug(428427): Consider supporting GraphProduct[G, H, "Strong"] as a synonym for GraphProduct[G, H, "Normal"]

DeleteCases[Flatten[Table[{{m,n},GraphData[{"King",{m,n}},"#"],RecognizeGraph@GraphProduct[PathGraph[Range[m]],PathGraph[Range[n]],"Normal"]},{n,5},{m,5}],1],{_,x_,x_}]

bug(425318): GraphProduct could give nicer (nondegenerate) embeddings

GraphProduct[PathGraph[Range[3]],PathGraph[Range[3]],"Normal"]

Graph[EdgeList[%]]

Planar

GraphData[{"King","Planar"}]

GraphicsGrid[Partition[Append[Table[Show[KingGraph[2,n,GraphLayout->"PlanarEmbedding"]//StyleGraphs[#,VertexSize->Scaled[.06]]&,PlotLabel->Row[{2,"×",n}],LabelStyle->Directive[Black,FontFamily->"Times"]],{n,2,8}],
Show[GraphData[{"King",{3,3}},"Graph","Planar"][[1]]//StyleGraphs[#,VertexSize->Scaled[.08]]&,PlotLabel->Row[{3,"×",3}],LabelStyle->Directive[Black,FontFamily->"Times"]]],4],ImageSize->500]

2×n

Table[GraphData[{"King",{2,n}},"Graph","Planar"],{n,2,6}]

Table[GraphData[{"King",{2,n}},"Graph","Planar"],{n,2,10}][[All,1]]

Planar Algorithm

From Ed 2018-10-10

GraphData[{"King",{2,3}},"Graph","Planar"][[1]]

GraphData[{"King",{2,3}},{"V","M"}]

v=Prepend[Most[Join@@Table[CirclePoints[r,3],{r,2}]],{0,0}];
g=System`Graph[Range[Length[v]],UndirectedEdge@@@Sort[{{1,4},{1,2},{1,3},{2,4},{2,3},{3,4},{5,6},{4,5},{2,6},{2,5},{4,6}}],VertexLabels->"Name",VertexCoordinates->v]

RecognizeGraph@g

GraphData[{"King",{2,4}},{"V","M"}]

Table[GraphData[{"King",{2,n}},"V"],{n,3,10}]

Table[GraphData[{"King",{2,n}},"M"],{n,3,10}]

FindSequenceFunction[%,n-2]

Simplify[%]

v=Prepend[Take[Join@@Table[CirclePoints[r,3],{r,3}],7],{0,0}];
g=System`Graph[Range[Length[v]],UndirectedEdge@@@Sort[{{1,4},{1,2},{1,3},{2,4},{2,3},{3,4},{5,6},{4,5},{2,6},{2,5},{4,6},

{5,8},{5,7},{6,7},{7,8},{6,8}
}],VertexLabels->"Name",VertexCoordinates->v]

Through[{VertexCount,EdgeCount}[g]]

RecognizeGraph@g

GraphData[{"King",{2,5}},{"V","M"}]

v=Prepend[Take[Join@@Table[CirclePoints[r,3],{r,4}],9],{0,0}];
g=System`Graph[Range[Length[v]],UndirectedEdge@@@Sort[{
{1,4},{1,2},{1,3},{2,4},{2,3},{3,4},

{2,5},{2,6},{4,5},{4,6},{5,6},

{5,7},{5,8},{6,7},{6,8},{7,8},

{7,9},{7,10},{8,9},{8,10},{9,10}
}],VertexLabels->"Name",VertexCoordinates->v]

Partition[-Subtract@@@{
{2,5},{2,6},{4,5},{4,6},{5,6},

{5,7},{5,8},{6,7},{6,8},{7,8},

{7,9},{7,10},{8,9},{8,10},{9,10}
},5]//Column

Through[{VertexCount,EdgeCount}[g]]

RecognizeGraph@g

v=Prepend[Take[Join@@Table[CirclePoints[r,3],{r,4}],11],{0,0}];
g=System`Graph[Range[Length[v]],UndirectedEdge@@@Sort[{
{1,4},{1,2},{1,3},{2,4},{2,3},{3,4},
{2,5},{2,6},{4,5},{4,6},{5,6},
{5,7},{5,8},{6,7},{6,8},{7,8},
{7,9},{7,10},{8,9},{8,10},{9,10},
{9,11},{9,12},{10,11},{10,12},{11,12}
}],VertexLabels->"Name",VertexCoordinates->v]

RecognizeGraph[g]

{2,3,1,2,1}

{
{2i-3,2i-3+2},
{2i-3,2i-3+3},
{2i-3+1,2i-3+1+1},
{2i-3+1,2i-3+1+2},
{2i-1,2i}
}

KingGraph2[1]:=System`Graph[{1},{},VertexCoordinates->{{0,0}}]
KingGraph2[n_]:=Module[{v=Prepend[Take[Join@@Table[CirclePoints[r,3],{r,Ceiling[2n/3]}],2n-1],{0,0}],
e0=Take[{{1,4},{1,2},{1,3},{2,4},{2,3},{3,4},
{2,5},{2,6},{4,5},{4,6},{5,6}},UpTo[5n-4]],
e=Flatten[Table[{{-3+2 i,-1+2 i},{-3+2 i,2 i},{-2+2 i,-1+2 i},{-2+2 i,2 i},{-1+2 i,2 i}},{i,4,n}],1]
},
System`Graph[Range[2n],UndirectedEdge@@@Join[e0,e],VertexCoordinates->v,VertexLabels->None]
]

GraphicsGrid[Partition[kings=Table[KingGraph2[n],{n,10}],UpTo[4]],ImageSize->500]

RecognizeGraph/@kings

RectilinearCrossingNumber/@kings

GetGraphData[{"King",{2,6}},"File"]

Embeddings

<<MathWorld`Graphs`

{"King", {1, 1}} == "SingletonGraph"

GraphData[{"King",{1,1}},"StandardName"]

{"King", {1, 2}} == {"Path", 2}

GraphData[{"King",{1,2}},"StandardName"]

{"King", {1, 3}} == {"Path", 3}

GraphData[{"King",{1,3}},"StandardName"]

{"King", {1, 4}} == {"Path", 4}

GraphData[{"King",{1,4}},"StandardName"]

{"King", {1, 5}} == {"Path", 5}

GraphData[{"King",{1,5}},"StandardName"]

{"King", {1, 6} == {"Path", 6}

GraphData[{"King",{1,6}},"StandardName"]

{"King", {1, 7}} == {"Path", 7}

GraphData[{"King",{1,7}},"StandardName"]

{"King", {1, 8}} == {"Path", 8}

GraphData[{"King",{1,8}},"StandardName"]

{"King", {1, 9}} == {"Path", 9}

GraphData[{"King",{1,9}},"StandardName"]

{"King", {1, 10}} == {"Path", 10}

GraphData[{"King",{1,10}},"StandardName"]

{"King", {2, 2}} == "TetrahedralGraph"

GraphData[{"King",{2,2}},"StandardName"]

{"King", {2, 3}}

Names

GraphData[{"King",{2,3}},"StandardName"]

GraphData[{"King",{2,3}},"StandardNames"]

Primary

GraphData[{"King",{2,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"King",{2,3}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"King",{2,3}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"King",{2,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"King",{2,3}},"Edges"]

v=Join[{{-1,0},{0,-1},{1,0},{0,1}},Subdivide[{-1,0},{1,0},3][[2;;-2]]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[4,1,2,3,4,5,2,6,4,2],{1,5},{3,6}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"King",{2,3}},"Graph","Degenerate"]//StyleGraphs

IGraph

GraphData[{"King",{2,3}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"King",{2,3}},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"King",{2,3}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

GraphData[{"King",{2,3}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"King",{2,3}},"Hamiltonian"]

GraphData[{"King",{2,3}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"King",{2,3}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"King",{2,3}}],#]&/@hc);//Timing

sym={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[sym[[All,-1]]]

DeleteCases[sym,{_,TransformationGroup[{}]}]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"King",{2,3}},"Planar"]

GraphData[{"King",{2,3}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"King",{2,3}}],Method->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"King",{2,3}}]],10]

PlanarGraphEmbeddings

GraphData[{"King",{2,3}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"King",{2,3}}],Debug->True])//Timing

Length[plemb]

MinimalCrossing

GraphData[{"King",{2,3}},{"RCN","CN"}]

GraphData[{"King",{2,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

g=RotateGraph[MinimalCrossingGraph[GraphData[{"King",{2,3}}],"CrossingNumber"->-1]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"King",{2,3}},"Circulant"]

GraphData[{"King",{2,3}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"King",{2,3}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"King",{2,3}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"King",{2,3}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"King",{2,3}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"King",{2,3}},"Line"]

LineGraphQ[GraphData[{"King",{2,3}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"King",{2,3}}&]

RootGraph[GraphData[{"King",{2,3}}]]

RecognizeGraph[%]

Halin

GraphData[{"King",{2,3}},"Halin"]

GraphData[{"King",{2,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"King",{2,3}},"Rigid"]

GraphData[{"King",{2,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"King",{2,3}},"Flexible"]

GraphData[{"King",{2,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"King",{2,3}},"LCF"]

GraphData[{"King",{2,3}},"HamiltonianCycleCount"]

GraphData[{"King",{2,3}},"LCFSignature"]

GraphData[{"King",{2,3}},"LCFNotations"]

GraphData[{"King",{2,3}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

UnitDistance

GraphData[{"King",{2,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"King",{2,3}}],Debug->True]//Timing

GraphData[{"King",{2,3}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"King",{2,3}},"Matchstick"]

GraphData[{"King",{2,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"King",{2,3}},"Edges"]]

3D All

GraphData[{"King",{2,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"King",{2,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"King",{2,3}},"Polyhedral"]

GraphData[{"King",{2,3}},"Graph",{"3D","Polyhedron"}]

{"King", {2, 4}}

Names

GraphData[{"King",{2,4}},"StandardName"]

GraphData[{"King",{2,4}},"StandardNames"]

Primary

GraphData[{"King",{2,4}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

Select[GraphData[{"King",{2,4}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"King",{2,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"King",{2,4}},"Edges"]

v=Join[CirclePoints[{1,Pi/2},6],#{-1/4,0}&/@{-1,1}];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[4,6,8,2,4,7,8,1,3,7,5,1],{2,6},{3,5},{4,8},{1,4},{1,7}},VertexCoordinates->v,VertexLabels->Automatic]

GraphPlot@

v=Join[CirclePoints[3],CirclePoints[1/2,3],{{0,0}}];
AppendTo[v,Mean[v[[{1,4}]]]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,1,8,4,5,6,4,7,5],e[3,8,2,6],{2,4},{6,7},{6,8}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

GraphPlot@

v={{0,0},{1/2,0},{1,0},{1/2,Sqrt[3]/2}};
v=Join[v,{Mean[v[[{1,2,4}]]]}];
v=Join[v,v[[4]]+Normalize[#-v[[4]]]2/3&/@(Subdivide[v[[3]],v[[2]],3][[2;;-2]])];
AppendTo[v,v[[4]]+(Mean[v[[{6,7}]]]-v[[4]])/2];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,1,5,2],e[5,4,2,8,4],e[8,7,6,8,3,7],{3,6}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

GraphPlot@RotateGraph[,-.1]

v=CirclePoints[8];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,4,5,8,1,3,6,8,4,2,7,5,1,6],e[7,4],{3,8},{2,5}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

GraphPlot@

Solve[(2y)^2==SquaredEuclideanDistance[{-1,0},{-x,y}],y]

x=1/3;
y=((Abs[-1+x])/(Sqrt[3]));
v=Join[CirclePoints[{1,Pi/2},4],{{-x,y},{-x,-y}}];
v=Join[v,Mean[v[[#]]]&/@{{2,5,6},{1,3,4}}];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,3,4,1,8,3,2,1,6,5,2,6,7,5],{4,8},{3,6},{2,7}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Degenerate

GraphData[{"King",{2,4}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"King",{2,4}},"Graph","Degenerate"]

Configuration

GraphData[{"King",{2,4}},"Configuration"]

GraphData[{"King",{2,4}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"King",{2,4}},"Graph","Perspective"]//StyleGraphs

HoneycombToroidal construction

GraphData[{"King",{2,4}},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"King",{2,4}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"King",{2,4}},"Graph","IGraph"]//StyleGraphs

Bilateral

gs=GraphData[{"King",{2,4}},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingQ[#],GraphSymmetryGroup[#]}&/@GraphData[{"King",{2,4}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,Left}}]

Circular

GraphData[{"King",{2,4}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"King",{2,4}},"Hamiltonian"]

GraphData[{"King",{2,4}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"King",{2,4}}],All][[All,All,1]]]

circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"King",{2,4}}],#]&/@hc

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"King",{2,4}},"Planar"]

GraphData[{"King",{2,4}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"King",{2,4}}],Method->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"King",{2,4}}]],10]

PlanarGraphEmbeddings

(plemb=PlanarGraphEmbeddings[GraphData[{"King",{2,4}}]])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"King",{2,4}}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"King",{2,4}}],"OuterFace"->#]&/@faces

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{}

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

RecognizeGraph/@gs

MinimalCrossing

GraphData[{"King",{2,4}},{"RCN","CN"}]

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

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"King",{2,4}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"King",{2,4}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"King",{2,4}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"King",{2,4}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"King",{2,4}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"King",{2,4}}],TimeConstraint->86400])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"King",{2,4}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[g,"OuterFace"->#]&/@faces

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"King",{2,4}},"V"]&]

(gs=Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"King",{2,4}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"King",{2,4}},"V"]&]])//Timing

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"King",{2,4}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"King",{2,4}},"LocalCrossingNumber"]

GraphData[{"King",{2,4}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData[{"King",{2,4}}],TimeConstraint->10])//AbsoluteTiming

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"King",{2,4}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"King",{2,4}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"King",{2,4}},"Circulant"]

GraphData[{"King",{2,4}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"King",{2,4}},"ComplementGraph","Name"]

Line graph

GraphData[{"King",{2,4}},"Line"]

LineGraphQ[GraphData[{"King",{2,4}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"King",{2,4}}&]

RootGraph[GraphData[{"King",{2,4}}]]

RecognizeGraph[%]

Halin

GraphData[{"King",{2,4}},"Halin"]

GraphData[{"King",{2,4}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"King",{2,4}},"Rigid"]

GraphData[{"King",{2,4}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"King",{2,4}},"Flexible"]

GraphData[{"King",{2,4}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"King",{2,4}},"LCF"]

GraphData[{"King",{2,4}},"HamiltonianCycleCount"]

GraphData[{"King",{2,4}},"LCFSignature"]

GraphData[{"King",{2,4}},"LCFNotations"]

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

Tally[LCFNotation[#][[2]]&/@%]

UnitDistance

GraphData[{"King",{2,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"King",{2,4}}],Debug->True]//Timing

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"King",{2,4}},"VertexList"],GraphData[{"King",{2,4}},"EdgeList"]],MaxIterations->500]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"King",{2,4}},"Graph",#]&/@{"All","UnitDistance"})

LabelGraph@

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"King",{2,4}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"King",{2,4}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"King",{2,4}},"Edges"]]

3D All

GraphData[{"King",{2,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"King",{2,4}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"King",{2,4}},"Polyhedral"]

GraphData[{"King",{2,4}},"Graph",{"3D","Polyhedron"}]

{"King", {2, 5}}

Names

GraphData[{"King",{2,5}},"StandardName"]

GraphData[{"King",{2,5}},"StandardNames"]

Primary

GraphData[{"King",{2,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"King",{2,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"King",{2,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"King",{2,5}}]]

Default embedding

GraphPlot[Graph[GraphData[{"King",{2,5}},"VertexList"],GraphData[{"King",{2,5}},"Edges"]]]

GraphPlot[Graph[GraphData[{"King",{2,5}},"VertexList"],GraphData[{"King",{2,5}},"Edges"]],GraphLayout->"TutteEmbedding"]

GraphPlot@

h=3/4;
v={{-1,0},{1,0},{0,Sqrt[3]},{-1/4,h},{1/4,h}};
m=Mean[v[[{1,4}]]];
v=Join[v,Most@Subdivide[{0,0},m,3],Subdivide[{0,0},{-1,1}m,3][[2;;-2]]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,6,2,3,1,4,3,5,2,10,5,6,4,8,1,7,4],{7,8},e[2,9,10],{9,5},{3,6}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Degenerate

GraphData[{"King",{2,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"King",{2,5}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"King",{2,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"King",{2,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"King",{2,5}},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"King",{2,5}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

GraphData[{"King",{2,5}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"King",{2,5}},"Hamiltonian"]

GraphData[{"King",{2,5}},"HamiltonianCycleCount"]

GraphData[{"King",{2,5}},"LCF"]

Length[hc=FindHamiltonianCycle[GraphData[{"King",{2,5}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"King",{2,5}}],#]&/@hc);//Timing

sym={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[sym[[All,-1]]]

DeleteCases[sym,{_,TransformationGroup[{}]}]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"King",{2,5}},"Planar"]

GraphData[{"King",{2,5}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"King",{2,5}}],Method->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"King",{2,5}}]],10]

PlanarGraphEmbeddings

GraphData[{"King",{2,5}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"King",{2,5}}],Debug->True])//Timing

Length[plemb]

MinimalCrossing

GraphData[{"King",{2,5}},{"RCN","CN"}]

GraphData[{"King",{2,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"King",{2,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"King",{2,5}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"King",{2,5}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"King",{2,5}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"King",{2,5}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"King",{2,5}}],TimeConstraint->86400])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"King",{2,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[g,"OuterFace"->#]&/@faces

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"King",{2,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"King",{2,5}},"V"]&]

(gs=Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"King",{2,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"King",{2,5}},"V"]&]])//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"King",{2,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"King",{2,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"King",{2,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"King",{2,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"King",{2,5}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"King",{2,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"King",{2,5}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData[{"King",{2,5}}],TimeConstraint->10])//AbsoluteTiming

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"King",{2,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"King",{2,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"King",{2,5}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"King",{2,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"King",{2,5}},"Circulant"]

GraphData[{"King",{2,5}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"King",{2,5}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"King",{2,5}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"King",{2,5}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"King",{2,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"King",{2,5}},"Line"]

LineGraphQ[GraphData[{"King",{2,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"King",{2,5}}&]

RootGraph[GraphData[{"King",{2,5}}]]

RecognizeGraph[%]

Halin

GraphData[{"King",{2,5}},"Halin"]

GraphData[{"King",{2,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"King",{2,5}},"Rigid"]

GraphData[{"King",{2,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"King",{2,5}},"Flexible"]

GraphData[{"King",{2,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"King",{2,5}},"LCF"]

GraphData[{"King",{2,5}},"HamiltonianCycleCount"]

GraphData[{"King",{2,5}},"LCFSignature"]

GraphData[{"King",{2,5}},"LCFNotations"]

GraphData[{"King",{2,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

UnitDistance

GraphData[{"King",{2,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"King",{2,5}}],Debug->True]//Timing

GraphData[{"King",{2,5}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"King",{2,5}},"VertexList"],GraphData[{"King",{2,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"King",{2,5}},"Graph",#]&/@{"All","UnitDistance"})

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"King",{2,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"King",{2,5}},"Matchstick"]

GraphData[{"King",{2,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"King",{2,5}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"King",{2,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"King",{2,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"King",{2,5}},"Polyhedral"]

GraphData[{"King",{2,5}},"Graph",{"3D","Polyhedron"}]

{"King", {3, 3}}

GraphData[{"King",{3,3}},"StandardName"]

Primary

GraphData[{"King",{3,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"King",{3,3}},"Graph","All"]//StyleGraphs

Planar

GraphData[{"King",{3,3}},"Planar"]

GraphData[{"King",{3,3}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"King",{3,3}},{"RCN","CN"}]

GraphData[{"King",{3,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"King",{3,3}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"King",{3,3}}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"King",{3,3}}],"OuterFace"->#]&/@faces

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{,,}

Tutte embedding construction 4

GraphPlot[RotateGraph[]]

v=Join[CirclePoints[{Csc[Pi/4]/2,-Pi/2},4],CirclePoints[1/4,4],{{0,0}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,1,5,2,6,3,7,4,8,1],e[8,9,6],e[7,9,5],e[4,9,2],e[3,9,1]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Tutte embedding construction 3 #1

GraphPlot[RotateGraph[,2Pi/3]]

v={{-1,0},{1,0},{0,Sqrt[3]},{-1/2,1/4},{-1/2+1/3,1/4},{-1/2+2/3,1/4},{1/2,1/4},{0,5/8},{0,1}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,1,4,5,6,7,2,9,1,5,8,6,2],e[4,9,7],e[8,9,3],e[5,9,6]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Tutte embedding construction 3 #2

GraphPlot[RotateGraph[,2Pi/3]]

v=Join[{{-1,0},{1,0},{0,Sqrt[3]}},{#,#2-0/8}&@@@{{0,1/4},{0,1/2},{1/8,1/2},{0,3/4},{1/8,3/4},{0,1}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,1,4,2,5,6,7,8,9,3],e[5,1,9,7,5,4],e[6,2,8],e[7,2,9]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Halin

GraphData[{"King",{3,3}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"King",{3,3}},"LCFSignature"]

GraphData[{"King",{3,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"King",{3,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"King",{3,3}}],Debug->True]//Timing

GraphData[{"King",{3,3}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"King",{3,3}},"Graph","Matchstick"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"King",{3,3}},"Edges"]

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

RecognizeGraph[g]

3D default

Graph3D[GraphData[{"King",{3,3}},"Edges"]]

3D All

GraphData[{"King",{3,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"King",{3,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"King",{3,3}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"King",{3,3}},"Polyhedron"]}]

3D Canonical

GraphData[{"King",{3,3}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"King",{3,3}},"Polyhedron"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"King",{3,3}}],-1]}]

(can=FindCanonicalPolyhedron[poly,WorkingPrecision->1000,MaxIterations->10000,PrecisionGoal->20])//Timing

SimplePolyhedronQ[can]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

{"King", {3, 7}}

GraphData[{"King",{3,7}},"StandardName"]

Primary

GraphData[{"King",{3,7}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"King",{3,7}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"King",{3,7}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"King",{3,7}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"King",{3,7}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"King",{3,7}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"King",{3,7}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"King",{3,7}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"King",{3,7}},"Planar"]

GraphData[{"King",{3,7}},"Graph","Planar"]//StyleGraphs

Minimal crossing construction Davidson-Hare

g0=MinimalCrossingGraph[GraphData[{"King",{3,7}}],"CrossingNumber"->4]

g1=IGLayoutDavidsonHarel[
IGVertexMap[#&,VertexCoordinates->(Rescale@GraphEmbedding[#,"PlanarEmbedding"]&),g0],
"Continue"->True,"EdgeCrossingWeight"->1000
]

GraphPlot@g1

GraphPlot@HighlightGraph[RotateGraph[GraphicsToGraph@,{10,16}],Range[22,25]]

g0=
LabelGraph@EdgeAdd[VertexDelete[GraphicsToGraph@,Range[22,25]],UndirectedEdge@@@{{10,11},{3,4},{10,9},{16,17},{12,11},{19,18},{13,12},{5,6}}]

v=GraphEmbedding[g0];
replacements=Join[
Thread[{10,4,5,13}->Subdivide[v[[10]],v[[13]],3]],
Thread[{6,12,18,17,9}->Subdivide[v[[6]],v[[9]],4]],
Thread[{6,14,20,19,11,3,2}->Subdivide[v[[6]],v[[2]],6]],
{1->Mean[v[[{2,8,9}]]]}];

replacements

g=Annotate[g,VertexCoordinates->ReplacePart[GraphEmbedding[g0],replacements]]

RecognizeGraph@g

RectilinearCrossingCount@g

MinimalCrossing

GraphData[{"King",{3,7}},{"RCN","CN"}]

GraphData[{"King",{3,7}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"King",{3,7}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"King",{3,7}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

GraphPlot[,VertexSize->1]

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"King",{3,7}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"King",{3,7}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"King",{3,7}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@MinimalCrossingGraph[GraphData[{"King",{3,7}}],"CrossingNumber"->4]

GraphicsToGraph@

GraphPlot[HighlightGraph[,Range[22,26]],VertexSize->.4]

With[{x=GraphEmbedding[g][[22]],dx=.1},Show[Annotate[g,VertexSize->10],PlotRange->({-1,1}dx+#&/@x)]]

IGraphM`IGLayoutTutte@IGraphM`IGEdgeMap[Apply[EuclideanDistance],EdgeWeight->IGraphM`IGEdgeVertexProp[VertexCoordinates],g]

Manipulate[
IGraphM`IGLayoutTutte[
IGraphM`IGEdgeMap[(EuclideanDistance@@#)^power&,EdgeWeight->IGraphM`IGEdgeVertexProp[VertexCoordinates],g],
VertexSize->{"Scaled",.01}
],
{{power,1},-3,3}
]

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"King",{3,7}},"Circulant"]

GraphData[{"King",{3,7}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"King",{3,7}},"Halin"]

GraphData[{"King",{3,7}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"King",{3,7}},"LCF"]

GraphData[{"King",{3,7}},"LCFSignature"]

GraphData[{"King",{3,7}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"King",{3,7}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"King",{3,7}}],Debug->True]//Timing

GraphData[{"King",{3,7}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"King",{3,7}},"VertexList"],GraphData[{"King",{3,7}},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]]]&/@Complement@@(GraphData[{"King",{3,7}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"King",{3,7}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"King",{3,7}},"Matchstick"]

GraphData[{"King",{3,7}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"King",{3,7}},"Edges"]]

3D All

GraphData[{"King",{3,7}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"King",{3,7}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"King",{3,7}},"Polyhedral"]

GraphData[{"King",{3,7}},"Graph",{"3D","Polyhedron"}]

{"King", {3, 8}}

Names

GraphData[{"King",{3,8}},"StandardName"]

GraphData[{"King",{3,8}},"StandardNames"]

Primary

GraphData[{"King",{3,8}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"King",{3,8}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"King",{3,8}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"King",{3,8}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"King",{3,8}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"King",{3,8}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"King",{3,8}},"Graph","Degenerate"]

Bilateral

GraphData[{"King",{3,8}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"King",{3,8}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"King",{3,8}},"Planar"]

GraphData[{"King",{3,8}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"King",{3,8}},{"RCN","CN"}]

GraphData[{"King",{3,8}},"Graph","MinimalCrossing"]//StyleGraphs

Minimal crossing construction Davidson-Hare

g0=MinimalCrossingGraph[GraphData[{"King",{3,8}}],"CrossingNumber"->5]

g1=IGLayoutDavidsonHarel[
IGVertexMap[#&,VertexCoordinates->(Rescale@GraphEmbedding[#,"PlanarEmbedding"]&),g0],
"Continue"->True,"EdgeCrossingWeight"->1000
]

GraphPlot@g1

GraphPlot@HighlightGraph[RotateGraph[GraphicsToGraph@,π],Range[24,29]]

g0=
LabelGraph@EdgeAdd[VertexDelete[GraphicsToGraph@,Range[24,29]],UndirectedEdge@@@{{3,2},{10,11},{4,5},{13,12},{20,19},{12,11},{21,22},{13,14},{15,14},{6,7}}]

RecognizeGraph@g0

v=GraphEmbedding[g0];
replacements=Join[
Thread[{10,4,5,13}->Subdivide[v[[10]],v[[13]],3]],
Thread[{6,12,18,17,9}->Subdivide[v[[6]],v[[9]],4]],
Thread[{6,14,20,19,11,3,2}->Subdivide[v[[6]],v[[2]],6]],
{1->Mean[v[[{2,8,9}]]]}];

replacements

g=Annotate[g,VertexCoordinates->ReplacePart[GraphEmbedding[g0],replacements]]

RecognizeGraph@g

RectilinearCrossingCount@g

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"King",{3,8}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"King",{3,8}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"King",{3,8}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"King",{3,8}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"King",{3,8}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"King",{3,8}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"King",{3,8}},"Circulant"]

GraphData[{"King",{3,8}},"Graph","Circulant"]//StyleGraphs

Circulant construction

CirculantGraph1@@@CirculantIndices[GraphData[{"King",{3,8}}]]

gs=CirculantGraph1@@@Cases[GraphData[{"King",{3,8}},"StandardNames"],{"Circulant",i_}:>i]

Line graph

GraphData[{"King",{3,8}},"Line"]

LineGraphQ[GraphData[{"King",{3,8}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"King",{3,8}}&]

RootGraph[GraphData[{"King",{3,8}}]]

Halin

GraphData[{"King",{3,8}},"Halin"]

GraphData[{"King",{3,8}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"King",{3,8}},"Rigid"]

GraphData[{"King",{3,8}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"King",{3,8}},"Flexible"]

GraphData[{"King",{3,8}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"King",{3,8}},"LCF"]

GraphData[{"King",{3,8}},"HamiltonianCycleCount"]

GraphData[{"King",{3,8}},"LCFSignature"]

GraphData[{"King",{3,8}},"LCFNotations"]

GraphData[{"King",{3,8}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"King",{3,8}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"King",{3,8}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

(gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFGraph@#,#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,1}]]}])//Timing

Length[gs]

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"King",{3,8}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"King",{3,8}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"King",{3,8}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

(gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFGraph@#,#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,1}]]}])//Timing

Length[gs]

i=0;
gs={};
t0=AbsoluteTime[];
count=Length[order2];
Monitor[
Do[
If[!MissingQ[g=BilateralLCFGraph[LCFGraph@@order2[[i]]]],AppendTo[gs,g]],
{i,count}
],
Column[{
ProgressIndicator[i,{1,count}],
Row[{i,"/",count}],
Row[{"estimated time remaining: ",Round[(AbsoluteTime[]-t0) (count/i-1)]," s"}],
Row[{Length[gs]," bilateral graphs"}]
}]
];//Timing

UnitDistance

GraphData[{"King",{3,8}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"King",{3,8}}],Debug->True]//Timing

GraphData[{"King",{3,8}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"King",{3,8}},"VertexList"],GraphData[{"King",{3,8}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"King",{3,8}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"King",{3,8}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"King",{3,8}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"King",{3,8}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"King",{3,8}}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"King",{3,8}},"Matchstick"]

GraphData[{"King",{3,8}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"King",{3,8}},"Edges"]]

3D All

GraphData[{"King",{3,8}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"King",{3,8}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"King",{3,8}},"Polyhedral"]

{"King", {4, 4}}

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

All

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

LCF

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

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

UnitDistance

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

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

MinimalCrossing

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

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

3D

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

Default embedding

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

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@(g0=RotateGraph[MinimalCrossingGraph[GraphData[{"King",{4,4}}],"CrossingNumber"->4],Pi/4])

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

VertexDegree[g0]//Sort//Tally

RecognizeGraph[g]

RectilinearCrossingCount[g]

Properties 2×n

ConnectedInducedSubgraphCount

A290764

seq=Table[GraphData[{"King",Sort[{2,n}]},"ConnectedInducedSubgraphCount"],{n,10}]

FindLinearRecurrence[seq]

LinearRecurrence[{5,-7,3},{3,15,54},40]

FindSequenceFunction[seq,n]//FullSimplify

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

gf=x FindGeneratingFunction[seq,x]

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

IndependentEdgeSetCount

A052978

seq=Table[GraphData[{"King",Sort[{2,n}]},"IndependentEdgeSetCount"],{n,10}]

FindLinearRecurrence[seq]

LinearRecurrence[{4,2,-4},{2,10,40},{0,20}]

FindSequenceFunction[seq,n]//FullSimplify

f1=4-2 #1-4 ((#1)^2)+((#1)^3)&;
f2=-4+47 #1-158 ((#1)^2)+158 ((#1)^3)&;
pos={2,1,3};

Table[Sum[((Root[f1,k])^n)Root[f2,pos[[k]]],{k,Length[pos]}],{n,10}]//N//Chop

an=ToNumberField[Root[f2,pos[[#]]],Root[f1,#]]&/@Range[Length[pos]];

Equal@@Last/@an

RootSum[f1,Evaluate[((#)^(n+Range[Length[pos]]-1)).an[[1,2]]]&]

seq=Table[RootSum[4-2 #-4 #^2+#^3&,30 #^n-13 #^(n+1)+6 #^(n+2)&]/158,{n,0,10}]

Sum(-1/158*(-11-42*r+24*r^2)*r^(-1-n) where r=RootOf(1-4*_Z-2*_Z^2+4*_Z^3)

seq=158Table[RootSum[1-4#-2#^2+4#^3&,-1/158*(-11-42*#+24*#^2)*#^(-1-n)&]/158,{n,0,10}]

seq=Table[RootSum[1-4#-2#^2+4#^3&,(11+42#-24#^2)/#^(n+1)&]/158,{n,0,10}]

gf=x FindGeneratingFunction[seq,x]

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

IndependentVertexSetCount

A001045

Jacobsthal numbers

seq=Table[GraphData[{"King",Sort[{2,n}]},"IndependentVertexSetCount"],{n,10}]

FindLinearRecurrence[seq]

LinearRecurrence[{1,2},{3,5},20]

FindSequenceFunction[seq,n]//FullSimplify

seq=Table[((2^n)-(((-1))^n))/3,{n,0,20}]

gf=x FindGeneratingFunction[seq,x]

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

MaximalIndependentVertexSetCount

A107383

seq=Table[GraphData[{"King",Sort[{2,n}]},"MaximalIndependentVertexSetCount"],{n,10}]

FindLinearRecurrence[DeleteMissing@seq]

LinearRecurrence[{0,2,2},{2,4,6},20]

gf=x FindGeneratingFunction[seq,x]

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

FindSequenceFunction[seq,n]//FullSimplify

f1=-2-2 #1+((#1)^3)&;
f2=-1-3 #1-19 ((#1)^2)+19 ((#1)^3)&;
pos=Range[3];

Table[Sum[((Root[f1,k])^n)Root[f2,pos[[k]]],{k,Length[pos]}],{n,10}]//N//Chop

an=ToNumberField[Root[f2,pos[[#]]],Root[f1,#]]&/@Range[Length[pos]]

Equal@@Last/@an

RootSum[f1,Evaluate[((#)^(n+Range[Length[pos]]-1)).an[[1,2]]]&]

Table[RootSum[-2-2 #+((#)^3)&,5 ((#)^n)+8 ((#)^(n+1))+((#)^(n+2))&]/19,{n,20}]

MinimalDominatingSetCount

A286850

seq=Table[GraphData[{"King",Sort[{2,n}]},"MinimalDominatingSetCount"],{n,10}]

seq={2,4,6,16,20,52,80,176,296,592,1104,2064,3936,7296,14048,25984,49600,92736,175872,330240,623232,1175296,2213632,4176128,7863808,14838784,27948544,52707328,99320832,187257856,352940032,665276416,1254090752,2363805696,4455927808};

FindLinearRecurrence[DeleteMissing@seq]

LinearRecurrence[{0,2,2,4,0,-8},{2,4,6,16,20,52},20]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[seq,x]

Series[gf=2*x*(1+2*x+x^2+2*x^3-4*x^4-4*x^5)/(1-2*x^2-2*x^3-4*x^4+8*x^6),{x,0,20}]

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

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

terms=List@@%80;

N[terms/.n->0]//Chop

terms[[All,1]]/.n->1//N

RootApproximant[ r=(-8+2 ((Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,1])^3)+2 ((Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,1])^4)+((Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,1])^5))/((Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,1]-Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,2]) (Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,1]-Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,3]) (Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,1]-Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,4]) (Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,1]-Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,5]) (Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,1]-Root[8-4 ((#1)^2)-2 ((#1)^3)-2 ((#1)^4)+((#1)^6)&,6]))]

N[Root[2-22 #1+26 ((#1)^2)-3 ((#1)^3)+18 ((#1)^4)-18 ((#1)^5)-15 ((#1)^6)+15 ((#1)^7)&,2]-r,200]

Properties m×n

ConnectedDominatingSetCount

A291873

Table[GraphData[{"King",{m,n}},"ConnectedDominatingSetCount"],{n,10},{m,n}]//Column

data=Import["https://oeis.org/A291873/b291873.txt","Table"][[All,2]];

Table[data[[Binomial[i,2]+(1/2) (j-1) (2 i+j)+1]],{i,10},{j,i}]//Column

MinimalDominatingSetCount

A286849

data=Import["https://oeis.org/A286849/b286849.txt","Table"][[All,2]];

Table[data[[Binomial[i,2]+(1/2) (j-1) (2 i+j)+1]],{i,10},{j,If[i==10,8,i]}]//Column

Table[GraphData[{"King",{m,n}},"MinimalDominatingSetCount"],{n,10},{m,n}]//Column

Properties n×n

Acyclic

seq=Table[GraphData[{"King",{n,n}},"Acyclic"],{n,20}]

AdjacencyMatrixCount

seq=Table[GraphData[{"King",{n,n}},"AdjacencyMatrixCount"],{n,20}]

Table[(((n^2)!)/(Piecewise[{{1,n==1},{24,n==2}},8])),{n,20}]

Arboricity

seq=Table[GraphData[{"King",{n,n}},"Arboricity"],{n,20}]

ArcTransitive

seq=Table[GraphData[{"King",{n,n}},"ArcTransitive"],{n,20}]

ArcTransitivity

seq=Table[GraphData[{"King",{n,n}},"ArcTransitivity"],{n,20}]

AutomorphismCount

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

BalabanIndex

seq=Table[GraphData[{"King",{n,n}},"BalabanIndex"],{n,4}]

MinimalPolynomial[#,x]&/@%

Bandwidth

seq=Table[GraphData[{"King",{n,n}},"Bandwidth"],{n,20}]

Block

seq=Table[GraphData[{"King",{n,n}},"Block"],{n,20}]

BridgeCount

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

BurningNumber

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

CharacteristicPolynomial

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

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

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]

Chordal

seq=Table[GraphData[{"King",{n,n}},"Chordal"],{n,20}]

ChordCount

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

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

Chordless

seq=Table[GraphData[{"King",{n,n}},"Chordless"],{n,20}]

ChordlessCycleCount

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

FindSequenceFunction[seq,n]

Chords

seq=Table[GraphData[{"King",{n,n}},"Chords"],{n,20}]

ChromaticInvariant

A295177

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

FindSequenceFunction[Drop[seq,2],n]

ChromaticNumber

Table[GraphData[{"King",{n,n}},"ChromaticNumber"],{n,20}]

ChromaticPolynomial

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

CoefficientList[Take[poly,4],x]

coef=Factor/@FindLinearRecurrence[DeleteMissing@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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Circumference

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

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

Classes

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

ClawFree

seq=Table[GraphData[{"King",{n,n}},"ClawFree"],{n,20}]

CliqueCount

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

FindSequenceFunction[seq,n]

(1+x) (1+x (-1+(n^2)+3 (((-1+n))^2) x+(((-1+n))^2) (x^2)))/.x->1//Factor

CliqueCoveringNumber

A008794

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

Table[Ceiling[n/2]^2,{n,20}]

Table[CliqueCoveringNumber[KingGraph[n,n]],{n,5}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers&&n>0]

gf=x FindGeneratingFunction[seq,x]

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

CliqueNumber

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

CliquePolynomial

(poly=Factor[Table[GraphData[{"King",{n,n}},"CliquePolynomial"],{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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

CochromaticGraphNames

Table[GraphData[{"King",{n,n}},"CochromaticGraphNames"],{n,20}]//Column

Select[GraphData["King"],GraphData[#,"ChromaticallyUnique"]=!=False&]

ComplementOddChordlessCycleCount

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

FindSequenceFunction[Take[seq,{3,5}],n]

ConnectedComponentCount

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

ConnectedDominatingSetCount

A289180

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

FindLinearRecurrence[seq]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

gf=x FindGeneratingFunction[seq,x]

ConnectedDominationNumber

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

FindSequenceFunction[seq,n]

ConnectedDominationPolynomial

(poly=Table[GraphData[{"King",{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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

ConnectedInducedSubgraphCount

A286139

seq=Table[GraphData[{"King",{n,n}},"ConnectedInducedSubgraphCount"],{n,20}]

seq={1,15,388,37196,14765089,24076152503,159850328891568,4290837646252661680,463376724731585422732393,200665409586497566263900755703,347694350828123116321061347501951972,2406781070555276417850396576804205226358828,66481859567653621586313146932097075651519991887257};

FindLinearRecurrence[seq]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

ConnectedInducedSubgraphPolynomial

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

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

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]

CrossingNumber

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

gf=x FindGeneratingFunction[seq,x]

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

GraphData[{"King",{4,4}},"Graph","MinimalCrossing"]

GraphData[{"King",{5,5}},"Graph","MinimalCrossing"]

CycleCount

A234622

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

FindLinearRecurrence[seq]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

CyclePolynomial

(poly=Factor[Table[GraphData[{"King",{n,n}},"CyclePolynomial"],{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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Cyclic

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

CyclomaticNumber

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

FindSequenceFunction[seq,n]

DetourIndex

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

FindSequenceFunction[DeleteMissing@seq,n]//Factor

DetourPolynomial

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

FindSequenceFunction[{3,8,15,24,35,48,63,80,99},n-1]//Factor

Table[With[{k=(-1+n) (1+n)},(x-(k^2))(((k+x))^k)],{n,20}]==poly

Diameter

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

Disconnected

GraphData[{"King","Disconnected"}]

DisorderNumber

seq=Table[GraphData[{"King",{n,n}},"DisorderNumber"],{n,20}]

DistancePolynomial

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

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

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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

DistinguishingNumber

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

DomaticNumber

Inferred for n > 10 (?):

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

DominatingSetCount

A133791

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

FindLinearRecurrence[seq]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

DominationNumber

A075561

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

seq=Table[Floor[(n+2)/3]^2,{n,50}]

FindLinearRecurrence[seq]

LinearRecurrence[{1,0,2,-2,0,-1,1},{1,1,1,4,4,4,9},20]

gf=x FindGeneratingFunction[seq,x]

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

DominationPolynomial

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

CoefficientList[Take[poly,4],x]

coef=Factor/@FindLinearRecurrence[DeleteMissing@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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

EdgeChromaticNumber

Table[GraphData[{"King",{n,n}},"EdgeChromaticNumber"],{n,20}]

EdgeConnectivity

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

EdgeCount

A002943

seq=Table[GraphData[{"King",{n,n}},"EdgeCount"],{n,20}]

FindSequenceFunction[seq,n]//Factor

EdgeCoverCount

A297056

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

EdgeCoverNumber

A000982

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

Table[If[n==1,0,Ceiling[n^2/2]],{n,20}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

EdgeCoverPolynomial

(poly=Factor[Table[GraphData[{"King",{n,n}},"EdgeCoverPolynomial"],{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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

EulerianCycleCount

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

FaceCount

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

FlowPolynomial

(poly=Factor[Table[GraphData[{"King",{n,n}},"FlowPolynomial"],{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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

FractionalChromaticNumber

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

FractionalEdgeChromaticNumber

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

Girth

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

Gonality

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

HamiltonConnected

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

HamiltonDecompositionCount

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

Hamiltonian

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

HamiltonianCycleCount

A140519

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

FindLinearRecurrence[Rest@seq]//Head//Timing

FindGeneratingFunction[Rest@seq,x]//Head//Timing

HamiltonianNumber

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

FindSequenceFunction[seq,n]

HamiltonianPathCount

A308129

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

FindLinearRecurrence[Rest@seq]//Head//Timing

FindGeneratingFunction[Rest@seq,x]//Head//Timing

HamiltonianWalkCount

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

HararyIndex

A144945

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

FindSequenceFunction[seq,n]//Factor

FindGeneratingFunction[seq,x]

HexagonCount

A288920

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

FindLinearRecurrence[Drop[seq,2]]

LinearRecurrence[{3,-3,1},{82,430,1030},{-1,1}]

Join[{0,0},LinearRecurrence[{3,-3,1},{142,-14,82},{3,30}]]

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

Table[If[n<3,0,2 (275-267 n+63 (n^2))],{n,20}]

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

CoefficientList[Series[((2 (x^2) (-41-92 x+7 (x^2)))/(((-1+x))^3)),{x,0,20}],x]

IdiosyncraticPolynomial

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

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

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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

IndependenceNumber

A008794

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

Table[Ceiling[n/2]^2,{n,20}]==seq

FindSequenceFunction[seq,n]//FullSimplify

IndependencePolynomial

A193580

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

(poly=x^Range[0,Length[#]-1].#&/@Rest@(Split[data,#2≠1&]//.{x__,l_List,{1},y__}:>{x,Append[l,1],y}))//Column

CoefficientList[Take[poly,5],x]//Column

FindLinearRecurrence[poly]//Head//Timing

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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

IndependenceRatio

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

FindSequenceFunction[seq,n]//FullSimplify

Table[((Ceiling[n/2]^2)/(n^2)),{n,20}]

IndependentEdgeSetCount

A220638

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

FindLinearRecurrence[DeleteMissing@Drop[seq,2]]//Head//Timing

FindGeneratingFunction[DeleteMissing@Drop[seq,1],x]//Head//Timing

b[n_,l_]:=b[n,l]=Module[{d,f,k},d=Length[l]/2;f=False;Which[n==0,1,l[[1;;d]]==Array[f&,d],b[n-1,Join[l[[d+1;;2d]],Array[True&,d]]],True,For[k=1,!l[[k]],k++];b[n,ReplacePart[l,k->f]]+If[k<d&&n>1&&l[[k+d+1]],b[n,ReplacePart[l,k|k+d+1->f]],0]+If[k>1&&n>1&&l[[k+d-1]],b[n,ReplacePart[l,k|k+d-1->f]],0]+If[n>1&&l[[k+d]],b[n,ReplacePart[l,k|k+d->f]],0]+If[k<d&&l[[k+1]],b[n,ReplacePart[l,k|k+1->f]],0]]];a[n_]:=b[n,Array[True&,2n]]

a[15]

a[16]

Array[a,15]==Take[seq,15]//Timing

IndependentVertexSetCount

A063443(n-1)

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

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

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

Algorithm 1

(* Mark McClure (mcmcclur(AT)bulldog.unca.edu) Mar 19 2006 *)

step[sa[rules1_,{dim1_,dim1_}],sa[rules2_,{dim2_,dim2_}]]:=sa[Join[rules2,rules1/.{x_Integer,y_Integer}->{x+dim2,y},rules1/.{x_Integer,y_Integer}->{x,y+dim2}],{dim1+dim2,dim1+dim2}];
mat[0]=sa[{{1,1}->1},{1,1}];mat[1]=sa[{{1,1}->1,{1,2}->1,{2,1}->1},{2,2}];mat[n_]:=mat[n]=step[mat[n-2],mat[n-1]];A[n_]:=mat[n]/.sa->SparseArray;Table[MatrixPower[A[n],n+1][[1,1]],{n,010}]

Algorithm 2

(* Jean-François Alcover, Dec 11 2014, after Alois P.Heinz *)

Clear[a,b];b[n_,l_List]:=b[n,l]=Module[{m=Min[l],k},If[m>0,b[n-m,l-m],If[n==0,1,k=Position[l,0,1,1][[1,1]];b[n,ReplacePart[l,k->1]]+If[n>1&&k<Length[l]&&l[[k+1]]==0,b[n,ReplacePart[l,{k->2,k+1->2}]],0]]]];a[n_]:=a[n]=If[n<2,1,b[n,Table[0,{n}]]];

Array[a,15]

IntersectionNumber

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

KirchhoffIndex

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

FindSequenceFunction[DeleteMissing@Rest@seq,n-1]//Head//Timing

KirchhoffSumIndex

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

FindSequenceFunction[DeleteMissing@Rest@seq,n-1]//Head//Timing

LaplacianPolynomial

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

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

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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

LeafCount

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

LongestCycleCount

==|HC|

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

LovaszNumber

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

MatchingGeneratingPolynomial

A243424

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

CoefficientList[Take[poly,5],x]//Column

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

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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

MatchingNumber

A007590

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

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

FindSequenceFunction[seq,n]//FullSimplify

MatchingPolynomial

(poly=Table[GraphData[{"King",{n,n}},"MatchingPolynomial"],{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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

MaximalCliqueCount

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

FindSequenceFunction[Rest@seq,n-1]

MaximalIndependentEdgeSetCount

A297489

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

MaximalIndependentVertexSetCount

A288956

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

FindLinearRecurrence[seq]//Head//Timing

FindSequenceFunction[Rest@seq,n-1]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

MaximumCliqueCount

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

FindSequenceFunction[Rest@seq,n-1]

MaximumIndependentEdgeSetCount

A243510

seq=Table[GraphData[{"King",{n,n}},"MaximumIndependentEdgeSetCount"],{n,20}]

FindLinearRecurrence[seq]//Head//Timing

FindSequenceFunction[Rest@seq,n-1]//Head//Timing

FindGeneratingFunction[Rest@seq,x]//Head//Timing

MaximumIndependentVertexSetCount

Even terms are A018807(n/2)

seq=Table[GraphData[{"King",{n,n}},"MaximumIndependentVertexSetCount"],{n,20}]

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

{4,79,3600,281571,32572756}//Head//Timing

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

MaximumLeafNumber

seq=Table[GraphData[{"King",{n,n}},"MaximumLeafNumber"],{n,20}]

MaximumVertexDegree

seq=Table[GraphData[{"King",{n,n}},"MaximumVertexDegree"],{n,20}]

MeanCurvature

seq=Table[GraphData[{"King",{n,n}},"MeanCurvature"],{n,20}]

FindSequenceFunction[seq,n]

seq[[3;;;;2]]

seq[[4;;;;2]]

MeanDistance

seq=Table[GraphData[{"King",{n,n}},"MeanDistance"],{n,20}]

FindSequenceFunction[seq,n]//Factor

Meyniel

seq=Table[GraphData[{"King",{n,n}},"Meyniel"],{n,20}]

MinimalDominatingSetCount

A286881

seq=Table[GraphData[{"King",{n,n}},"MinimalDominatingSetCount"],{n,20}]

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

MinimalDominationPolynomial

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

MinimumCliqueCoveringCount

seq=Table[GraphData[{"King",{n,n}},"MinimumCliqueCoveringCount"],{n,20}]

Table[GraphData[{"King",{n,n}},"MinimumCliqueCoverings"],{n,4}]

GraphData[{"King",{3,3}},"Graph","Labeled"]

GraphData[{"King",{4,4}},"Graph","Labeled"]

MinimumConnectedDominatingSetCount

Probably 1 for odd n

seq=Table[GraphData[{"King",{n,n}},"MinimumConnectedDominatingSetCount"],{n,20}]

FindSequenceFunction[seq,n]

MinimumDistinguishingLabelingCount

seq=Table[GraphData[{"King",{n,n}},"MinimumDistinguishingLabelingCount"],{n,20}]

MinimumDominatingSetCount

Probably 1 for odd n

seq=Table[GraphData[{"King",{n,n}},"MinimumDominatingSetCount"],{n,20}]

MinimumEdgeCoverCount

seq=Table[GraphData[{"King",{n,n}},"MinimumEdgeCoverCount"],{n,20}]

MinimumVertexDegree

seq=Table[GraphData[{"King",{n,n}},"MinimumVertexDegree"],{n,20}]

MolecularTopologicalIndex

seq=Table[GraphData[{"King",{n,n}},"MolecularTopologicalIndex"],{n,20}]

FindSequenceFunction[seq,n]//Factor

Nonhamiltonian

Table[GraphData[{"King",{n,n}},"Nonhamiltonian"],{n,20}]

OddChordlessCycleCount

seq=Table[GraphData[{"King",{n,n}},"OddChordlessCycleCount"],{n,20}]

PathCount

A288033

seq=Table[GraphData[{"King",{n,n}},"PathCount"],{n,20}]

Head/@Table[FindLinearRecurrence[Drop[seq,k]],{k,0,3}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

PathPolynomial

(poly=Table[GraphData[{"King",{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]

PentagonCount

A288919

seq=Table[GraphData[{"King",{n,n}},"PentagonCount"],{n,20}]

FindLinearRecurrence[Drop[seq,2]]

LinearRecurrence[{3,-3,1},{52,176,372},{-1,1}]

Join[{0,0},LinearRecurrence[{3,-3,1},{20,0,52},{3,20}]]

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

Table[If[n==1,0,4(n-2)(9n-14)],{n,30}]

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

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

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

Perfect

Table[GraphData[{"King",{n,n}},"Perfect"],{n,20}]

Planar

Select[GraphData[{"King","Planar"}],Equal@@("King"/.GraphData[#,"NotationRules"])&]

ProjectivePlaneCrossingNumber

seq=Table[GraphData[{"King",{n,n}},"ProjectivePlaneCrossingNumber"],{n,20}]

Radius

seq=Table[GraphData[{"King",{n,n}},"Radius"],{n,20}]

Table[GraphRadius[KingGraph[n,n]],{n,40}]//Timing

RankPolynomial

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

RectilinearCrossingNumber

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

Regular

GraphData[{"King","Regular"}]

ReliabilityPolynomial

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

SigmaPolynomial

(poly=Factor[Table[GraphData[{"King",{n,n}},"SigmaPolynomial"],{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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

SpanningTreeCount

A288957

seq=Table[GraphData[{"King",{n,n}},"SpanningTreeCount"],{n,20}]

FindSequenceFunction[seq,n]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

SquareCount

A288918

seq=Table[GraphData[{"King",{n,n}},"SquareCount"],{n,20}]

(seq=Table[CycleCount[KingGraph[n,n],4],{n,40}])//Timing

FindLinearRecurrence[Rest@seq]

LinearRecurrence[{3,-3,1},{3,29,79},{0,1}]

Join[{0},LinearRecurrence[{3,-3,1},{1,3,29},{2,20}]]

FindSequenceFunction[Rest@seq,n-1]//Factor

Table[If[n==1,0,23-34 n+12 (n^2)],{n,20}]

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

FindGeneratingFunction[seq,x]

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

StabilityIndex

seq=Table[GraphData[{"King",{n,n}},"StabilityIndex"],{n,20}]

FindSequenceFunction[seq,n]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

TopologicalIndex

seq=Table[GraphData[{"King",{n,n}},"TopologicalIndex"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

ToroidalCrossingNumber

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

Traceable

Table[GraphData[{"King",{n,n}},"Traceable"],{n,20}]

TriangleCount

A016742(n+1)

seq=Table[GraphData[{"King",{n,n}},"TriangleCount"],{n,20}]

FindSequenceFunction[seq,n]

TuttePolynomial

(poly=Factor[Table[GraphData[{"King",{n,n}},"TuttePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x,y]])//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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Untraceable

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

VertexConnectivity

Table[GraphData[{"King",{n,n}},"VertexConnectivity"],{n,20}]

VertexCount

Table[GraphData[{"King",{n,n}},"VertexCount"],{n,20}]

VertexCoverNumber

vertex cover number == vertex count - independence number

seq=Table[GraphData[{"King",{n,n}},"VertexCoverNumber"],{n,20}]

FindSequenceFunction[seq,n]//FullSimplify

gf=x FindGeneratingFunction[seq,x]

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

VertexCoverPolynomial

(poly=Table[GraphData[{"King",{n,n}},"VertexCoverPolynomial"],{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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

VertexDegrees

Tally/@Table[GraphData[{"King",{n,n}},"VertexDegrees"],{n,20}]//Column

VertexTransitive

Table[GraphData[{"King",{n,n}},"VertexTransitive"],{n,20}]

WienerIndex

A292053

seq=Table[GraphData[{"King",{n,n}},"WienerIndex"],{n,20}]

FindLinearRecurrence[seq]

gf=x FindGeneratingFunction[seq,x]

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

Refine[SeriesCoefficient[gf,{x,0,n}],n>0]//Factor

seq=Table[(n-1) n (1+n) (7 (n^2)+2)/30,{n,40}]

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{6,-15,20,-15,6,-1},{0,6,52,228,708,1778},20]

WienerSumIndex

seq=Table[GraphData[{"King",{n,n}},"WienerSumIndex"],{n,20}]

FindSequenceFunction[Rest@DeleteMissing@seq,n]//Head//Timing

GraphData

GraphDataClassString

GraphDataClassString["King"]

GraphDataClassString[Intersection@@(GraphData[#,"Classes"]&/@GraphData["King",5;;])]

GraphDataString

<<MathWorld`Graphs`

file=OpenAppend["~/king.m"]

Do[
WriteString[file,
GraphDataString[KingGraph[n,n],
"StandardName"->{"King",{n,n}},
"Name"->"("<>ToString[n]<>","<>ToString[n]<>")\[Hyphen]king graph",
"NotationRules"->{"King"->{n,n}},
"Classes"->{"King"},
"Information"->"KingGraph",
"Skip"->{"Arboricity","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","EigenvectorCentralities","HamiltonianCycle","HITSCentralities","IdiosyncraticPolynomial","MatchingGeneratingPolynomial","MaximalIndependentVertexSets","MaximumIndependentEdgeSets","MaximumIndependentVertexSets","MinimumDistinguishingLabelings","MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover","MinimumVertexCut","SpanningTreeCount","TopologicalIndex","TuttePolynomial"},
TimeConstraint->1,
Debug->True
]],
{n,18,20}
]

Close[file]