Queen Graph

Author

Eric W. Weisstein
October 25, 2024

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

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

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

Graphics

Graphs.m (degenerate)

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

GraphData "Grid" (degenerate)

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

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

GraphData default

GraphicsRow[Table[GraphData[{"Queen",{n,n}}]/.g_System`Graph:>SetProperty[g,{VertexSize->If[n==1,.015,{"Scaled",.05}],System`VertexStyle->Red,System`EdgeStyle->Black}],{n,5}],Dividers->All,ImageSize->500]

Special cases

Cases[GraphData["TetrahedralGraph","StandardNames"],{"Queen",_}]

TextGrid[Sort[{GraphData[#,"NotationRules","Queen"],GraphData[#,"Name"]}&/@DeleteCases[GraphData["Queen"],{"Queen",_}]],Dividers->All]

Complements

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

Embedding types

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

Embeddings

<<MathWorld`Graphs`

{"Queen", {2, 2}} == "TetrahedralGraph"

Names

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

GraphData[{"Queen",{2,2}},"StandardNames"]

{"Queen", {2, 3}}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Queen",{2,3}}]]

Default embedding

GraphPlot[Graph[GraphData[{"Queen",{2,3}},"VertexList"],GraphData[{"Queen",{2,3}},"Edges"]]]

GraphPlot[Graph[GraphData[{"Queen",{2,3}},"VertexList"],GraphData[{"Queen",{2,3}},"Edges"]],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph@g

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData[{"Queen",{2,3}},"Graph","Degenerate"]//Column

GeneralizedPetersen

GraphData[{"Queen",{2,3}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

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

Bilateral

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

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

Circular

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

Circular construction

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

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

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

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"Queen",{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[{"Queen",{2,3}},"Planar"]

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

PlanarGraphEmbeddings

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

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

Length[plemb]

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

GraphPlot@RotateGraph[,-2Pi/3]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"Queen",{2,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,3}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"Queen",{2,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,3}},"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[{"Queen",{2,3}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

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

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

Circulant construction

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

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

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

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

RootGraph

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

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

RecognizeGraph[%]

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

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

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

3D default

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

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Queen", {2, 4}}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Queen",{2,4}}]]

Default embedding

GraphPlot@RotateGraph[Graph[Graph[GraphData[{"Queen",{2,4}},"VertexList"],GraphData[{"Queen",{2,4}},"Edges"]]],{2,7}]

g0=LabelGraph@GraphicsToGraph@

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

RecognizeGraph@g

GraphPlot@RotateGraph[Graph[Graph[Graph[GraphData[{"Queen",{2,4}},"VertexList"],GraphData[{"Queen",{2,4}},"Edges"]]],GraphLayout->"SpringEmbedding"],{8,2}]

g0=LabelGraph@GraphicsToGraph@

Mean[v[[{7,8},2]]]

v=Join[CirclePoints[6],{#/4,-((Sqrt[3])/4)}&/@{-1,1}][[{2,1,3,8,4,7,5,6}]];
g=Graph[Range@Length@v,EdgeList[g0],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

GraphPlot[Graph[GraphData[{"Queen",{2,4}},"VertexList"],GraphData[{"Queen",{2,4}},"Edges"]],GraphLayout->"SpringEmbedding"]

GraphPlot[Graph[GraphData[{"Queen",{2,4}},"VertexList"],GraphData[{"Queen",{2,4}},"Edges"]],GraphLayout->"HighDimensionalEmbedding"]

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

RecognizeGraph@g

Degenerate

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

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

GeneralizedPetersen

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

IGraph

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

Bilateral

GraphData[{"Queen",{2,4}},"Graph","Bilateral"]//StyleGraphs

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

Circular

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

Circular construction

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

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

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

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

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

ReverseSortBy[Tally[graphswithsymmetrygroups[[All,-1]]],Last]//Column

(bilaterallyrotatedgraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[symmetricgraphs=DeleteDuplicatesBy[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

GraphPlot@RotateGraph[,2Pi/3]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

Quit

MinimalLocalCrossing

GraphData[{"Queen",{2,4}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"Queen",{2,4}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,4}},"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[{"Queen",{2,4}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

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

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

Circulant construction

GraphData[{"Queen",{2,4}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Queen",{2,4}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Queen",{2,4}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

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

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

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

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

RootGraph

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

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

RecognizeGraph[%]

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

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

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

3D default

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

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Queen", {2, 5}}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

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

Default embedding

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

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

RecognizeGraph@g

g0=LabelGraph@

v=CirclePoints[{1,Pi/2},10][[{8,9,7,10,6,1,5,2,4,3}]];
g=Graph[Range@Length@v,EdgeList[g0],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Degenerate

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

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

GeneralizedPetersen

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

IGraph

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

Bilateral

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

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

Circular

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

Circular construction 10^4

GraphData[{"Queen",{2,10}},"Hamiltonian"]

GraphData[{"Queen",{2,10}},"LCF"]

GraphData[{"Queen",{2,10}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"Queen",{2,10}}],10^4][[All,All,1]]]//Timing

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

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

Tally[graphswithsymmetrygroups[[All,-1]]]

(bilaterallyrotatedgraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[symmetricgraphs=DeleteDuplicatesBy[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

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

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

MinimalCrossing

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

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

RectilinearCrossingCount/@%

MinimalCrossing construction

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

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

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

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

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

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

(g=MinimalCrossingGraph[GraphData[{"Queen",{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[{"Queen",{2,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

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

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

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"Queen",{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[{"Queen",{2,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

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

GraphData[{"Queen",{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[{"Queen",{2,5}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

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

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

Circulant construction

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

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

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

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

RootGraph

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

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

RecognizeGraph[%]

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

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

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

3D default

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

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Queen", {2, 6}}

Names

GraphData[{"Queen",{2,6}},"StandardName"]

GraphData[{"Queen",{2,6}},"StandardNames"]

Primary

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

All

GraphData[{"Queen",{2,6}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Queen",{2,6}}]]

Default embedding

GraphPlot[Graph[GraphData[{"Queen",{2,6}},"VertexList"],GraphData[{"Queen",{2,6}},"Edges"]],GraphLayout->"HighDimensionalEmbedding"]

g0=LabelGraph@GraphicsToGraph@

RectilinearCrossingCount@g0

v=Join[CirclePoints[1/2,4],CirclePoints[{1,Pi/4+Pi/12},4],CirclePoints[{1,Pi/4-Pi/12},4]][[{6,9,10,5,3,2,4,1,7,12,11,8}]];
g=Graph[Range@Length@v,EdgeList[g0],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

g0=LabelGraph@

p=InversePermutation@RotateLeft[Ordering@Mod[ArcTan@@@GraphEmbedding[g0],2Pi],-3]

v=CirclePoints[12][[p]];
g=Graph[Range@Length@v,EdgeList[g0],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Degenerate

GraphData[{"Queen",{2,6}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Queen",{2,6}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"Queen",{2,6}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Queen",{2,6}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Queen",{2,6}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"Queen",{2,6}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"Queen",{2,6}},"Hamiltonian"]

GraphData[{"Queen",{2,6}},"LCF"]

GraphData[{"Queen",{2,6}},"HamiltonianCycleCount"]

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

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

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

ReverseSortBy[Tally[graphswithsymmetrygroups[[All,-1]]],Last]//Column

(bilaterallyrotatedgraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[symmetricgraphs=DeleteDuplicatesBy[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"Queen",{2,6}},"Planar"]

GraphData[{"Queen",{2,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Queen",{2,6}},{"RCN","CN"}]

GraphData[{"Queen",{2,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"Queen",{2,6}},"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[{"Queen",{2,6}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,6}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"Queen",{2,6}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,6}},"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[{"Queen",{2,6}}],TimeConstraint->10])//AbsoluteTiming

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

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

Circulant

GraphData[{"Queen",{2,6}},"Circulant"]

GraphData[{"Queen",{2,6}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Queen",{2,6}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Queen",{2,6}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Queen",{2,6}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"Queen",{2,6}},"ComplementGraph","Name"]

Line graph

GraphData[{"Queen",{2,6}},"Line"]

LineGraphQ[GraphData[{"Queen",{2,6}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"Queen",{2,6}}]]

RecognizeGraph[%]

Halin

GraphData[{"Queen",{2,6}},"Halin"]

GraphData[{"Queen",{2,6}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Queen",{2,6}},"Rigid"]

GraphData[{"Queen",{2,6}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Queen",{2,6}},"Flexible"]

GraphData[{"Queen",{2,6}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Queen",{2,6}},"LCF"]

GraphData[{"Queen",{2,6}},"HamiltonianCycleCount"]

GraphData[{"Queen",{2,6}},"LCFSignature"]

GraphData[{"Queen",{2,6}},"LCFNotations"]

GraphData[{"Queen",{2,6}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Queen",{2,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Queen",{2,6}}],Debug->True]//Timing

GraphData[{"Queen",{2,6}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Queen",{2,6}},"Matchstick"]

GraphData[{"Queen",{2,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Queen",{2,6}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Queen",{2,6}},"Polyhedral"]

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

{"Queen", {2, 7}}

Names

GraphData[{"Queen",{2,7}},"StandardName"]

GraphData[{"Queen",{2,7}},"StandardNames"]

Primary

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

All

GraphData[{"Queen",{2,7}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Queen",{2,7}}]]

Default embedding

GraphPlot[Graph[GraphData[{"Queen",{2,7}},"VertexList"],GraphData[{"Queen",{2,7}},"Edges"]],GraphLayout->"HighDimensionalEmbedding"]

g0=LabelGraph@GraphicsToGraph@

v=Join[CirclePoints[12],{#/8,0}&/@{-1,1}][[{9,4,7,6,8,5,13,14,11,2,12,1,10,3}]];
g=Graph[Range@Length@v,EdgeList[g0],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

DegenerateGraphEmbeddingQ@g

g0=LabelGraph@

p=InversePermutation@RotateLeft[Ordering@Mod[ArcTan@@@GraphEmbedding[g0],2Pi],-4]

v=CirclePoints[{1,-Pi/2},14][[p]];
g=Graph[Range@Length@v,EdgeList[g0],VertexCoordinates->v,VertexLabels->Automatic]

Degenerate

GraphData[{"Queen",{2,7}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Queen",{2,7}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"Queen",{2,7}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Queen",{2,7}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Queen",{2,7}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"Queen",{2,7}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"Queen",{2,7}},"Hamiltonian"]

GraphData[{"Queen",{2,7}},"LCF"]

GraphData[{"Queen",{2,7}},"HamiltonianCycleCount"]

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

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"Queen",{2,7}}],#]&/@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[{"Queen",{2,7}},"Planar"]

GraphData[{"Queen",{2,7}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Queen",{2,7}},{"RCN","CN"}]

GraphData[{"Queen",{2,7}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"Queen",{2,7}},"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[{"Queen",{2,7}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,7}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"Queen",{2,7}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,7}},"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[{"Queen",{2,7}}],TimeConstraint->10])//AbsoluteTiming

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

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

Circulant

GraphData[{"Queen",{2,7}},"Circulant"]

GraphData[{"Queen",{2,7}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Queen",{2,7}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Queen",{2,7}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Queen",{2,7}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"Queen",{2,7}},"ComplementGraph","Name"]

Line graph

GraphData[{"Queen",{2,7}},"Line"]

LineGraphQ[GraphData[{"Queen",{2,7}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"Queen",{2,7}}]]

RecognizeGraph[%]

Halin

GraphData[{"Queen",{2,7}},"Halin"]

GraphData[{"Queen",{2,7}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Queen",{2,7}},"Rigid"]

GraphData[{"Queen",{2,7}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Queen",{2,7}},"Flexible"]

GraphData[{"Queen",{2,7}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Queen",{2,7}},"LCF"]

GraphData[{"Queen",{2,7}},"HamiltonianCycleCount"]

GraphData[{"Queen",{2,7}},"LCFSignature"]

GraphData[{"Queen",{2,7}},"LCFNotations"]

GraphData[{"Queen",{2,7}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Queen",{2,7}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Queen",{2,7}}],Debug->True]//Timing

GraphData[{"Queen",{2,7}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Queen",{2,7}},"Matchstick"]

GraphData[{"Queen",{2,7}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Queen",{2,7}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Queen",{2,7}},"Polyhedral"]

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

{"Queen", {2, 8}}

Names

GraphData[{"Queen",{2,8}},"StandardName"]

GraphData[{"Queen",{2,8}},"StandardNames"]

Primary

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

All

GraphData[{"Queen",{2,8}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Queen",{2,8}}]]

Default embedding

g0=LabelGraph@

p=InversePermutation@RotateLeft[Ordering[Mod[ArcTan@@@GraphEmbedding[g0],2Pi]],-4]

v=CirclePoints[16][[p]];
g=Graph[Range@Length@v,EdgeList[g0],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

GraphPlot[Graph[GraphData[{"Queen",{2,8}},"VertexList"],GraphData[{"Queen",{2,8}},"Edges"]],GraphLayout->"HighDimensionalEmbedding"]

g0=LabelGraph@GraphicsToGraph@

v=Join[CirclePoints[12],CirclePoints[1/6,4]][[{9,4,7,5,8,6,15,14,16,13,11,2,12,1,10,3}]];
g=Graph[Range@Length@v,EdgeList[g0],VertexCoordinates->v,VertexLabels->Automatic]

GraphSymmetryGroup@g

RecognizeGraph@g

BilateralGraphEmbeddingQ@g

DegenerateGraphEmbeddingQ@g

Degenerate

GraphData[{"Queen",{2,8}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Queen",{2,8}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"Queen",{2,8}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Queen",{2,8}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Queen",{2,8}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"Queen",{2,8}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"Queen",{2,8}},"Hamiltonian"]

GraphData[{"Queen",{2,8}},"LCF"]

GraphData[{"Queen",{2,8}},"HamiltonianCycleCount"]

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

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"Queen",{2,8}}],#]&/@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[{"Queen",{2,8}},"Planar"]

GraphData[{"Queen",{2,8}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Queen",{2,8}},{"RCN","CN"}]

GraphData[{"Queen",{2,8}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"Queen",{2,8}},"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[{"Queen",{2,8}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,8}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"Queen",{2,8}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,8}},"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[{"Queen",{2,8}}],TimeConstraint->10])//AbsoluteTiming

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

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

Circulant

GraphData[{"Queen",{2,8}},"Circulant"]

GraphData[{"Queen",{2,8}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Queen",{2,8}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Queen",{2,8}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Queen",{2,8}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"Queen",{2,8}},"ComplementGraph","Name"]

Line graph

GraphData[{"Queen",{2,8}},"Line"]

LineGraphQ[GraphData[{"Queen",{2,8}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"Queen",{2,8}}]]

RecognizeGraph[%]

Halin

GraphData[{"Queen",{2,8}},"Halin"]

GraphData[{"Queen",{2,8}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Queen",{2,8}},"Rigid"]

GraphData[{"Queen",{2,8}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Queen",{2,8}},"Flexible"]

GraphData[{"Queen",{2,8}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Queen",{2,8}},"LCF"]

GraphData[{"Queen",{2,8}},"HamiltonianCycleCount"]

GraphData[{"Queen",{2,8}},"LCFSignature"]

GraphData[{"Queen",{2,8}},"LCFNotations"]

GraphData[{"Queen",{2,8}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Queen",{2,8}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Queen",{2,8}}],Debug->True]//Timing

GraphData[{"Queen",{2,8}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Queen",{2,8}},"Matchstick"]

GraphData[{"Queen",{2,8}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Queen",{2,8}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Queen",{2,8}},"Polyhedral"]

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

{"Queen", {2, 9}}

Names

GraphData[{"Queen",{2,9}},"StandardName"]

GraphData[{"Queen",{2,9}},"StandardNames"]

Primary

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

All

GraphData[{"Queen",{2,9}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Queen",{2,9}}]]

Default embedding

GraphPlot[Graph[GraphData[{"Queen",{2,9}},"VertexList"],GraphData[{"Queen",{2,9}},"Edges"]],GraphLayout->"HighDimensionalEmbedding"]

g0=LabelGraph@

p=InversePermutation@RotateLeft[Ordering[Mod[ArcTan@@@GraphEmbedding[g0],2Pi]],-5]

v=CirclePoints[{1,-Pi/2},18][[p]];
g=Graph[Range@Length@v,EdgeList[g0],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Degenerate

GraphData[{"Queen",{2,9}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Queen",{2,9}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"Queen",{2,9}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Queen",{2,9}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Queen",{2,9}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"Queen",{2,9}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"Queen",{2,9}},"Hamiltonian"]

GraphData[{"Queen",{2,9}},"LCF"]

GraphData[{"Queen",{2,9}},"HamiltonianCycleCount"]

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

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"Queen",{2,9}}],#]&/@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[{"Queen",{2,9}},"Planar"]

GraphData[{"Queen",{2,9}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Queen",{2,9}},{"RCN","CN"}]

GraphData[{"Queen",{2,9}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"Queen",{2,9}},"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[{"Queen",{2,9}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,9}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"Queen",{2,9}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,9}},"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[{"Queen",{2,9}}],TimeConstraint->10])//AbsoluteTiming

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

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

Circulant

GraphData[{"Queen",{2,9}},"Circulant"]

GraphData[{"Queen",{2,9}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Queen",{2,9}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Queen",{2,9}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Queen",{2,9}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"Queen",{2,9}},"ComplementGraph","Name"]

Line graph

GraphData[{"Queen",{2,9}},"Line"]

LineGraphQ[GraphData[{"Queen",{2,9}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"Queen",{2,9}}]]

RecognizeGraph[%]

Halin

GraphData[{"Queen",{2,9}},"Halin"]

GraphData[{"Queen",{2,9}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Queen",{2,9}},"Rigid"]

GraphData[{"Queen",{2,9}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Queen",{2,9}},"Flexible"]

GraphData[{"Queen",{2,9}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Queen",{2,9}},"LCF"]

GraphData[{"Queen",{2,9}},"HamiltonianCycleCount"]

GraphData[{"Queen",{2,9}},"LCFSignature"]

GraphData[{"Queen",{2,9}},"LCFNotations"]

GraphData[{"Queen",{2,9}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Queen",{2,9}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Queen",{2,9}}],Debug->True]//Timing

GraphData[{"Queen",{2,9}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Queen",{2,9}},"Matchstick"]

GraphData[{"Queen",{2,9}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Queen",{2,9}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Queen",{2,9}},"Polyhedral"]

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

{"Queen", {2, 10}}

Names

GraphData[{"Queen",{2,10}},"StandardName"]

GraphData[{"Queen",{2,10}},"StandardNames"]

Primary

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

All

GraphData[{"Queen",{2,10}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Queen",{2,10}}]]

Default embedding

GraphPlot[Graph[GraphData[{"Queen",{2,10}},"VertexList"],GraphData[{"Queen",{2,10}},"Edges"]],GraphLayout->"HighDimensionalEmbedding"]

g0=LabelGraph@

p=InversePermutation@RotateLeft[Ordering[Mod[ArcTan@@@GraphEmbedding[g0],2Pi]],-5]

v=CirclePoints[20][[p]];
g=Graph[Range@Length@v,EdgeList[g0],VertexCoordinates->v,VertexLabels->Automatic]

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

RecognizeGraph@g

Degenerate

GraphData[{"Queen",{2,10}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Queen",{2,10}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"Queen",{2,10}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Queen",{2,10}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Queen",{2,10}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"Queen",{2,10}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"Queen",{2,10}},"Hamiltonian"]

GraphData[{"Queen",{2,10}},"LCF"]

GraphData[{"Queen",{2,10}},"HamiltonianCycleCount"]

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

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"Queen",{2,10}}],#]&/@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[{"Queen",{2,10}},"Planar"]

GraphData[{"Queen",{2,10}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Queen",{2,10}},{"RCN","CN"}]

GraphData[{"Queen",{2,10}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"Queen",{2,10}},"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[{"Queen",{2,10}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,10}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"Queen",{2,10}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"Queen",{2,10}},"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[{"Queen",{2,10}}],TimeConstraint->10])//AbsoluteTiming

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

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

Circulant

GraphData[{"Queen",{2,10}},"Circulant"]

GraphData[{"Queen",{2,10}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Queen",{2,10}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Queen",{2,10}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Queen",{2,10}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"Queen",{2,10}},"ComplementGraph","Name"]

Line graph

GraphData[{"Queen",{2,10}},"Line"]

LineGraphQ[GraphData[{"Queen",{2,10}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"Queen",{2,10}}]]

RecognizeGraph[%]

Halin

GraphData[{"Queen",{2,10}},"Halin"]

GraphData[{"Queen",{2,10}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Queen",{2,10}},"Rigid"]

GraphData[{"Queen",{2,10}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Queen",{2,10}},"Flexible"]

GraphData[{"Queen",{2,10}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Queen",{2,10}},"LCF"]

GraphData[{"Queen",{2,10}},"HamiltonianCycleCount"]

GraphData[{"Queen",{2,10}},"LCFSignature"]

GraphData[{"Queen",{2,10}},"LCFNotations"]

GraphData[{"Queen",{2,10}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Queen",{2,10}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Queen",{2,10}}],Debug->True]//Timing

GraphData[{"Queen",{2,10}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Queen",{2,10}},"Matchstick"]

GraphData[{"Queen",{2,10}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Queen",{2,10}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Queen",{2,10}},"Polyhedral"]

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

{"Queen", {4, 1}} == "TetrahedralGraph"

Names

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

GraphData[{"Queen",{4,1}},"StandardNames"]

Properties n×n

<<MathWorld`Graphs`

Acyclic

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

AdjacencyMatrixCount

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

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

AlgebraicConnectivity

seq=Table[GraphData[{"Queen",{n,n}},"AlgebraicConnectivity"],{n,20}]

Arboricity

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

ArcTransitive

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

ArcTransitivity

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

AutomorphismCount

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

BalabanIndex

seq=Table[GraphData[{"Queen",{n,n}},"BalabanIndex"],{n,20}]

Bandwidth

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

Block

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

BridgeCount

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

BurningNumber

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

CharacteristicPolynomial

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

Chordal

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

ChordCount

Inferred for n > 10:

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

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

Chordless

Inferred for n > 10:

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

ChordlessCycleCount

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

ChromaticallyUnique

seq=Table[GraphData[{"Queen",{n,n}},"ChromaticallyUnique"],{n,20}]

ChromaticInvariant

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

ChromaticNumber

A088202

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

Date: Thu, 11 Sep 2003 16:45:12 +0800
From: Gordon Royle <gordon@csse.uwa.edu.au>
To: EIS fans <seqfan@ext.jussieu.fr>
Subject: Queen's Graph

Vasek Chvatal raised the (old) question of considering the number of colours needed to colour the n x n "queen's graph" - the graph with vertex set equal to the cells on a chessboard, with two vertices adjacent if a queen can move from one to the other.

Clearly, as each row/column is an n-clique, this graph needs at least n colours.

And in fact, when n congruent to 1,5 mod 6 it can be shown that n colours suffices - denote this by (*).

For small values of n, we have

    n=3    5 colours
    n=4    5 colours
    n=5    5 colours (*)
    n=6    7 colours
    n=7    7 colours (*)
    n=8    9 colours
    n=9    10 colours
    n=10    11 colours
    n=11     11 colours (*)

But then Guenter Stertenbrink supplied a 12-colouring of the 12x12 queens graph

    n = 12    12 colours
    n = 13    13 colours (*)

Table[{n,GraphData[{"Queen",{n,n}},"ChromaticNumber"]},{n,2,10}]//TableForm

Class 1

seq=Table[GraphData[{"Queen",{n,n}},"Class1"],{n,20}]

GraphData["Class1","Missing"]

Queen graphs with m or n even are class 1:

even=Select[("Queen"/.GraphData[#,"NotationRules"])&/@GraphData["Queen"],Mod[#,2]!={1,1}&]

And@@(GraphData[{"Queen",#},"Class1"]&/@even)

What's left:

odd=Select[("Queen"/.GraphData[#,"NotationRules"])&/@GraphData["Queen"],Mod[#,2]=={1,1}&]

m,n odd with m≤n≤2m-1 are class 1 (Wagon, Dec. 9, 2015):

Select[odd,Function[{m,n},m≤n≤2m-1]@@#&]

And@@(GraphData[{"Queen",#},"Class1"]&/@%)

What's left:

Select[odd,!Function[{m,n},m≤n≤2m-1]@@#&]

Correspondence

-------- Original Message --------
Subject: more....
Date: Sun, 13 Nov 2011 08:30:24 -0600
From: Stan Wagon
To: Eric Weisstein

I posed the Queen problem to my prob of week e list and an answer just came in which I attach. I have read about half of it. 

From your list, the following I had settled as Class One.

{{"QueensTour", {2, 7}}, {"QueensTour", {2, 8}}, {"QueensTour", {2, 
   9}}, {"QueensTour", {2, 10}}, {"QueensTour", {3, 3}}, {"QueensTour", {3, 
   4}}, {"QueensTour", {3, 5}}, {"QueensTour", {3, 6}}, {"QueensTour", {3, 
   7}}, {"QueensTour", {3, 8}}, {"QueensTour", {4, 4}}, {"QueensTour", {4, 
   5}}, {"QueensTour", {4, 6}}, {"QueensTour", {4, 7}}, {"QueensTour", {4, 
   8}}, {"QueensTour", {4, 9}}, {"QueensTour", {4, 10}}, {"QueensTour", {5, 
   5}}, {"QueensTour", {5, 6}}, {"QueensTour", {5, 7}}, {"QueensTour", {5, 
   8}}, {"QueensTour", {5, 10}}, {"QueensTour", {6, 6}}, {"QueensTour", {6, 
   7}}, {"QueensTour", {6, 8}}, {"QueensTour", {6, 9}}, {"QueensTour", {6, 
   10}}, {"QueensTour", {7, 7}}, {"QueensTour", {7, 8}}, {"QueensTour", {7, 
   9}}, {"QueensTour", {8, 8}}, {"QueensTour", {8, 9}}, {"QueensTour", {8, 
   10}}, {"QueensTour", {9, 9}}, {"QueensTour", {9, 10}}, {"QueensTour", {10, 
   10}}}

The following you had done:

{{"QueensTour", {2, 3}}, {"QueensTour", {2, 4}}, {"QueensTour", {2, 5}}, {"QueensTour", {2, 6}}}

So that left: 

{"QueensTour", {3, 9}}, {"QueensTour", {3, 10}}, {"QueensTour", {5, 9}}, {"QueensTour", {7, 10}}}

The email attach claims that those are class 1 except for ODD x ODD square, leaving

{"QueensTour", {3, 9}}, {"QueensTour", {5, 9}}, 

unsettled.

Also here is a formula for the max degree in those cases where one of m n is > 1.

For Queen  m xn  where m <= n max degree is

  3 m + n - 5 if m = n and n is even
  3 m + n - 4 otherwise

[[And just in from Witold Jarnicki of google poland: a claim for the even x even case....!!! ]]

You should credit Joe DeVincentis if you can....

And we should read his proof...

Joseph DeVincentis <devjoe@gmail.com>
For the king graph, each interior square shows that at least 8 colors are required, since 8 edges meet at that square's vertex. But 8 are sufficient; assign two colors to the vertical edges, two to the horizontal, to the SW-NE diagonal, and two to the SE-NW diagonal. Along each line, assign the two colors for that line to alternate edges (indeed, you are forced to do so). This ensures that no two connected edges along that line have the same color, and since all the other edges of these colors are parallel, they never meet the ones on this line.

For the queen graph, this strategy of making the edges in each direction use a different set of colors fails for most boards, but it can be adapted for most cases to have some colors used in multiple directions in such a way that they do not hit the same vertices. I still lack a strategy for odd x odd boards in the minimum number of colors.

First off, note that the portion of the graph lying along any one line is the complete graph on the n vertices on that line, and when n is odd, n colors (not the n-1 which is the contribution of that line to the maximum order) are needed to color that complete graph. It's OK when n is even, because in that case the complete graph can be colored with n-1 colors; Wikipedia provides a construction from Soifer (2008). For odd n, the same construction without the center point applies; each vertex lacks a different one of the colors.

When m and n are different and both even, using m-1 colors in each diagonal and one orthogonal direction and n-1 colors in the other direction provides a solution.

On the square even board, as noted in the problem statement, the maximum order is one less than on other boards because there is no one square on both maximum length diagonals. On this board, use colors 1 through n-1 for the diagonals in one direction and n-1 through 2n-3 for the diagonals in the other direction. Choose the coloring for the n-1 square diagonals so that the square intersecting the opposite n square diagonal does not use color n-1 in the n-1 square direction. On all the shorter diagonals of n-2 squares or fewer, n-2 colors or fewer are needed, and for these do not use color n-1. In this way there are no conflicts between the colors used by the diagonals. In this way a total of 2n-3 colors are used for the diagonals and 2n-2 for the orthogonal directions for a total of 4n-5.

For m even, n odd boards, there is no problem on the diagonals. The longest diagonals are m units long, and they use m-1 different colors each. In the orthogonal directions, we use only m+n-2 colors by this color-sharing strategy: In the odd direction, colors 1 to n are used, the same way in each line, so that all the squares in each crossing line lack the same color. Then this color along with colors n+1 to m+n-2 are the m-1 colors used in that even-length crossing line.

For m odd, n even boards, there is a more involved sharing strategy. The odd orthogonal lines and the long diagonals all use m colors. As I described before, there is one color not used at each vertex. Choose colors on each of these lines so that the unused colors form stripes in the even direction. So the three sets of odd lines might use colors 1 to m, m+1 to 2m, and 2m+1 to 3m, with colors 1, m+1, and 2m+1 all unused in even row 1, colors 2, m+2, and 2m+2 all unused in even row 2, and so forth. Then each even row uses colors k, m+k, 2m+k and 3m+1 to 3m+n-4 for a total of 3+n-4 = n-1 colors, the number needed for an even row of length n. On the 3 x 4 board, the smallest nontrivial board of this type, the even rows use no colors of their own, just the 3 shared ones.

For odd x odd boards, I don't have a strategy that works. The best I can do is to reuse the m odd, n even strategy, with one orthogonal direction being designated the one that uses 3 colors shared with the lines in the other directions, but this uses one more color than the minimum. I have a 3x3 solution in 8 colors, so I know at least this case can be done in the minimum you conjecture, but I don't have a general strategy. I'll update you if I figure something out.

-------- Original Message --------
Subject: queen graph
Date: Mon, 14 Nov 2011 14:11:18 -0600
From: Stan Wagon
To: Eric Weisstein

I don't know if you would ever intend to include QueenGraph in its general form -- all n,m. I needed it this weekend so programmed it as follows.

So now that the dust is settled, we have these things in class 1 except for the cases (m,n) with m<n and both odd. In those case we know:

A. several small cases are class 1. All the GraphData cases also (3,11) and (5,11) by ILP.

B. f n>=1/3 (2 m3-11 m+18) then it is class 2. So (3, 11 or 12 0r....)   (5, 71 or 73 or ...)   Proof of this is just easy counting of edges given the max possibility for a matching.

C. the remaining odd/odd cases we don't know. So for squares, say, that means  11x11 13x13, etc are open.


I used the code below to create the 3,11 and 5,11 objects that I then fed to ILP.


neighbors[{m_, n_} , 
  k_] := (verts = Flatten[ Table[{i, j}, {i, m}, {j, n}], 1];
  p = {Quotient[k - 1, n] + 1, Mod[k, n, 1]};
  ss = Select[
    verts, # != 
       p && (#[[1]] == p[[1]] || #[[2]] == 
         p[[2]] || (#[[2]] - p[[2]]) == #[[1]] - 
          p[[1]] || (#[[2]] - p[[2]]) == p[[1]] - #[[1]]) &];
  Flatten[ss /. {i_Integer, j_} :> Position[verts, {i, j}, 1, 1][[1]]])

QueenEdges[{m_, n_} , i_] := 
 Table[UndirectedEdge[i, ss], {ss, Select[neighbors[{m, n}, i], # > i &]}]

QueenEdges[{m_, n_} ] := Flatten[Table[QueenEdges[{m, n}, j], {j, m n}]]

QueenGraph[{m_, n_}] := 
  Graph[ Range[m n], QueenEdges[{m, n}], 
   VertexCoordinates -> 
    Thread[Range[m n] -> Flatten[ Table[{i, j}, {i, m}, {j, n}], 1]]];

GraphPlot[QueenGraph[{3, 5}], VertexLabeling -> True]

-------- Original Message --------
Subject: Queen(3,9) is class 1
Date: Fri, 18 Nov 2011 16:44:13 -0600
From: Stan Wagon <wagon@macalester.edu>
To: Witold Jarnicki <witoldj@gmail.com>, Eric Weisstein <eww@wolfram.com>
CC: Joseph DeVincentis <devjoe@gmail.com>

So, the question is: what algorithm Sage is using....

I guess there are two possibilities:

1. They are using some general edge-coloring algorithm from the literature.  I think there are edge-coloring algorithms that are more specific than general vertex-coloring algorithms.
2. They are just doing some simple backtracking which we could have programmed in Mathematica....

Since I was into the ILP method I hadn't thought about backtracking. The graph is not all that large.... but not all that small...  so I can't guess if backtracking would work or not.
But the Mathematica package Combinatorica I believe has backtracking included, but I think Eric W. would have tried that....  

Eric: This concerns the QueenGraph[{3,9}] which I have been working very hard without success. As you see below, Witold has shown it is class 1 using SAGE. 

Witold: Can you dig and find out what algorithm Sage is using here? I would imagine they are not very secretive about these things.

Witold: And I see the actual coloring is provided so we could (should?) check it to see if it is correct.

Witold: So this settles everything in Queen (3,n) for all n as (3, >= 13) is class 2  and I did (3,11), though maybe you should try that in Sage too as a check. Anyway, getting all (3,n) for all n is satisfying. Is any of this stuff publishable? This might be because of your and Joe's work on those specific colorings for the other cases.




On Nov 18, 2011, at 3:42 PM, Witold Jarnicki wrote:

> 
> 
> On Thu, Nov 17, 2011 at 3:26 PM, Stan Wagon <wagon@macalester.edu> wrote:
> Will fix. Thanks.
> 
> Back to Queen 3,9    My ILP overnight failed, even though I had succeeded on larger ones like 3,11 and 5,11 in an hour or less.
> 
> So since so far the ILP worked when there were colorings to be found, it makes me wonder if possibly Q(3,9) is class 2.  How would one prove that?
> Q(3,9) is class 1.
> 
> I found a nice software package called Sage. It computed the coloring in less than a minute. Here's a session transcript containing the solution and the sequence of commands I used (in case you want to give it a try yourself).
> 
> sage: from sage.graphs.graph_coloring import edge_coloring; g=Graph(); X=3; Y=9
> sage: for x in range(X):
>     for y in range(Y):
>         for xx in range(x):
>             g.add_edge((xx,y),(x,y))
>         for yy in range(y):
>             g.add_edge((x,yy),(x,y))
>         for d in range(min(x,y)):
>             g.add_edge((x-d-1,y-d-1),(x,y))
>         for d in range(min(x,Y-y-1)):
>             g.add_edge((x-d-1,y+d+1),(x,y))
> ....:                     
> sage: %time c=edge_coloring(g)
> CPU times: user 54.95 s, sys: 1.15 s, total: 56.10 s
> Wall time: 59.89 s
> sage: len(c)
> 14
> sage: c
> [[((1, 3), (1, 7)), ((0, 0), (0, 6)), ((0, 3), (1, 2)), ((0, 4), (2, 6)), ((1, 1), (1, 6)), ((0, 1), (0, 7)), ((1, 4), (2, 5)), ((1, 0), (1, 5)), ((0, 8), (1, 8)), ((0, 2), (2, 2)), ((0, 5), (2, 3)), ((2, 4), (2, 7))], [((1, 3), (2, 4)), ((0, 7), (1, 6)), ((0, 0), (2, 0)), ((0, 3), (2, 1)), ((2, 5), (2, 7)), ((1, 2), (1, 5)), ((0, 4), (1, 4)), ((0, 1), (0, 8)), ((2, 6), (2, 8)), ((2, 2), (2, 3)), ((1, 0), (1, 7)), ((0, 2), (1, 1)), ((0, 5), (0, 6))], [((1, 3), (2, 3)), ((0, 0), (0, 3)), ((1, 2), (1, 6)), ((1, 5), (2, 5)), ((1, 1), (1, 4)), ((0, 1), (0, 6)), ((2, 2), (2, 4)), ((2, 1), (2, 6)), ((0, 8), (1, 7)), ((0, 2), (0, 4)), ((2, 0), (2, 8)), ((1, 8), (2, 7)), ((0, 5), (0, 7))], [((1, 3), (1, 5)), ((0, 0), (0, 4)), ((1, 6), (2, 6)), ((0, 3), (0, 7)), ((1, 2), (2, 2)), ((1, 1), (1, 7)), ((0, 1), (2, 1)), ((2, 3), (2, 5)), ((1, 0), (1, 8)), ((2, 7), (2, 8)), ((0, 2), (0, 6)), ((2, 0), (2, 4)), ((0, 5), (1, 4))], [((1, 3), (1, 4)), ((0, 0), (0, 1)), ((1, 6), (1, 7)), ((0, 3), (0, 6)), ((2, 5), (2, 6)), ((1, 5), (1, 8)), ((0, 4), (0, 8)), ((1, 1), (1, 2)), ((2, 3), (2, 7)), ((2, 1), (2, 2)), ((1, 0), (2, 0)), ((0, 2), (0, 5)), ((2, 4), (2, 8))], [((1, 6), (2, 7)), ((0, 3), (1, 3)), ((0, 6), (0, 8)), ((1, 5), (1, 7)), ((0, 4), (2, 2)), ((0, 1), (1, 1)), ((1, 4), (2, 3)), ((1, 0), (1, 2)), ((0, 2), (0, 7)), ((2, 0), (2, 1)), ((1, 8), (2, 8)), ((0, 5), (2, 5)), ((2, 4), (2, 6))], [((1, 3), (1, 8)), ((0, 0), (0, 7)), ((1, 2), (1, 4)), ((1, 5), (1, 6)), ((0, 4), (0, 6)), ((0, 1), (2, 3)), ((2, 2), (2, 5)), ((2, 1), (2, 4)), ((1, 0), (1, 1)), ((0, 8), (2, 6)), ((0, 2), (0, 3)), ((1, 7), (2, 8)), ((0, 5), (2, 7))], [((0, 0), (0, 2)), ((0, 3), (0, 5)), ((1, 2), (1, 8)), ((0, 6), (1, 6)), ((0, 4), (0, 7)), ((1, 1), (2, 0)), ((2, 2), (2, 6)), ((1, 4), (1, 5)), ((2, 1), (2, 3)), ((1, 0), (1, 3)), ((0, 8), (2, 8)), ((1, 7), (2, 7)), ((2, 4), (2, 5))], [((0, 7), (1, 8)), ((0, 0), (1, 0)), ((0, 3), (0, 8)), ((1, 2), (1, 7)), ((0, 6), (1, 5)), ((1, 1), (1, 3)), ((0, 1), (0, 4)), ((2, 2), (2, 8)), ((1, 4), (2, 4)), ((2, 3), (2, 6)), ((2, 1), (2, 5)), ((0, 2), (2, 0)), ((0, 5), (1, 6))], [((0, 7), (0, 8)), ((0, 0), (2, 2)), ((0, 3), (2, 5)), ((1, 2), (2, 3)), ((0, 6), (2, 6)), ((0, 4), (1, 3)), ((1, 1), (1, 5)), ((0, 1), (0, 5)), ((1, 4), (1, 6)), ((1, 0), (2, 1)), ((0, 2), (2, 4)), ((2, 0), (2, 7)), ((1, 7), (1, 8))], [((0, 0), (1, 1)), ((1, 6), (1, 8)), ((0, 3), (0, 4)), ((2, 5), (2, 8)), ((1, 2), (1, 3)), ((0, 6), (0, 7)), ((1, 5), (2, 6)), ((0, 1), (0, 2)), ((1, 4), (1, 7)), ((2, 3), (2, 4)), ((2, 1), (2, 7)), ((2, 0), (2, 2)), ((0, 5), (0, 8))], [((1, 3), (1, 6)), ((0, 7), (2, 5)), ((0, 0), (0, 8)), ((0, 3), (1, 4)), ((0, 6), (2, 8)), ((0, 4), (2, 4)), ((1, 1), (2, 1)), ((0, 1), (1, 0)), ((2, 2), (2, 7)), ((0, 2), (1, 2)), ((2, 0), (2, 3)), ((1, 7), (2, 6)), ((0, 5), (1, 5))], [((1, 3), (2, 2)), ((0, 7), (2, 7)), ((1, 6), (2, 5)), ((1, 2), (2, 1)), ((0, 6), (1, 7)), ((1, 5), (2, 4)), ((0, 4), (0, 5)), ((1, 1), (1, 8)), ((0, 1), (0, 3)), ((2, 3), (2, 8)), ((1, 0), (1, 4)), ((0, 2), (0, 8)), ((2, 0), (2, 6))], [((0, 7), (1, 7)), ((0, 0), (0, 5)), ((0, 3), (2, 3)), ((0, 6), (2, 4)), ((0, 4), (1, 5)), ((1, 1), (2, 2)), ((0, 1), (1, 2)), ((2, 6), (2, 7)), ((1, 4), (1, 8)), ((2, 1), (2, 8)), ((1, 0), (1, 6)), ((0, 2), (1, 3)), ((2, 0), (2, 5))]]
> sage: 
> 
> 
> First

-------- Original Message --------
Subject: new ideas
Date: Fri, 18 Nov 2011 22:04:05 -0600
From: Stan Wagon <wagon@macalester.edu>
To: Eric Weisstein <eww@wolfram.com>

I now have a much better EdgeColoring   ILP setup. While Queen (3,9) defeated me overnight, I can now solve it using this new ILP in 70 seconds. I was not going to let SAGE beat me!

I will now try some more of the missing ones in version 8 with this new code...  and I will send you the code too.  Here it is.

Results:

{"Square", 7}   is CLASS TWO   (89 seconds)  AND I JUST REALIZED that this is a breakthrough -- maybe the first instance of using ILP to prove no coloring exists. All my other results here used Blossom etc.

Oh, I see that Queen (7,10)   was still in my list of unknowns, but that is an odd/even case, and so is class one by the direct construction I sent you.

Class 2

Odd graphs with n\geq (2m^3-11m+18)/3 are trivially class 2:

Select[odd,Function[{m,n},n>=(2m^3-11m+18)/3]@@#&]

And@@(GraphData[{"Queen",#},"Classs"]&/@%)

Examples of class 2 graphs:

Select[{{3,13},{3,15},{5,71},{5,73},{7,209}},Function[{m,n},n>=(2m^3-11m+18)/3]@@#&]

General results are not known for these:

Select[odd,Function[{m,n},2m-1<n<(2m^3-11m+18)/3]@@#&]

ChromaticPolynomial

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

CircuitRank

seq=Table[GraphData[{"Queen",{n,n}},"CircuitRank"],{n,20}]

FindSequenceFunction[seq,n]//Factor

Circumference

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

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

Classes

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

ClawFree

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

CliqueCount

A295903

Inferred for n > 16:

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

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

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

CliqueCoveringNumber

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

CliqueNumber

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

CliquePolynomial

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

Simplify[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[{"Queen",{n,n}},"CochromaticGraphNames"],{n,20}]//Column

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

ComplementOddChordlessCycleCount

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

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

ConnectedComponentCount

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

ConnectedDominatingSetCount

A289185

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

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

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

ConnectedDominationNumber

Cf. A358062

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

FindSequenceFunction[seq,n]

ConnectedDominationPolynomial

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

ConnectedInducedSubgraphCount

A285765

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

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

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

ConnectedInducedSubgraphPolynomial

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

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

FullSimplify[poly2-poly]

CrossingNumber

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

CycleCount

A234626

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

FindSequenceFunction[DeleteMissing[seq],n]

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

CyclePolynomial

(poly=Factor[Table[GraphData[{"Queen",{n,n}},"CyclePolynomial"],{n,k0=1,kmax=10}]/.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]

Cyclic

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

DetourIndex

Inferred for n > 10:

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

FindSequenceFunction[DeleteMissing@seq,n]//Factor

DetourPolynomial

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

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

99^2

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

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]

Diameter

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

Disconnected

seq=Table[GraphData[{"Queen",{n,n}},"Disconnected"],{n,20}]

DistanceHereditary

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

DistancePolynomial

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

DistinguishingNumber

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

DomaticNumber

A292192

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

Table[Floor[Divide@@GraphData[{"Queen",{n,n}},{"VertexCount","DominationNumber"}]],{n,7}]

DominatingSetCount

A287070

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

FindLinearRecurrence[DeleteMissing[seq]]

FindSequenceFunction[DeleteMissing[seq],n]

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

DominationPolynomial

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

EdgeChromaticNumber

Inferred for n > 19:

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

EdgeConnectivity

seq=Table[GraphData[{"Queen",{n,n}},"EdgeConnectivity"],{n,20}]

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

EdgeCount

A144945

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

FindSequenceFunction[DeleteMissing[seq],n]//Factor

EdgeCoverCount

A297058

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

EdgeCoverNumber

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

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

EdgeCoverPolynomial

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

FaceCount

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

FlowPolynomial

(poly=Table[GraphData[{"Queen",{n,n}},"FlowPolynomial"],{n,k0=1,kmax=20}]/.f_Function:>Factor@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[{"Queen",{n,n}},"FractionalChromaticNumber"],{n,20}]

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

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

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

ewwmaclap (M1 ARM):

Do[Print[{{"Queen",{n,n}},FractionalChromaticNumber[QueenGraph[n,n]]//Timing}],{n,8}]

byblis66:

Do[Print[{{"Queen",{n,n}},FractionalChromaticNumber[QueenGraph[n,n],Method->"Dynamic"]//Timing}],{n,10}]

Do[Print[{{"Queen",{n,n}},FractionalChromaticNumber[QueenGraph[n,n],Method->"Static"]//Timing}],{n,10}]

FractionalEdgeChromaticNumber

Inferred for n > 19:

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

Girth

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

Gonality

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

HamiltonConnected

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

HamiltonDecompositionCount

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

Hamiltonian

Table[GraphData[{"Queen",{n,n}},"Hamiltonian"],{n,20}]

HamiltonianCycleCount

A307928

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

2DeleteMissing[seq]

HamiltonianNumber

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

FindSequenceFunction[seq,n]

HamiltonianPathCount

A308139

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

2DeleteMissing[seq]

HamiltonianWalkCount

A307928 == HamiltonianCycleCount

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

HararyIndex

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

FindSequenceFunction[seq,n]//Factor

HexagonCount

A288917

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

(seq=Table[CycleCount[QueenGraph[n,n],6],{n,60}])//Timing

coef=FindLinearRecurrence[seq]

"a(n)="<>StringReplace[StringJoin@@Table[If[coef[[k]]==0,"",Switch[
coef[[k]],
-1,"-",
1,"+",
_,ToString[coef[[k]]]<>"*"]<>"a(n-"<>ToString[k]<>")+"],{k,Length[coef]}],"+-"->"-"]

coef={0,3,2,-1,-5,-6,-1,6,11,6,-4,-10,-10,-4,6,11,6,-1,-6,-5,-1,2,3,0,-1}

Length[coef]

Take[seq,Length[coef]]

seq=LinearRecurrence[{0,3,2,-1,-5,-6,-1,6,11,6,-4,-10,-10,-4,6,11,6,-1,-6,-5,-1,2,3,0,-1},{0,0,976,26414,207136,951750,3190304,8721576,20615340,43736788,85332868,155691014,268995384,444000894,705336724,1083967932,1619250600,2358809948,3361809572,4697700286,6451359236,8719953330,11620829368,15285494276,19871396864},200]

FindSequenceFunction[seq,n]

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

RSolve[Join[{a[n]==Sum[a[n-k]coef[[k]],{k,Length[coef]}]},Table[a[k]==seq[[k]],{k,Length[coef]}]],a[n],n]

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

IdiosyncraticPolynomial

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

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

gf=x FindGeneratingFunction[seq,x]

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

IndependencePolynomial

A348129

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

Do[Print[{k,FindLinearRecurrence[DeleteMissing@Drop[poly,k]]//Head//Timing}],{k,0,3}]

Do[Print[{{"Queen",{n,n}},IndependencePolynomial[QueenGraph[n,n],x]//Timing}],{n,20}]

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[{"Queen",{n,n}},"IndependenceRatio"],{n,20}]

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

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

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

IndependentEdgeSetCount

A287226

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

FindLinearRecurrence[DeleteMissing[seq]]

FindSequenceFunction[DeleteMissing[seq],n]

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

IndependentVertexSetCount

A287227

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

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

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

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

Table[IndependencePolynomial[QueenGraph[n,n],1],{n,8}]//Timing

Do[Print[{{"Queen",{n,n}},IndependencePolynomial[QueenGraph[n,n],x]//Timing}],{n,20}]

IntersectionNumber

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

IrredundantSetCount

A290711

Table[GraphData[{"Queen",{n,n}},"IrredundantSetCount"],{n,20}]

KirchhoffIndex

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

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

KirchhoffSumIndex

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

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

LaplacianPolynomial

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

LeafCount

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

LongestCycleCount

Same as |HC|

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

LovaszNumber

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

MatchingGeneratingPolynomial

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

CoefficientList[Take[poly,5],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]

MatchingNumber

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

FindSequenceFunction[seq,n]//FullSimplify

MatchingPolynomial

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

MaximalCliqueCount

A288947

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

(seq=Table[Length@FindClique[QueenGraph[n,n],Infinity,All],{n,20}])//Timing

FindLinearRecurrence[Drop[seq,2]]

FindLinearRecurrence[Drop[seq,3]]

LinearRecurrence[{2,1,-4,1,2,-1},{10,36,76,129,210,310},{-1,1}]

Join[{1,1},LinearRecurrence[{2,1,-4,1,2,-1},{-28,-9,10,36,76,129},{3,40}]]

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]

gf=x FindGeneratingFunction[seq,x]//Factor

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

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

Table[Piecewise[{{1,n<3},{10,n==3}},n (73-3 (((-1))^n)+4 n (2n-3))/12-14],{n,20}]

MaximalIndependentEdgeSetCount

A297483

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

MaximalIndependentVertexSetCount

A146303

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

(seq=Table[Length@FindAllMaximalIndependentVertexSets[QueenGraph[n,n]],{n,20}])//Timing

Do[Print[{k,FindLinearRecurrence[DeleteMissing[Drop[seq,k]]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindSequenceFunction[DeleteMissing[Drop[seq,k]],n-k]//Head//Timing}],{k,0,3}]

MaximumCliqueCount

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

gf=x FindGeneratingFunction[seq,x]

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

MaximumIndependentEdgeSetCount

A288948

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

Do[Print[{k,FindLinearRecurrence[DeleteMissing[Drop[seq,k]]]//Head//Timing}],{k,0,3}]

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

Do[Print[{k,FindSequenceFunction[DeleteMissing[Drop[seq,k]],n-k]//Head//Timing}],{k,0,3}]

MaximumIndependentVertexSetCount

A000170(n) for n > 3

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

Do[Print[{k,FindLinearRecurrence[DeleteMissing[Drop[seq,k]]]//Head//Timing}],{k,0,4}]

Do[Print[{k,FindSequenceFunction[DeleteMissing[Drop[seq,k]],n-k]//Head//Timing}],{k,0,4}]

MaximumLeafNumber

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

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

MaximumVertexDegree

A047470

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

FindLinearRecurrence[seq]

LinearRecurrence[{1,1,-1},{0,3,8},20]

FindSequenceFunction[seq,n]//FullSimplify

Table[(8n-9-(((-1))^n))/2,{n,20}]

gf=x FindGeneratingFunction[seq,x]//Factor

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

MeanCurvature

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

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

MeanDistance

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

FindSequenceFunction[seq,n]//Factor

Meyniel

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

MinimalDominatingSetCount

A286883

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

MinimalDominationPolynomial

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

MinimumConnectedDominatingSetCount

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

FindSequenceFunction[seq,n]

MinimumCoveringsByMaximalCliquesCount

seq=Table[GraphData[{"Queen",{n,n}},"MinimumCoveringsByMaximalCliquesCount"],{n,20}]

MinimumDistinguishingLabelingCount

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

MinimumDominatingSetCount

A002564

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

MinimumEdgeCoverCount

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

MinimumVertexColoring

https://oeis.org/A088202/a088202.pdf

n×n queen graph is n-colourable whenever n mod 6 is 1 or 5.
The proof is easy: When the chessboard is thought of as the Cartesian square of {0,1,...,n-1}, colour vertex (i,j) by (j-2i) mod n. This construction is illustrated below on n=5 and on n=7.

g=GraphData[{"Queen",{11,11}},"Graph","Labeled"]

Select[Range[11,20],MatchQ[Mod[#,6],1|5]&]

MinimumVertexColoring[{"Queen",{n_Integer?Positive,n_}}]:=Module[{i,j},
Flatten[1+Table[Mod[j-2i,n],{i,0,n-1},{j,0,n-1}],1]
]/;MatchQ[Mod[n,6],1|5]

MinimumVertexColoring[{"Queen",{12,12}}]:=1+{0,5,9,6,3,8,4,1,10,11,7,2,7,11,4,2,1,6,10,3,0,8,9,5,8,1,10,9,5,2,0,7,11,6,3,4,10,0,3,8,7,11,9,5,4,1,2,6,5,6,11,4,2,1,3,0,8,9,10,7,11,7,0,1,10,4,8,6,3,2,5,9,2,8,6,3,9,5,7,11,1,10,4,0,3,4,5,0,11,10,6,9,2,7,8,1,9,2,1,10,4,7,5,8,6,3,0,11,4,10,7,11,0,3,1,2,9,5,6,8,6,3,2,5,8,9,11,4,7,0,1,10,1,9,8,7,6,0,2,10,5,4,11,3}

MinimumVertexColoring[{"Queen",{14,14}}]:=1+{1,9,11,7,5,13,3,2,12,4,6,10,8,0,7,12,4,8,3,0,11,10,1,2,9,5,13,6,6,3,13,10,1,4,8,9,5,0,11,12,2,7,5,10,1,9,13,2,6,7,3,12,8,0,11,4,4,0,2,6,11,12,9,8,13,10,7,3,1,5,2,8,7,13,0,10,5,4,11,1,12,6,9,3,12,1,5,3,8,11,7,6,10,9,2,4,0,13,0,6,10,12,2,9,4,5,8,3,13,11,7,1,9,11,3,4,6,1,12,13,0,7,5,2,10,8,8,4,12,1,7,3,10,11,2,6,0,13,5,9,11,7,0,2,9,5,13,12,4,8,3,1,6,10,13,2,9,11,4,7,0,1,6,5,10,8,3,12,10,5,8,0,12,6,2,3,7,13,1,9,4,11,3,13,6,5,10,8,1,0,9,11,4,7,12,2}

MinimumVertexColoring[{"Queen",{15,15}}]:=1+{1,10,2,3,8,4,11,12,7,14,13,0,9,6,5,13,3,1,6,2,5,0,10,8,9,12,11,14,7,4,0,7,5,11,1,9,14,2,6,4,3,13,12,10,8,9,12,14,7,6,8,1,4,5,2,11,10,0,3,13,11,6,3,4,9,0,12,13,10,8,14,1,5,2,7,12,14,8,13,3,11,2,5,4,1,6,7,10,0,9,4,2,12,5,10,6,13,7,3,11,0,9,8,14,1,5,11,4,1,7,14,10,0,9,13,8,2,3,12,6,2,13,7,10,0,12,4,8,14,5,9,6,11,1,3,10,0,9,8,5,2,3,6,1,12,4,14,7,13,11,8,1,6,2,13,7,9,14,11,0,10,3,4,5,12,14,4,0,9,12,1,6,3,2,7,5,8,13,11,10,7,9,11,14,4,3,5,1,13,10,2,12,6,8,0,3,8,13,12,11,10,7,9,0,6,1,5,2,4,14,6,5,10,0,14,13,8,11,12,3,7,4,1,9,2}

MinimumVertexColoring[{"Queen",{16,16}}]:=1+{0,4,12,8,11,15,2,6,7,3,14,10,9,13,5,1,1,8,11,3,6,12,14,5,4,15,13,7,2,10,9,0,7,5,15,0,8,11,13,2,3,12,10,9,1,14,4,6,9,13,2,14,5,6,1,10,11,0,7,4,15,3,12,8,4,14,6,13,1,10,9,3,2,8,11,0,12,7,15,5,10,3,1,9,12,5,7,15,14,6,4,13,8,0,2,11,15,9,10,7,2,0,4,12,13,5,1,3,6,11,8,14,12,2,5,6,15,1,10,9,8,11,0,14,7,4,3,13,14,0,7,4,13,3,8,11,10,9,2,12,5,6,1,15,13,11,8,5,0,2,6,14,15,7,3,1,4,9,10,12,8,1,3,11,14,7,5,13,12,4,6,15,10,2,0,9,6,12,4,15,3,8,11,1,0,10,9,2,14,5,13,7,11,15,0,12,7,4,3,8,9,2,5,6,13,1,14,10,5,7,13,2,10,9,15,0,1,14,8,11,3,12,6,4,3,10,9,1,4,14,12,7,6,13,15,5,0,8,11,2,2,6,14,10,9,13,0,4,5,1,12,8,11,15,7,3}

MinimumVertexColoring[{"Queen",{18,18}}]:=1+{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,8,4,5,6,1,10,17,3,2,15,14,0,7,16,11,12,13,9,10,13,8,14,0,6,15,12,16,1,5,2,11,17,3,9,4,7,16,7,17,13,8,11,5,14,15,2,3,12,6,9,4,0,10,1,2,8,12,1,7,13,3,0,11,6,17,14,4,10,16,5,9,15,6,14,10,16,15,17,12,13,9,8,4,5,0,2,1,7,3,11,5,16,0,11,9,2,14,10,4,13,7,3,15,8,6,17,1,12,11,2,3,12,17,4,16,9,7,10,8,1,13,0,5,14,15,6,9,17,4,7,3,1,2,5,6,11,12,15,16,14,10,13,0,8,4,11,9,10,12,15,0,1,14,3,16,17,2,5,7,8,6,13,7,3,16,0,13,9,11,2,5,12,15,6,8,4,17,1,14,10,13,9,15,5,10,0,1,6,3,14,11,16,17,7,12,2,8,4,15,5,6,8,14,16,7,17,13,4,0,10,1,3,9,11,12,2,14,0,1,2,5,8,4,11,10,7,6,13,9,12,15,16,17,3,1,12,13,15,11,14,10,8,17,0,9,7,3,6,2,4,5,16,3,15,7,17,6,12,9,4,1,16,13,8,5,11,0,10,2,14,17,6,14,9,2,7,13,16,12,5,1,4,10,15,8,3,11,0,12,10,11,4,16,3,8,15,0,17,2,9,14,1,13,6,7,5}

MinimumVertexColoring[{"Queen",{20,20}}]:=1+{0,4,8,12,11,16,6,19,15,3,2,14,18,7,17,10,13,9,5,1,8,15,0,4,18,12,2,11,6,17,16,7,10,3,13,19,5,1,14,9,4,18,17,8,0,10,3,15,12,7,6,13,14,2,11,1,9,16,19,5,11,0,4,13,14,2,7,8,19,16,17,18,9,6,3,15,12,5,1,10,13,19,14,0,4,9,16,2,10,6,7,11,3,17,8,5,1,15,18,12,14,10,18,17,5,6,13,1,9,2,3,8,0,12,7,4,16,19,11,15,18,3,7,16,10,1,9,12,5,14,15,4,13,8,0,11,17,6,2,19,7,9,13,5,3,15,19,16,1,10,11,0,17,18,14,2,4,12,8,6,19,12,1,11,17,5,8,6,2,15,14,3,7,9,4,16,10,0,13,18,1,7,9,3,15,19,12,5,16,11,10,17,4,13,18,14,2,8,6,0,3,5,11,1,13,17,14,7,18,9,8,19,6,15,16,12,0,10,4,2,17,14,3,9,19,7,10,4,0,13,12,1,5,11,6,18,8,2,15,16,5,11,15,7,1,13,17,18,3,8,9,2,19,16,12,0,6,14,10,4,16,1,5,18,8,3,11,14,7,12,13,6,15,10,2,9,19,4,0,17,12,8,16,19,7,4,15,3,11,0,1,10,2,14,5,6,18,17,9,13,15,17,12,2,6,11,18,0,8,4,5,9,1,19,10,7,3,13,16,14,9,2,6,15,12,0,5,10,17,18,19,16,11,4,1,13,14,7,3,8,6,16,19,10,2,8,1,13,14,5,4,15,12,0,9,3,11,18,17,7,10,13,2,6,16,14,0,9,4,19,18,5,8,1,15,17,7,3,12,11,2,6,10,14,9,18,4,17,13,1,0,12,16,5,19,8,15,11,7,3}

VertexColoringQ[GraphData[gn={"Queen",18{1,1}}],MinimumVertexColoring[gn]]

MinimumVertexDegree

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

FindSequenceFunction[seq,n]

MolecularTopologicalIndex

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

FindSequenceFunction[seq,n]//Factor

FindGeneratingFunction[seq,x]//Factor

Nonhamiltonian

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

OddChordlessCycleCount

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

PathCount

A291995

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n-2]//Factor

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

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

PathPolynomial

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

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

FullSimplify[poly2-poly]

PentagonCount

A288916

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

(seq=Table[CycleCount[QueenGraph[n,n],5],{n,50}])//Timing

coef=FindLinearRecurrence[seq]

FullSimplify[RSolve[Join[{a[n]==Sum[a[n-k]coef[[k]],{k,Length[coef]}]},Table[a[k]==seq[[k]],{k,Length[coef]}]],a[n],n],n∈Integers]

Table[(1/2160)(-41575+518049 n-1242186 (n^2)+1172970 (n^3)-485790 (n^4)+73026 (n^5)+576 (n^6)-45 (((-1))^n) (-867+1621 n-690 (n^2)+74 (n^3))+2560 Cos[((2 n π)/3)]),{n,20}]

Factor[(-867+n (1621-690 n+74 (n^2)))]

Take[seq,{3,Length[coef]+2}]

LinearRecurrence[{2,3,-7,-4,9,6,-6,-9,4,7,-3,-2,1},{0,0,376,4644,23920,81876,219384,499544,1014160,1885960,3280968,5402716,8516848},20]

seq=LinearRecurrence[{2,3,-7,-4,9,6,-6,-9,4,7,-3,-2,1},{0,0,376,4644,23920,81876,219384,499544,1014160,1885960,3280968,5402716,8516848},100]

FindSequenceFunction[seq,n]

Table[DifferenceRoot[{9001440+21670344 #2+7005616 ((#2)^2)+7848721 ((#2)^3)-9791276 ((#2)^4)+12064963 ((#2)^5)-3198041 ((#2)^6)+1765864 ((#2)^7)-465159 ((#2)^8)-3552 ((#2)^9)+(-8550+5790 #2-7380 ((#2)^2)+2220 ((#2)^3)) #1[#2]+(-32490+33000 #2-21420 ((#2)^2)+4440 ((#2)^3)) #1[1+#2]+(-32490+33000 #2-21420 ((#2)^2)+4440 ((#2)^3)) #1[2+#2]+(-23940+27210 #2-14040 ((#2)^2)+2220 ((#2)^3)) #1[3+#2]==0,#1[1]==0,#1[2]==0,#1[3]==376}&][n],{n,20}]

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

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

Perfect

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

Planar

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

Radius

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

RankPolynomial

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

Regular

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

ReliabilityPolynomial

(poly=Factor[Table[GraphData[{"Queen",{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[{"Queen",{n,n}},"SigmaPolynomial"],{n,k0=1,kmax=10}]/.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

A288951

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

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

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

Compute

SquareCount

A156001

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

(seq=Table[CycleCount[QueenGraph[n,n],4],{n,30}])//Timing

coef=FindLinearRecurrence[seq]

Take[seq,Length[coef]]

LinearRecurrence[{3,0,-8,6,6,-8,0,3,-1},{0,3,122,776,2704,6987,15206,29224,51680},30]

FindSequenceFunction[seq,n]//FullSimplify

Factor[(((-1))^n) (4+3 (-4+n) n)]

Table[(60-1296 n+3110 (n^2)-2325 (n^3)+505 (n^4)+21 (n^5)-15 (((-1))^n)(4-12 n+3 (n^2)))/60,{n,20}]

gf=x FindGeneratingFunction[Drop[seq,1],x]//Factor//Cancel

CoefficientList[Series[-((x (-3-113 x-410 (x^2)-400 (x^3)+167 (x^4)+297 (x^5)+126 (x^6)))/((((-1+x))^6) (((1+x))^3))),{x,0,20}],x]

StabilityIndex

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

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

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

TopologicalIndex

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

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

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

ToroidalCrossingNumber

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

Traceable

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

TriangleCount

A144298

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

(seq=Table[CycleCount[QueenGraph[n,n],3],{n,30}])//Timing

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]//FullSimplify

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

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

Factor[(5+2 n (-5+n+(n^2)))]

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

LinearRecurrence[{3,-1,-5,5,1,-3,1},{0,4,36,124,320,672,1260},20]

TuttePolynomial

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

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

Untraceable

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

VertexConnectivity

seq=Table[GraphData[{"Queen",{n,n}},"VertexConnectivity"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]

VertexCount

seq=Table[GraphData[{"Queen",{n,n}},"VertexCount"],{n,20}]

FindSequenceFunction[seq,n]

VertexCoverNumber

vertex cover number == vertex count - independence number

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

Table[Piecewise[{{3,n==2},{7,n==3}},n(n-1)],{n,20}]

(seq=Table[VertexCoverNumber[QueenGraph[n,n]],{n,6}])//Timing

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

VertexCoverPolynomial

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

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

coef=Factor/@FindLinearRecurrence[Rest@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[{"Queen",{n,n}},"VertexDegrees"],{n,20}]//Column

VertexTransitive

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

WienerIndex

A292057

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

FindSequenceFunction[seq,n]//Factor

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

FindLinearRecurrence[seq]

LinearRecurrence[{5,-10,10,-5,1},{0,6,44,164,440},20]

gf=x FindGeneratingFunction[seq,x]

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

WienerSumIndex

seq=Table[GraphData[{"Queen",{n,n}},"WienerSumIndex"],{n,20}]

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

GraphData

GraphClassString

"QueensTour"/.GraphData["TetrahedralGraph","NotationRules"]

GraphClassString[GraphData["QueensTour"]]

GraphClassString[GraphData["QueensTour",5;;]]

GraphDataString

Function[{m,n},Print[GraphDataString[QueenGraph[n,m],
"Name"->"("<>ToString[m]<>","<>ToString[n]<>")-queen's tour graph",
"StandardName"->{"QueensTour",{m,n}},
"Skip"->{"Perfect"},
"Classes"->{"QueensTour"},
"NotationRules"->{"QueensTour"->{m,n}},
TimeConstraint->60,
Debug->True,
MemoryConstraint->10^9
]]]@@@Sort[Flatten[Table[{m,n},{n,2,10},{m,2,n}],1]]

file=OpenWrite["~/queen.m"]

Do[
WriteString[file,
GraphDataString[QueenGraph[n,n],
"StandardName"->{"Queen",{n,n}},
"Name"->"("<>ToString[n]<>","<>ToString[n]<>")\[Hyphen]queen graph",
"NotationRules"->{"Queen"->{n,n}},
"Classes"->{"Queen"},
"Information"->"QueenGraph",
"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,11,20}
];

Close[file]