Andrásfai Graph

Author

Eric W. Weisstein
March 5, 2024

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

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

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

Figure

GraphicsGrid[Partition[Table[Show[AndrasfaiGraph[n]//StyleGraphs,PlotLabel->Style[HoldForm[n]==n,Directive[14,Black,FontFamily->"Times"]]],{n,6}],UpTo[3]],Alignment->Center,ImageSize->400,Dividers->All]

Definition

Mod

AndrasfaiGraph1[k_]:=System`CirculantGraph[3 k-1,Select[Range[3 k-1],Mod[#,3]==1&]]

AndrasfaiGraph1/@Range[4]

ToEntity/@Table[AndrasfaiGraph1[k],{k,10}]

Range

AndrasfaiGraph2[k_]:=System`CirculantGraph[3 k-1,Range[1,3k,3]]

AndrasfaiGraph2/@Range[4]

ToEntity/@Table[AndrasfaiGraph2[k],{k,10}]

Embeddings

<<MathWorld`Graphs`

{"Andrasfai", 4}

Names

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

GraphData[{"Andrasfai",4},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",4},"EdgeList"]]

Default embedding

GraphData[{"Andrasfai",4},"V"]

GraphPlot@GraphData[{"Andrasfai",4},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData[{"Andrasfai",4},"Configuration"]

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

Perspective

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

Perspective construction

GraphData[{"Andrasfai",4},"Polyhedron"]

GeneralizedPetersen

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

IGraph

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

Bilateral

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

Circular

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

Planar

GraphData[{"Andrasfai",4},"Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Andrasfai",4}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}],Max[OuterFace[#]]<=GraphData[{"Andrasfai",4},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",4}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union//Timing

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@MinimalCrossingGraph[GraphData[{"Andrasfai",4}],"CrossingNumber"->5]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",4},"Circulant"]

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

Complement graph

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

Line graph

GraphData[{"Andrasfai",4},"Line"]

LineGraphQ[GraphData[{"Andrasfai",4}]]//Timing

RootGraph

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

RootGraph[GraphData[{"Andrasfai",4}]]

Halin

GraphData[{"Andrasfai",4},"Halin"]

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

Rigid

GraphData[{"Andrasfai",4},"Rigid"]

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

Flexible

GraphData[{"Andrasfai",4},"Flexible"]

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

LCF

GraphData[{"Andrasfai",4},"LCF"]

GraphData[{"Andrasfai",4},"HamiltonianCycleCount"]

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

GraphData[{"Andrasfai",4},"LCFNotations"]

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

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

LCF compute largest

n=4;

try=Join[-Reverse[#],#]&/@With[{order=3n-1},Subsets[Range[order/2],{Floor[n/2-1]}]]

can=CanonicalGraph[GraphData[{"Andrasfai",n}]];

lcf=Select[try,CanonicalGraph[LCFGraph[{#},3n-1]]===can&]

LCF compute all

Divisors[GraphData[{"Andrasfai",4},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",4}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",4}],All])[[All,2]]]//Timing

lcf

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",4},"UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",4}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Andrasfai",4},"Matchstick"]

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Andrasfai",4},"Polyhedral"]

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

{"Andrasfai", 5}

Names

GraphData[{"Andrasfai",5},"StandardName"]

GraphData[{"Andrasfai",5},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",5},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",5},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

GraphData[{"Andrasfai",5},"Planar"]

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

MinimalCrossing

GraphData[{"Andrasfai",5},{"RCN","CN"}]

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

MinimalCrossing construction

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

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Andrasfai",5}],"CrossingNumber"->cn,RandomSeed->n]],{n,500}],Max[OuterFace[#]]<=GraphData[{"Andrasfai",5},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",5}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",5},"Circulant"]

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

Circulant construction

CirculantGraph1@@@CirculantIndices[GraphData[{"Andrasfai",5}]]

Halin

GraphData[{"Andrasfai",5},"Halin"]

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

LCF

GraphData[{"Andrasfai",5},"LCF"]

GraphData[{"Andrasfai",5},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",5},"LCFSignature"]

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

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

LCF compute largest

n=5;

try=Join[-Join[If[Mod[n,2]==2,{},{1-3n}/2],Reverse[#]],#]&/@With[{order=3n-1},Subsets[Range[order/2],{Floor[n/2-1]}]]

can=CanonicalGraph[GraphData[{"Andrasfai",n}]];

lcf=Select[try,CanonicalGraph[LCFGraph[{#},3n-1]]===can&]

LCF compute all

Divisors[GraphData[{"Andrasfai",5},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",5}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",5}],All])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,3,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",5},"UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",5}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Andrasfai",5},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Andrasfai",5}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"Andrasfai",5},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Andrasfai",5},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Andrasfai",5},"Polyhedral"]

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

{"Andrasfai", 6}

Names

GraphData[{"Andrasfai",6},"StandardName"]

GraphData[{"Andrasfai",6},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",6},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",6},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

GraphData[{"Andrasfai",6},"Planar"]

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

MinimalCrossing

GraphData[{"Andrasfai",6},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",6}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",6},"Circulant"]

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

Circulant construction

CirculantGraph1@@@CirculantIndices[GraphData[{"Andrasfai",6}]]

Halin

GraphData[{"Andrasfai",6},"Halin"]

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

LCF

GraphData[{"Andrasfai",6},"LCF"]

GraphData[{"Andrasfai",6},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",6},"LCFSignature"]

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

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

LCF compute largest

n=6;

try=Join[-Join[If[Mod[n,2]==0,{},{1-3n}/2],Reverse[#]],#]&/@With[{order=3n-1},Subsets[Range[order/2],{Floor[n/2-1]}]]

can=CanonicalGraph[GraphData[{"Andrasfai",n}]];

lcf={{#},3n-1}&/@Select[try,CanonicalGraph[LCFGraph[{#},3n-1]]===can&]

LCFGraph@@@lcf

LCF compute all

Divisors[GraphData[{"Andrasfai",6},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",6}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",6}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,3])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",6},"UnitDistance"]

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Andrasfai",6},"VertexList"],GraphData[{"Andrasfai",6},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Andrasfai",6},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Andrasfai",6},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Andrasfai",6},"Polyhedral"]

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

{"Andrasfai", 7}

Names

GraphData[{"Andrasfai",7},"StandardName"]

GraphData[{"Andrasfai",7},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",7},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",7},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

GraphData[{"Andrasfai",7},"Planar"]

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

MinimalCrossing

GraphData[{"Andrasfai",7},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",7},"Circulant"]

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

Circulant construction

CirculantGraph1@@@CirculantIndices[GraphData[{"Andrasfai",7}]]

Halin

GraphData[{"Andrasfai",7},"Halin"]

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

LCF

GraphData[{"Andrasfai",7},"LCF"]

GraphData[{"Andrasfai",7},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",7},"LCFSignature"]

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

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

GraphData[{"Andrasfai",7},"LCFNotations"]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,3,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Andrasfai",7},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute largest

n=7;

try=Join[-Join[If[Mod[n,2]==0,{},{1-3n}/2],Reverse[#]],#]&/@With[{order=3n-1},Subsets[Range[order/2],{Floor[n/2-1]}]]

can=CanonicalGraph[GraphData[{"Andrasfai",n}]];

lcf={{#},3n-1}&/@Select[try,CanonicalGraph[LCFGraph[{#},3n-1]]===can&]

LCFGraph@@@lcf

RecognizeGraph/@%

LCF compute all

Divisors[GraphData[{"Andrasfai",7},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",7}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",7}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Andrasfai",7},".m.gz"]])[[All,2]]]//Timing//AbsoluteTiming

DeleteCases[lcf,{_,1|2}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,4,3])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",7},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Andrasfai",7},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Andrasfai",7},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Andrasfai",7},"Polyhedral"]

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

{"Andrasfai", 8}

Names

GraphData[{"Andrasfai",8},"StandardName"]

GraphData[{"Andrasfai",8},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",8},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",8},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Perspective

GraphData[{"Andrasfai",8},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Andrasfai",8},"Polyhedron"]

Bilateral

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

Circular

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

Planar

GraphData[{"Andrasfai",8},"Planar"]

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

MinimalCrossing

GraphData[{"Andrasfai",8},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",8},"Circulant"]

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

Circulant construction

GraphData[{"Andrasfai",8},"NotationRules"]

ci=CirculantIndices[GraphData[{"Andrasfai",8}]]

CirculantGraph1@@@ci

CirculantGraph1@@@Cases[GraphData[{"Andrasfai",8},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",8},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",8},"Line"]

LineGraphQ[GraphData[{"Andrasfai",8}]]//Timing

RootGraph

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

RootGraph[GraphData[{"Andrasfai",8}]]

Halin

GraphData[{"Andrasfai",8},"Halin"]

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

Rigid

GraphData[{"Andrasfai",8},"Rigid"]

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

Flexible

GraphData[{"Andrasfai",8},"Flexible"]

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

LCF

GraphData[{"Andrasfai",8},"LCF"]

GraphData[{"Andrasfai",8},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",8},"LCFSignature"]

GraphData[{"Andrasfai",8},"LCFNotations"]

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

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

LCF compute largest

n=8;

try=Join[-Join[If[Mod[n,2]==0,{},{1-3n}/2],Reverse[#]],#]&/@With[{order=3n-1},Subsets[Range[order/2],{Floor[n/2-1]}]]

can=CanonicalGraph[GraphData[{"Andrasfai",n}]];

lcf={{#},3n-1}&/@Select[try,CanonicalGraph[LCFGraph[{#},3n-1]]===can&]

LCFGraph@@@lcf

RecognizeGraph/@%

LCF compute all

Divisors[GraphData[{"Andrasfai",8},"V"]]

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

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",8},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Andrasfai",8},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Andrasfai",8},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Andrasfai",8},"Polyhedral"]

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

{"Andrasfai", 9}

Names

GraphData[{"Andrasfai",9},"StandardName"]

GraphData[{"Andrasfai",9},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",9},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",9},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Perspective

GraphData[{"Andrasfai",9},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Andrasfai",9},"Polyhedron"]

Bilateral

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

Circular

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

Planar

GraphData[{"Andrasfai",9},"Planar"]

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

MinimalCrossing

GraphData[{"Andrasfai",9},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",9}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",9},"Circulant"]

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

Circulant construction

GraphData[{"Andrasfai",9},"NotationRules"]

ci=CirculantIndices[GraphData[{"Andrasfai",9}]]

CirculantGraph1@@@ci

gs=CirculantGraph1@@@Cases[GraphData[{"Andrasfai",9},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",9},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",9},"Line"]

LineGraphQ[GraphData[{"Andrasfai",9}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",9}&]

RootGraph[GraphData[{"Andrasfai",9}]]

Halin

GraphData[{"Andrasfai",9},"Halin"]

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

Rigid

GraphData[{"Andrasfai",9},"Rigid"]

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

Flexible

GraphData[{"Andrasfai",9},"Flexible"]

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

LCF

GraphData[{"Andrasfai",9},"LCF"]

GraphData[{"Andrasfai",9},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",9},"LCFSignature"]

GraphData[{"Andrasfai",9},"LCFNotations"]

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

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

LCF compute largest

n=9;

try=Join[-Join[If[Mod[n,2]==0,{},{1-3n}/2],Reverse[#]],#]&/@With[{order=3n-1},Subsets[Range[order/2],{Floor[n/2-1]}]]

can=CanonicalGraph[GraphData[{"Andrasfai",n}]];

lcf={{#},3n-1}&/@Select[try,CanonicalGraph[LCFGraph[{#},3n-1]]===can&]

BilateralLCFGraph@@@lcf

RecognizeGraph/@%

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",9}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Andrasfai",9},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",9}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",9}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",9},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",9}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Andrasfai",9},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Andrasfai",9},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Andrasfai",9},"Polyhedral"]

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

{"Andrasfai", 10}

Names

GraphData[{"Andrasfai",10},"StandardName"]

GraphData[{"Andrasfai",10},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",10},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",10},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Perspective

GraphData[{"Andrasfai",10},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Andrasfai",10},"Polyhedron"]

Bilateral

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

Circular

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

Planar

GraphData[{"Andrasfai",10},"Planar"]

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

MinimalCrossing

GraphData[{"Andrasfai",10},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",10}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",10},"Circulant"]

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

Circulant construction

GraphData[{"Andrasfai",10},"NotationRules"]

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

(ci2=CirculantIndices[GraphData[{"Andrasfai",10}],All,Method->"NextSubset"])//Timing

ci===ci2

CirculantGraph1@@@ci

gs=CirculantGraph1@@@Cases[GraphData[{"Andrasfai",10},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",10},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",10},"Line"]

LineGraphQ[GraphData[{"Andrasfai",10}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",10}&]

RootGraph[GraphData[{"Andrasfai",10}]]

Halin

GraphData[{"Andrasfai",10},"Halin"]

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

Rigid

GraphData[{"Andrasfai",10},"Rigid"]

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

Flexible

GraphData[{"Andrasfai",10},"Flexible"]

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

LCF

GraphData[{"Andrasfai",10},"LCF"]

GraphData[{"Andrasfai",10},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",10},"LCFSignature"]

GraphData[{"Andrasfai",10},"LCFNotations"]

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

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

LCF compute largest

n=10;

try=Join[-Join[If[Mod[n,2]==0,{},{1-3n}/2],Reverse[#]],#]&/@With[{order=3n-1},Subsets[Range[order/2],{Floor[n/2-1]}]]

Length[try]

can=CanonicalGraph[GraphData[{"Andrasfai",n}]];

lcf={{#},3n-1}&/@Select[try,CanonicalGraph[LCFGraph[{#},3n-1]]===can&]

BilateralLCFGraph@@@lcf

RecognizeGraph/@%

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",10}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2}]

LCF compute all

Divisors[GraphData[{"Andrasfai",10},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",10}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",10}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",10},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",10}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Andrasfai",10},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Andrasfai",10},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Andrasfai",10},"Polyhedral"]

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

{"Andrasfai", 11}

Names

GraphData[{"Andrasfai",11},"StandardName"]

GraphData[{"Andrasfai",11},"StandardNames"]

Primary

GraphData[{"Andrasfai",11}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Andrasfai",11},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",11},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",11},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Andrasfai",11},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Andrasfai",11},"Graph","Degenerate"]

Perspective

GraphData[{"Andrasfai",11},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Andrasfai",11},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Andrasfai",11},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Andrasfai",11},"Planar"]

GraphData[{"Andrasfai",11},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Andrasfai",11},{"RCN","CN"}]

GraphData[{"Andrasfai",11},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Andrasfai",11}],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Andrasfai",11}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Andrasfai",11}],TimeConstraint->3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Andrasfai",11}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",11}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",11},"Circulant"]

GraphData[{"Andrasfai",11},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Andrasfai",11},"NotationRules"]

ci=CirculantIndices[GraphData[{"Andrasfai",11}]]

gf=CirculantGraph1@@@ci

gs=CirculantGraph1@@@Cases[GraphData[{"Andrasfai",11},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",11},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",11},"Line"]

LineGraphQ[GraphData[{"Andrasfai",11}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",11}&]

RootGraph[GraphData[{"Andrasfai",11}]]

Halin

GraphData[{"Andrasfai",11},"Halin"]

GraphData[{"Andrasfai",11},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Andrasfai",11},"Rigid"]

GraphData[{"Andrasfai",11},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Andrasfai",11},"Flexible"]

GraphData[{"Andrasfai",11},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Andrasfai",11},"LCF"]

GraphData[{"Andrasfai",11},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",11},"LCFSignature"]

GraphData[{"Andrasfai",11},"LCFNotations"]

GraphData[{"Andrasfai",11},"Graph","LCF"]//StyleGraphs

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

LCF compute largest

n=11;

try=Join[-Join[If[Mod[n,2]==0,{},{1-3n}/2],Reverse[#]],#]&/@With[{order=3n-1},Subsets[Range[order/2],{Floor[n/2-1]}]]

can=CanonicalGraph[GraphData[{"Andrasfai",n}]];

lcf={{#},3n-1}&/@Select[try,CanonicalGraph[LCFGraph[{#},3n-1]]===can&]

BilateralLCFGraph@@@lcf

RecognizeGraph/@%

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",11}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Andrasfai",11},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",11}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",11}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",11},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Andrasfai",11}],Debug->True]//Timing

GraphData[{"Andrasfai",11},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Andrasfai",11},"VertexList"],GraphData[{"Andrasfai",11},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",11}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",11}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Andrasfai",11},"Matchstick"]

GraphData[{"Andrasfai",11},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Andrasfai",11},"Edges"]]

3D All

GraphData[{"Andrasfai",11},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Andrasfai",11},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Andrasfai",11},"Polyhedral"]

GraphData[{"Andrasfai",11},"Graph",{"3D","Polyhedron"}]

{"Andrasfai", 12}

Names

GraphData[{"Andrasfai",12},"StandardName"]

GraphData[{"Andrasfai",12},"StandardNames"]

Primary

GraphData[{"Andrasfai",12}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Andrasfai",12},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",12},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",12},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Andrasfai",12},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Andrasfai",12},"Graph","Degenerate"]

Perspective

GraphData[{"Andrasfai",12},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Andrasfai",12},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Andrasfai",12},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Andrasfai",12},"Planar"]

GraphData[{"Andrasfai",12},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Andrasfai",12},{"RCN","CN"}]

GraphData[{"Andrasfai",12},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Andrasfai",12}],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Andrasfai",12}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Andrasfai",12}],TimeConstraint->3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Andrasfai",12}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",12}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",12},"Circulant"]

GraphData[{"Andrasfai",12},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Andrasfai",12},"NotationRules"]

ci=CirculantIndices[GraphData[{"Andrasfai",12}]]

CirculantGraph1@@@ci

gs=CirculantGraph1@@@Cases[GraphData[{"Andrasfai",12},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",12},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",12},"Line"]

LineGraphQ[GraphData[{"Andrasfai",12}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",12}&]

RootGraph[GraphData[{"Andrasfai",12}]]

Halin

GraphData[{"Andrasfai",12},"Halin"]

GraphData[{"Andrasfai",12},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Andrasfai",12},"Rigid"]

GraphData[{"Andrasfai",12},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Andrasfai",12},"Flexible"]

GraphData[{"Andrasfai",12},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Andrasfai",12},"LCF"]

GraphData[{"Andrasfai",12},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",12},"LCFSignature"]

GraphData[{"Andrasfai",12},"LCFNotations"]

GraphData[{"Andrasfai",12},"Graph","LCF"]//StyleGraphs

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

LCF compute largest

n=12;

try=Join[-Join[If[Mod[n,2]==0,{},{1-3n}/2],Reverse[#]],#]&/@With[{order=3n-1},Subsets[Range[order/2],{Floor[n/2-1]}]]

Length[try]

can=CanonicalGraph[GraphData[{"Andrasfai",n}]];

lcf={{#},3n-1}&/@Select[try,CanonicalGraph[LCFGraph[{#},3n-1]]===can&]

BilateralLCFGraph@@@lcf

RecognizeGraph/@%

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",12}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Andrasfai",12},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",12}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",12}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",12},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Andrasfai",12}],Debug->True]//Timing

GraphData[{"Andrasfai",12},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Andrasfai",12},"VertexList"],GraphData[{"Andrasfai",12},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",12}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",12}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Andrasfai",12},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Andrasfai",12}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"Andrasfai",12},"Matchstick"]

GraphData[{"Andrasfai",12},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Andrasfai",12},"Edges"]]

3D All

GraphData[{"Andrasfai",12},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Andrasfai",12},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Andrasfai",12},"Polyhedral"]

GraphData[{"Andrasfai",12},"Graph",{"3D","Polyhedron"}]

{"Andrasfai", 13}

Names

GraphData[{"Andrasfai",13},"StandardName"]

GraphData[{"Andrasfai",13},"StandardNames"]

Primary

GraphData[{"Andrasfai",13}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Andrasfai",13},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",13},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",13},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Andrasfai",13},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Andrasfai",13},"Graph","Degenerate"]

Perspective

GraphData[{"Andrasfai",13},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Andrasfai",13},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Andrasfai",13},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Andrasfai",13},"Planar"]

GraphData[{"Andrasfai",13},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Andrasfai",13},{"RCN","CN"}]

GraphData[{"Andrasfai",13},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Andrasfai",13}],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Andrasfai",13}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Andrasfai",13}],TimeConstraint->3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Andrasfai",13}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",13}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",13},"Circulant"]

GraphData[{"Andrasfai",13},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Andrasfai",13},"NotationRules"]

ci=CirculantIndices[GraphData[{"Andrasfai",13}]]

gs=CirculantGraph1@@@ci

gs=CirculantGraph1@@@Cases[GraphData[{"Andrasfai",13},"StandardNames"],{"Circulant",i_}:>i]

Quit

Complement graph

GraphData[{"Andrasfai",13},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",13},"Line"]

LineGraphQ[GraphData[{"Andrasfai",13}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",13}&]

RootGraph[GraphData[{"Andrasfai",13}]]

Halin

GraphData[{"Andrasfai",13},"Halin"]

GraphData[{"Andrasfai",13},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Andrasfai",13},"Rigid"]

GraphData[{"Andrasfai",13},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Andrasfai",13},"Flexible"]

GraphData[{"Andrasfai",13},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Andrasfai",13},"LCF"]

GraphData[{"Andrasfai",13},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",13},"LCFSignature"]

GraphData[{"Andrasfai",13},"LCFNotations"]

GraphData[{"Andrasfai",13},"Graph","LCF"]//StyleGraphs

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

LCF compute largest

n=13;

try=Join[-Join[If[Mod[n,2]==0,{},{1-3n}/2],Reverse[#]],#]&/@With[{order=3n-1},Subsets[Range[order/2],{Floor[n/2-1]}]]

Length[try]

can=CanonicalGraph[GraphData[{"Andrasfai",n}]];

(lcf={{#},3n-1}&/@Select[try,CanonicalGraph[LCFGraph[{#},3n-1]]===can&])//Timing

BilateralLCFGraph@@@lcf

RecognizeGraph/@%

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",13}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Andrasfai",13},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",13}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",13}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",13},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Andrasfai",13}],Debug->True]//Timing

GraphData[{"Andrasfai",13},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Andrasfai",13},"VertexList"],GraphData[{"Andrasfai",13},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",13}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",13}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Andrasfai",13},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Andrasfai",13}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"Andrasfai",13},"Matchstick"]

GraphData[{"Andrasfai",13},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Andrasfai",13},"Edges"]]

3D All

GraphData[{"Andrasfai",13},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Andrasfai",13},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Andrasfai",13},"Polyhedral"]

GraphData[{"Andrasfai",13},"Graph",{"3D","Polyhedron"}]

{"Andrasfai", 14}

Names

GraphData[{"Andrasfai",14},"StandardName"]

GraphData[{"Andrasfai",14},"StandardNames"]

Primary

GraphData[{"Andrasfai",14}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Andrasfai",14},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",14},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",14},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Andrasfai",14},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Andrasfai",14},"Graph","Degenerate"]

Perspective

GraphData[{"Andrasfai",14},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Andrasfai",14},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Andrasfai",14},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Andrasfai",14},"Planar"]

GraphData[{"Andrasfai",14},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Andrasfai",14},{"RCN","CN"}]

GraphData[{"Andrasfai",14},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Andrasfai",14}],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Andrasfai",14}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Andrasfai",14}],TimeConstraint->3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Andrasfai",14}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",14}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",14},"Circulant"]

GraphData[{"Andrasfai",14},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Andrasfai",14},"NotationRules"]

(ci=CirculantIndices[GraphData[{"Andrasfai",14}]])//Timing

gs=CirculantGraph1@@@ci

CirculantGraph1@@@Cases[GraphData[{"Andrasfai",14},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",14},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",14},"Line"]

LineGraphQ[GraphData[{"Andrasfai",14}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",14}&]

RootGraph[GraphData[{"Andrasfai",14}]]

Halin

GraphData[{"Andrasfai",14},"Halin"]

GraphData[{"Andrasfai",14},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Andrasfai",14},"Rigid"]

GraphData[{"Andrasfai",14},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Andrasfai",14},"Flexible"]

GraphData[{"Andrasfai",14},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Andrasfai",14},"LCF"]

GraphData[{"Andrasfai",14},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",14},"LCFSignature"]

GraphData[{"Andrasfai",14},"LCFNotations"]

GraphData[{"Andrasfai",14},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",14}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Andrasfai",14},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",14}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",14}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",14},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Andrasfai",14}],Debug->True]//Timing

GraphData[{"Andrasfai",14},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Andrasfai",14},"VertexList"],GraphData[{"Andrasfai",14},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",14}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",14}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Andrasfai",14},"Matchstick"]

GraphData[{"Andrasfai",14},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Andrasfai",14},"Edges"]]

3D All

GraphData[{"Andrasfai",14},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Andrasfai",14},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Andrasfai",14},"Polyhedral"]

GraphData[{"Andrasfai",14},"Graph",{"3D","Polyhedron"}]

{"Andrasfai", 15}

Names

GraphData[{"Andrasfai",15},"StandardName"]

GraphData[{"Andrasfai",15},"StandardNames"]

Primary

GraphData[{"Andrasfai",15}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Andrasfai",15},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",15},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",15},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Andrasfai",15},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Andrasfai",15},"Graph","Degenerate"]

Perspective

GraphData[{"Andrasfai",15},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Andrasfai",15},"Polyhedron"]

Bilateral

GraphData[{"Andrasfai",15},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Andrasfai",15},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Andrasfai",15},"Planar"]

GraphData[{"Andrasfai",15},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Andrasfai",15},{"RCN","CN"}]

GraphData[{"Andrasfai",15},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Andrasfai",15}],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Andrasfai",15}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Andrasfai",15}],TimeConstraint->3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Andrasfai",15}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",15}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",15},"Circulant"]

GraphData[{"Andrasfai",15},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Andrasfai",15},"NotationRules"]

(ci=CirculantIndices[GraphData[{"Andrasfai",15}]])//Timing

gs=CirculantGraph1@@@ci

CirculantGraph1@@@Cases[GraphData[{"Andrasfai",15},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",15},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",15},"Line"]

LineGraphQ[GraphData[{"Andrasfai",15}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",15}&]

RootGraph[GraphData[{"Andrasfai",15}]]

Halin

GraphData[{"Andrasfai",15},"Halin"]

GraphData[{"Andrasfai",15},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Andrasfai",15},"Rigid"]

GraphData[{"Andrasfai",15},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Andrasfai",15},"Flexible"]

GraphData[{"Andrasfai",15},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Andrasfai",15},"LCF"]

GraphData[{"Andrasfai",15},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",15},"LCFSignature"]

GraphData[{"Andrasfai",15},"LCFNotations"]

GraphData[{"Andrasfai",15},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",15}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Andrasfai",15},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",15}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",15}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",15},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Andrasfai",15}],Debug->True]//Timing

GraphData[{"Andrasfai",15},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Andrasfai",15},"VertexList"],GraphData[{"Andrasfai",15},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",15}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",15}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Andrasfai",15},"Matchstick"]

GraphData[{"Andrasfai",15},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Andrasfai",15},"Edges"]]

3D All

GraphData[{"Andrasfai",15},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Andrasfai",15},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Andrasfai",15},"Polyhedral"]

GraphData[{"Andrasfai",15},"Graph",{"3D","Polyhedron"}]

{"Andrasfai", 16}

Names

GraphData[{"Andrasfai",16},"StandardName"]

GraphData[{"Andrasfai",16},"StandardNames"]

Primary

GraphData[{"Andrasfai",16}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Andrasfai",16},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",16},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",16},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Andrasfai",16},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Andrasfai",16},"Graph","Degenerate"]

Perspective

GraphData[{"Andrasfai",16},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Andrasfai",16},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Andrasfai",16},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Andrasfai",16},"Planar"]

GraphData[{"Andrasfai",16},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Andrasfai",16},{"RCN","CN"}]

GraphData[{"Andrasfai",16},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Andrasfai",16}],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Andrasfai",16}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Andrasfai",16}],TimeConstraint->3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Andrasfai",16}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",16}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",16},"Circulant"]

GraphData[{"Andrasfai",16},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Andrasfai",16},"NotationRules"]

(ci=CirculantIndices[GraphData[{"Andrasfai",16}]])//Timing

MaxMemoryUsed[]/10^9.

(ci2=CirculantIndices[GraphData[{"Andrasfai",16}],Method->"NextSubset",Debug->True])//Timing

ci===ci2

gs=CirculantGraph1@@@ci

CirculantGraph1@@@Cases[GraphData[{"Andrasfai",16},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",16},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",16},"Line"]

LineGraphQ[GraphData[{"Andrasfai",16}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",16}&]

RootGraph[GraphData[{"Andrasfai",16}]]

Halin

GraphData[{"Andrasfai",16},"Halin"]

GraphData[{"Andrasfai",16},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Andrasfai",16},"Rigid"]

GraphData[{"Andrasfai",16},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Andrasfai",16},"Flexible"]

GraphData[{"Andrasfai",16},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Andrasfai",16},"LCF"]

GraphData[{"Andrasfai",16},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",16},"LCFSignature"]

GraphData[{"Andrasfai",16},"LCFNotations"]

GraphData[{"Andrasfai",16},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",16}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Andrasfai",16},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",16}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",16}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",16},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Andrasfai",16}],Debug->True]//Timing

GraphData[{"Andrasfai",16},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Andrasfai",16},"VertexList"],GraphData[{"Andrasfai",16},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",16}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",16}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Andrasfai",16},"Matchstick"]

GraphData[{"Andrasfai",16},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Andrasfai",16},"Edges"]]

3D All

GraphData[{"Andrasfai",16},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Andrasfai",16},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Andrasfai",16},"Polyhedral"]

GraphData[{"Andrasfai",16},"Graph",{"3D","Polyhedron"}]

{"Andrasfai", 17}

Names

GraphData[{"Andrasfai",17},"StandardName"]

GraphData[{"Andrasfai",17},"StandardNames"]

Primary

GraphData[{"Andrasfai",17}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Andrasfai",17},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",17},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",17},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Andrasfai",17},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Andrasfai",17},"Graph","Degenerate"]

Perspective

GraphData[{"Andrasfai",17},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Andrasfai",17},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Andrasfai",17},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Andrasfai",17},"Planar"]

GraphData[{"Andrasfai",17},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Andrasfai",17},{"RCN","CN"}]

GraphData[{"Andrasfai",17},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Andrasfai",17}],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Andrasfai",17}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Andrasfai",17}],TimeConstraint->3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Andrasfai",17}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",17}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",17},"Circulant"]

GraphData[{"Andrasfai",17},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Andrasfai",17},"NotationRules"]

(ci=CirculantIndices[AndrasfaiGraph[17],Debug->True])//Timing

ci={{50,{1,3,10,12,14,16,21,23,25}},{50,{1,4,7,9,12,17,20,22,25}},{50,{1,4,7,10,13,16,19,22,25}},{50,{1,6,8,11,13,18,20,23,25}},{50,{2,3,7,11,12,16,20,21,25}},{50,{2,3,8,9,13,14,19,20,25}},{50,{2,6,9,10,13,14,17,21,25}},{50,{3,4,10,11,17,18,19,24,25}},{50,{6,7,8,9,10,11,23,24,25}},{50,{17,18,19,20,21,22,23,24,25}}};

gs=CirculantGraph1@@@ci

CirculantGraph1@@@Cases[GraphData[{"Andrasfai",17},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",17},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",17},"Line"]

LineGraphQ[GraphData[{"Andrasfai",17}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",17}&]

RootGraph[GraphData[{"Andrasfai",17}]]

Halin

GraphData[{"Andrasfai",17},"Halin"]

GraphData[{"Andrasfai",17},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Andrasfai",17},"Rigid"]

GraphData[{"Andrasfai",17},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Andrasfai",17},"Flexible"]

GraphData[{"Andrasfai",17},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Andrasfai",17},"LCF"]

GraphData[{"Andrasfai",17},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",17},"LCFSignature"]

GraphData[{"Andrasfai",17},"LCFNotations"]

GraphData[{"Andrasfai",17},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",17}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Andrasfai",17},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",17}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",17}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",17},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Andrasfai",17}],Debug->True]//Timing

GraphData[{"Andrasfai",17},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Andrasfai",17},"VertexList"],GraphData[{"Andrasfai",17},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",17}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",17}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Andrasfai",17},"Matchstick"]

GraphData[{"Andrasfai",17},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Andrasfai",17},"Edges"]]

3D All

GraphData[{"Andrasfai",17},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Andrasfai",17},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Andrasfai",17},"Polyhedral"]

GraphData[{"Andrasfai",17},"Graph",{"3D","Polyhedron"}]

{"Andrasfai", 18}

Names

GraphData[{"Andrasfai",18},"StandardName"]

GraphData[{"Andrasfai",18},"StandardNames"]

Primary

GraphData[{"Andrasfai",18}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Andrasfai",18},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",18},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",18},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Andrasfai",18},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Andrasfai",18},"Graph","Degenerate"]

Perspective

GraphData[{"Andrasfai",18},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Andrasfai",18},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Andrasfai",18},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Andrasfai",18},"Planar"]

GraphData[{"Andrasfai",18},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Andrasfai",18},{"RCN","CN"}]

GraphData[{"Andrasfai",18},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Andrasfai",18}],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Andrasfai",18}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Andrasfai",18}],TimeConstraint->3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Andrasfai",18}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",18}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",18},"Circulant"]

GraphData[{"Andrasfai",18},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Andrasfai",18},"NotationRules"]

(ci=CirculantIndices[AndrasfaiGraph[18],Debug->True])//Timing

ci={{53,{1,3,5,7,9,11,13,15,17}},{53,{1,3,5,12,14,16,18,20,22}},{53,{1,3,8,10,12,14,19,21,23}},{53,{1,4,6,9,11,14,16,19,24}},{53,{1,4,6,11,13,16,18,23,25}},{53,{1,4,7,9,12,15,17,20,25}},{53,{1,4,7,10,13,15,18,21,24}},{53,{1,4,7,10,13,16,19,22,25}},{53,{1,6,8,10,13,15,17,22,24}},{53,{2,3,7,8,12,17,21,22,26}},{53,{2,3,8,9,14,15,20,21,26}},{53,{2,3,8,13,14,18,19,23,24}},{53,{2,5,8,11,14,17,20,23,26}},{53,{2,5,8,12,15,18,21,22,25}},{53,{2,5,9,12,16,19,20,23,26}},{53,{2,6,7,11,15,16,20,24,25}},{53,{2,6,9,10,13,17,21,24,25}},{53,{2,6,10,14,18,19,22,23,26}},{53,{3,4,5,11,12,18,19,20,26}},{53,{3,4,5,12,13,14,21,22,23}},{53,{3,4,9,10,11,16,17,23,24}},{53,{4,5,6,7,15,16,17,25,26}},{53,{5,6,7,8,18,19,20,21,22}},{53,{6,7,8,9,10,11,24,25,26}},{53,{9,10,11,12,13,14,15,16,17}},{53,{18,19,20,21,22,23,24,25,26}}};

gs=CirculantGraph1@@@ci

gs=CirculantGraph1@@@Cases[GraphData[{"Andrasfai",18},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",18},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",18},"Line"]

LineGraphQ[GraphData[{"Andrasfai",18}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",18}&]

RootGraph[GraphData[{"Andrasfai",18}]]

Halin

GraphData[{"Andrasfai",18},"Halin"]

GraphData[{"Andrasfai",18},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Andrasfai",18},"Rigid"]

GraphData[{"Andrasfai",18},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Andrasfai",18},"Flexible"]

GraphData[{"Andrasfai",18},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Andrasfai",18},"LCF"]

GraphData[{"Andrasfai",18},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",18},"LCFSignature"]

GraphData[{"Andrasfai",18},"LCFNotations"]

GraphData[{"Andrasfai",18},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",18}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Andrasfai",18},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",18}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",18}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",18},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Andrasfai",18}],Debug->True]//Timing

GraphData[{"Andrasfai",18},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Andrasfai",18},"VertexList"],GraphData[{"Andrasfai",18},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",18}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",18}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Andrasfai",18},"Matchstick"]

GraphData[{"Andrasfai",18},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Andrasfai",18},"Edges"]]

3D All

GraphData[{"Andrasfai",18},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Andrasfai",18},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Andrasfai",18},"Polyhedral"]

GraphData[{"Andrasfai",18},"Graph",{"3D","Polyhedron"}]

{"Andrasfai", 19}

Names

GraphData[{"Andrasfai",19},"StandardName"]

GraphData[{"Andrasfai",19},"StandardNames"]

Primary

GraphData[{"Andrasfai",19}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Andrasfai",19},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",19},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",19},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Andrasfai",19},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Andrasfai",19},"Graph","Degenerate"]

Perspective

GraphData[{"Andrasfai",19},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Andrasfai",19},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Andrasfai",19},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Andrasfai",19},"Planar"]

GraphData[{"Andrasfai",19},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Andrasfai",19},{"RCN","CN"}]

GraphData[{"Andrasfai",19},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Andrasfai",19}],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Andrasfai",19}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Andrasfai",19}],TimeConstraint->3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Andrasfai",19}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",19}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",19},"Circulant"]

GraphData[{"Andrasfai",19},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Andrasfai",19},"NotationRules"]

(ci=CirculantIndices[GraphData[{"Andrasfai",19}]])//Timing

gs=CirculantGraph1@@@ci

CirculantGraph1@@@Cases[GraphData[{"Andrasfai",19},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",19},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",19},"Line"]

LineGraphQ[GraphData[{"Andrasfai",19}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",19}&]

RootGraph[GraphData[{"Andrasfai",19}]]

Halin

GraphData[{"Andrasfai",19},"Halin"]

GraphData[{"Andrasfai",19},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Andrasfai",19},"Rigid"]

GraphData[{"Andrasfai",19},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Andrasfai",19},"Flexible"]

GraphData[{"Andrasfai",19},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Andrasfai",19},"LCF"]

GraphData[{"Andrasfai",19},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",19},"LCFSignature"]

GraphData[{"Andrasfai",19},"LCFNotations"]

GraphData[{"Andrasfai",19},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",19}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Andrasfai",19},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",19}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",19}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",19},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Andrasfai",19}],Debug->True]//Timing

GraphData[{"Andrasfai",19},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Andrasfai",19},"VertexList"],GraphData[{"Andrasfai",19},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",19}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",19}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Andrasfai",19},"Matchstick"]

GraphData[{"Andrasfai",19},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Andrasfai",19},"Edges"]]

3D All

GraphData[{"Andrasfai",19},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Andrasfai",19},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Andrasfai",19},"Polyhedral"]

GraphData[{"Andrasfai",19},"Graph",{"3D","Polyhedron"}]

{"Andrasfai", 20}

Names

GraphData[{"Andrasfai",20},"StandardName"]

GraphData[{"Andrasfai",20},"StandardNames"]

Primary

GraphData[{"Andrasfai",20}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Andrasfai",20},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Andrasfai",20},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Andrasfai",20},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Andrasfai",20},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Andrasfai",20},"Graph","Degenerate"]

Perspective

GraphData[{"Andrasfai",20},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Andrasfai",20},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Andrasfai",20},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Andrasfai",20},"Planar"]

GraphData[{"Andrasfai",20},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Andrasfai",20},{"RCN","CN"}]

GraphData[{"Andrasfai",20},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Andrasfai",20}],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Andrasfai",20}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Andrasfai",20}],TimeConstraint->3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Andrasfai",20}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Andrasfai",20}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Andrasfai",20},"Circulant"]

GraphData[{"Andrasfai",20},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Andrasfai",20},"NotationRules"]

(ci=CirculantIndices[GraphData[{"Andrasfai",20}]])//Timing

gs=CirculantGraph1@@@ci

CirculantGraph1@@@Cases[GraphData[{"Andrasfai",20},"StandardNames"],{"Circulant",i_}:>i]

Complement graph

GraphData[{"Andrasfai",20},"ComplementGraph","Name"]

Line graph

GraphData[{"Andrasfai",20},"Line"]

LineGraphQ[GraphData[{"Andrasfai",20}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Andrasfai",20}&]

RootGraph[GraphData[{"Andrasfai",20}]]

Halin

GraphData[{"Andrasfai",20},"Halin"]

GraphData[{"Andrasfai",20},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Andrasfai",20},"Rigid"]

GraphData[{"Andrasfai",20},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Andrasfai",20},"Flexible"]

GraphData[{"Andrasfai",20},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Andrasfai",20},"LCF"]

GraphData[{"Andrasfai",20},"HamiltonianCycleCount"]

GraphData[{"Andrasfai",20},"LCFSignature"]

GraphData[{"Andrasfai",20},"LCFNotations"]

GraphData[{"Andrasfai",20},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Andrasfai",20}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Andrasfai",20},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Andrasfai",20}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Andrasfai",20}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Andrasfai",20},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Andrasfai",20}],Debug->True]//Timing

GraphData[{"Andrasfai",20},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Andrasfai",20},"VertexList"],GraphData[{"Andrasfai",20},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",20}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Andrasfai",20}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Andrasfai",20},"Matchstick"]

GraphData[{"Andrasfai",20},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Andrasfai",20},"Edges"]]

3D All

GraphData[{"Andrasfai",20},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Andrasfai",20},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Andrasfai",20},"Polyhedral"]

GraphData[{"Andrasfai",20},"Graph",{"3D","Polyhedron"}]

Special cases

GraphData["Andrasfai"]

ToEntity/@AndrasfaiGraph/@Range[10]

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

RecognizeGraph/@AndrasfaiGraph/@Range[20]

Properties

Acyclic

seq=Table[GraphData[{"Andrasfai",n},"Acyclic"],{n,10}]

AdjacencyMatrix

a[n_]:=SparseArray[{i_,j_}:>1/;Mod[Abs[i-j],3]==1,(3n-1){1,1}]

Table[AdjacencyGraph[a[n]]//RecognizeGraph,{n,10}]

AdjacencyMatrixCount

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

Table[(((3n-1)!)/(2Piecewise[{{1,n==1}},(3n-1)])),{n,10}]

FullSimplify[(((3n-1)!)/(2Piecewise[{{1,n==1}},(3n-1)]))]

Table[Piecewise[{{1,n==1}},Gamma[3n-1]/2],{n,10}]

Arboricity

Table[GraphData[{"Andrasfai",n},"Arboricity"],{n,10}]

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

Table[Floor[n/2]+1,{n,20}]

ArcTransitive

seq=Table[GraphData[{"Andrasfai",n},"ArcTransitive"],{n,10}]

ArcTransitivity

seq=Table[GraphData[{"Andrasfai",n},"ArcTransitivity"],{n,10}]

AutomorphismCount

seq=Table[GraphData[{"Andrasfai",n},"AutomorphismCount"],{n,10}]

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

BalabanIndex

seq=Table[GraphData[{"Andrasfai",n},"BalabanIndex"],{n,10}]

FindSequenceFunction[seq,n]//Factor

Bandwidth

Probably 2n for n>2

seq=Table[GraphData[{"Andrasfai",n},"Bandwidth"],{n,10}]

BridgeCount

seq=Table[GraphData[{"Andrasfai",n},"BridgeCount"],{n,10}]

BurningNumber

seq=Table[GraphData[{"Andrasfai",n},"BurningNumber"],{n,10}]

CharacteristicPolynomial

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

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

FullSimplify[poly2-poly]

Chordal

seq=Table[GraphData[{"Andrasfai",n},"Chordal"],{n,10}]

ChordCount

seq=Table[GraphData[{"Andrasfai",n},"ChordCount"],{n,10}]

Table[GraphData[{"Andrasfai",n},"EdgeCount"],{n,10}]

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

Chordless

seq=Table[GraphData[{"Andrasfai",n},"Chordless"],{n,10}]

ChordlessCycleCount

seq=Table[GraphData[{"Andrasfai",n},"ChordlessCycleCount"],{n,10}]

FindLinearRecurrence[DeleteMissing[seq]]

FindSequenceFunction[DeleteMissing[seq],n]

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

Chords

seq=Table[GraphData[{"Andrasfai",n},"Chords"],{n,10}]

ChromaticallyUnique

seq=Table[GraphData[{"Andrasfai",n},"ChromaticallyUnique"],{n,10}]

GraphData[{"ChromaticallyUnique","Andrasfai"}]

ChromaticInvariant

A280333

seq=Table[GraphData[{"Andrasfai",n},"ChromaticInvariant"],{n,10}]

seq={1,12,815,157762,64916201,48508522364};

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n-1]

(x^2) FindGeneratingFunction[seq,x]

Do[Print[{n,Abs[Derivative[1][System`ChromaticPolynomial[System`CirculantGraph[3n-1,Range[1,3n,3]]]][1]]//Timing}],{n,7}]

ChromaticNumber

seq=Table[GraphData[{"Andrasfai",n},"ChromaticNumber"],{n,10}]

ChromaticPolynomial

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

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

FindLinearRecurrence[Take[poly,{2,6}]/(x(x-1)(x-2))]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

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

FullSimplify[poly2-poly]

Circumference

seq=Table[GraphData[{"Andrasfai",n},"Circumference"],{n,10}]

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

Classes

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

CliqueCount

A115067

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

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]//Factor

seq=Table[(3n+5)n/2,{n,0,20}]

LinearRecurrence[{3,-3,1},{0,4,11},20]

gf=x FindGeneratingFunction[seq,x]

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

CliqueCoveringNumber

seq=Table[GraphData[{"Andrasfai",n},"CliqueCoveringNumber"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

gf=x FindGeneratingFunction[seq,x]

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

CliqueNumber

seq=Table[GraphData[{"Andrasfai",n},"CliqueNumber"],{n,10}]

CliquePolynomial

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

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

FullSimplify[poly2-poly]

CochromaticGraphNames

Table[GraphData[{"Andrasfai",n},"CochromaticGraphNames"],{n,10}]

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

ComplementOddChordlessCycleCount

A051836

Table[GraphData[{"Andrasfai",n},"ComplementGraphName"],{n,10}]

seq=Table[GraphData[{"Andrasfai",n},"ComplementOddChordlessCycleCount"],{n,10}]

FindSequenceFunction[DeleteMissing[seq],n]//Factor

(1/5)Binomial[n+2,n-2](3n-1)

ConnectedComponentCount

seq=Table[GraphData[{"Andrasfai",n},"ConnectedComponentCount"],{n,10}]

ConnectedDominatingSetCount

A287429

seq=Table[GraphData[{"Andrasfai",n},"ConnectedDominatingSetCount"],{n,10}]

FindLinearRecurrence[DeleteMissing[seq]]

FindSequenceFunction[DeleteMissing[seq],n]

FindSequenceFunction[DeleteCases[Rest@seq,_Missing],n-1]

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

ConnectedDominationNumber

seq=Table[GraphData[{"Andrasfai",n},"ConnectedDominationNumber"],{n,10}]

ConnectedDominationPolynomial

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

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

FullSimplify[poly2-poly]

ConnectedInducedSubgraphCount

A287995

seq=Table[GraphData[{"Andrasfai",n},"ConnectedInducedSubgraphCount"],{n,10}]

FindLinearRecurrence[DeleteMissing[seq]]

FindSequenceFunction[DeleteMissing[seq],n]

FindSequenceFunction[DeleteCases[Rest@seq,_Missing],n-1]

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

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

ConnectedInducedSubgraphPolynomial

(poly=Factor[Table[GraphData[{"Andrasfai",n},"ConnectedInducedSubgraphPolynomial"],{n,k0=2,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]

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

FullSimplify[poly2-poly]

CrossingNumber

seq=Table[GraphData[{"Andrasfai",n},"CrossingNumber"],{n,10}]

CycleCount

A234602

seq=Table[GraphData[{"Andrasfai",n},"CycleCount"],{n,10}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

CyclePolynomial

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

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

FullSimplify[poly2-poly]

Cyclic

Table[GraphData[{"Andrasfai",n},"Cyclic"],{n,10}]

CyclomaticNumber

seq=Table[GraphData[{"Andrasfai",n},"CyclomaticNumber"],{n,10}]

FindSequenceFunction[seq,n]//Factor

DetourIndex

seq=Table[GraphData[{"Andrasfai",n},"DetourIndex"],{n,10}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

DetourMatrix

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

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

DetourPolynomial

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

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

FullSimplify[poly2-poly]

Diameter

seq=Table[GraphData[{"Andrasfai",n},"Diameter"],{n,10}]

DistanceMatrix

MatrixForm/@Table[GraphData[{"Andrasfai",n},"DistanceMatrix"],{n,10}]

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

DistancePolynomial

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

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

FullSimplify[poly2-poly]

DistinguishingNumber

seq=Table[GraphData[{"Andrasfai",n},"DistinguishingNumber"],{n,10}]

DomaticNumber

seq=Table[GraphData[{"Andrasfai",n},"DomaticNumber"],{n,10}]

DominatingSetCount

A285272

seq=Table[GraphData[{"Andrasfai",n},"DominatingSetCount"],{n,10}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,n]

DominationNumber

seq=Table[GraphData[{"Andrasfai",n},"DominationNumber"],{n,10}]

DominationPolynomial

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

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

FullSimplify[poly2-poly]

EdgeChromaticNumber

seq=Table[GraphData[{"Andrasfai",n},"EdgeChromaticNumber"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

gf=x FindGeneratingFunction[seq,x]

EdgeConnectivity

Table[GraphData[{"Andrasfai",n},"EdgeConnectivity"],{n,10}]

EdgeCount

seq=Table[GraphData[{"Andrasfai",n},"EdgeCount"],{n,10}]

FindSequenceFunction[seq,n]

EdgeCoverCount

seq=Table[GraphData[{"Andrasfai",n},"EdgeCoverCount"],{n,10}]

EdgeCoverNumber

seq=Table[GraphData[{"Andrasfai",n},"EdgeCoverNumber"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

x FindGeneratingFunction[seq,x]

EdgeCoverPolynomial

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

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

FullSimplify[poly2-poly]

EulerianCycleCount

seq=Table[GraphData[{"Andrasfai",n},"EulerianCycleCount"],{n,10}]

FaceCount

seq=Table[GraphData[{"Andrasfai",n},"FaceCount"],{n,10}]

FlowPolynomial

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

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

FullSimplify[poly2-poly]

FractionalChromaticNumber

seq=Table[GraphData[{"Andrasfai",n},"FractionalChromaticNumber"],{n,10}]

FindSequenceFunction[seq,n]

FractionalEdgeChromaticNumber

seq=Table[GraphData[{"Andrasfai",n},"FractionalEdgeChromaticNumber"],{n,10}]

FindSequenceFunction[DeleteMissing[seq],n]

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

Table[n(6n-1),{n,10}]

Table[3n-1,{n,10}]

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

Probable:

Table[Piecewise[{{((n (3 n-1))/(3 n-2)),Mod[n,2]==0},{n,Mod[n,2]==1}}],{n,10}]

Girth

seq=Table[GraphData[{"Andrasfai",n},"Girth"],{n,10}]

Gonality

seq=Table[GraphData[{"Andrasfai",n},"Gonality"],{n,10}]

HamiltonConnected

seq=Table[GraphData[{"Andrasfai",n},"HamiltonConnected"],{n,10}]

HamiltonDecompositionCount

seq=Table[GraphData[{"Andrasfai",n},"HamiltonDecompositionCount"],{n,10}]

Hamiltonian

Table[GraphData[{"Andrasfai",n},"Hamiltonian"],{n,10}]

HamiltonianCycleCount

A143249(n)/2

seq=Table[GraphData[{"Andrasfai",n},"HamiltonianCycleCount"],{n,10}]

2seq

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

HamiltonianNumber

seq=Table[GraphData[{"Andrasfai",n},"HamiltonianNumber"],{n,10}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

HamiltonianPathCount

A137884(n)/2

seq=Table[GraphData[{"Andrasfai",n},"HamiltonianPathCount"],{n,10}]

2seq

HamiltonianWalkCount

seq=Table[GraphData[{"Andrasfai",n},"HamiltonianWalkCount"],{n,10}]

HararyIndex

seq=Table[GraphData[{"Andrasfai",n},"HararyIndex"],{n,10}]

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

HexagonCount

seq=Table[GraphData[{"Andrasfai",n},"HexagonCount"],{n,10}]

FindSequenceFunction[seq,n]//Factor

IdiosyncraticPolynomial

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

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

FullSimplify[poly2-poly]

IndependenceNumber

seq=Table[GraphData[{"Andrasfai",n},"IndependenceNumber"],{n,10}]

FindSequenceFunction[seq,n]

IndependencePolynomial

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

CoefficientList[Take[poly,5],x]

coef=Factor/@FindLinearRecurrence[poly]

p=.

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]

IndependenceRatio

seq=Table[GraphData[{"Andrasfai",n},"IndependenceRatio"],{n,10}]

FindSequenceFunction[seq,n]

IndependentEdgeSetCount

A292428

seq=Table[GraphData[{"Andrasfai",n},"IndependentEdgeSetCount"],{n,10}]

FindLinearRecurrence[DeleteMissing[seq]]

FindSequenceFunction[DeleteMissing[seq],n]

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

IndependentVertexSetCount

A288038

seq=Table[GraphData[{"Andrasfai",n},"IndependentVertexSetCount"],{n,10}]

FindLinearRecurrence[DeleteMissing[seq]]

LinearRecurrence[{5,-8,4},{3,11,33},20]

FindSequenceFunction[DeleteMissing[seq],n]//FullSimplify

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

gf=x FindGeneratingFunction[seq,x]

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

IntersectionNumber

seq=Table[GraphData[{"Andrasfai",n},"IntersectionNumber"],{n,10}]

IrredundancePolynomial

(poly=DeleteMissing@Table[GraphData[{"Andrasfai",n},"IrredundancePolynomial"],{n,10}]/.f_Function:>f[x])//Column

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindLinearRecurrence[Rest@poly]

IrredundantSetCount

A290587

seq=Table[GraphData[{"Andrasfai",n},"IrredundantSetCount"],{n,10}]

seq={3,16,81,265,729,1786,4060,8833,18786,39586,83273,175463,370615,784290,1661122,3517669,7441936,15720066,33145015,69744491};

FindLinearRecurrence[DeleteMissing@seq]

coef=FindLinearRecurrence[DeleteMissing@Drop[seq,3]]

Take[Drop[seq,3],Length@coef]

seq=Join[{3,16,81},LinearRecurrence[{10,-43,104,-155,146,-85,28,-4},{265,729,1786,4060,8833,18786,39586,83273},50]]

gf=Factor[3x+16(x^2)+81(x^3)+(x^4) FindGeneratingFunction[Drop[seq,3],x]]

Series[-((x (-3+14 x-50 (x^2)+169 (x^3)-363 (x^4)+491 (x^5)-461 (x^6)+260 (x^7)-46 (x^8)-22 (x^9)+8 (x^10)))/((((-1+x))^6) (((-1+2 x))^2))),{x,0,20}]

CoefficientList[Series[-((-3+14 x-50 (x^2)+169 (x^3)-363 (x^4)+491 (x^5)-461 (x^6)+260 (x^7)-46 (x^8)-22 (x^9)+8 (x^10))/((((-1+x))^6) (((-1+2 x))^2))),{x,0,20}],x]

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

Factor[(1/120) (-45 (8+3 (2^n))+(1772+405 (2^n)) n-1010 (n^2)+25 (n^3)+50 (n^4)+3 (n^5))]

Table[Piecewise[{{3,n==1},{16,n==2},{81,n==3}},(-45 (8+3 (2^n))+(1772+405 (2^n)) n-1010 (n^2)+25 (n^3)+50 (n^4)+3 (n^5))/120],{n,20}]

KirchhoffIndex

seq=Table[GraphData[{"Andrasfai",n},"KirchhoffIndex"],{n,10}]

seq=Table[KirchhoffIndex[AndrasfaiGraph[n]],{n,15}]

FindSequenceFunction[seq,n]

KirchhoffSumIndex

seq=Table[GraphData[{"Andrasfai",n},"KirchhoffSumIndex"],{n,10}]

seq=Table[KirchhoffSumIndex[AndrasfaiGraph[n]],{n,15}]

FindSequenceFunction[seq,n]

LaplacianMatrix

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

LaplacianPolynomial

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

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

FullSimplify[poly2-poly]

LeafCount

seq=Table[GraphData[{"Andrasfai",n},"LeafCount"],{n,10}]

LongestCycleCount

Same as HC

seq=Table[GraphData[{"Andrasfai",n},"LongestCycleCount"],{n,10}]

LovaszNumber

seq=Table[GraphData[{"Andrasfai",n},"LovaszNumber"],{n,10}]

MatchingGeneratingPolynomial

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

CoefficientList[Take[poly,5],x]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

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

FullSimplify[poly2-poly]

MatchingNumber

seq=Table[GraphData[{"Andrasfai",n},"MatchingNumber"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

Table[3n-1,{n,10}]

gf=x FindGeneratingFunction[seq,x]

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

MatchingPolynomial

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

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

FullSimplify[poly2-poly]

MaximalCliqueCount

seq=Table[GraphData[{"Andrasfai",n},"MaximalCliqueCount"],{n,10}]

FindSequenceFunction[seq,n]

MaximalIndependentEdgeSetCount

seq=Table[GraphData[{"Andrasfai",n},"MaximalIndependentEdgeSetCount"],{n,10}]

FindLinearRecurrence[DeleteMissing@seq]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

MaximalIndependentVertexSetCount

seq=Table[GraphData[{"Andrasfai",n},"MaximalIndependentVertexSetCount"],{n,10}]

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

MaximalIrredundantSetCount

A291053

seq=Table[GraphData[{"Andrasfai",n},"MaximalIrredundantSetCount"],{n,10}]

seq={2,10,28,88,217,493,989,1794,3016,4785,7256,10612,15067,20869,28303,37694,49410,63865,81522,102896};

coef=FindLinearRecurrence[Drop[seq,3]]

Take[Drop[seq,3],Length@coef]

Join[{2,10,28},LinearRecurrence[{6,-15,20,-15,6,-1},{88,217,493,989,1794,3016},20]]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

CoefficientList[Series[((2-2 x-2 (x^2)+30 (x^3)-61 (x^4)+89 (x^5)-112 (x^6)+77 (x^7)-18 (x^8))/(((-1+x))^6)),{x,0,40}],x]

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

Table[Piecewise[{{2,n==1},{10,n==2},{28,n==3}},(-3120+10932 n-4970 (n^2)+765 (n^3)-10 (n^4)+3 (n^5))/120],{n,20}]

MaximumCliqueCount

seq=Table[GraphData[{"Andrasfai",n},"MaximumCliqueCount"],{n,10}]

FindSequenceFunction[seq,n]

MaximumIndependentEdgeSetCount

seq=Table[GraphData[{"Andrasfai",n},"MaximumIndependentEdgeSetCount"],{n,10}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

MaximumIndependentVertexSetCount

seq=Table[GraphData[{"Andrasfai",n},"MaximumIndependentVertexSetCount"],{n,10}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

MaximumIrredundantSetCount

seq=Table[GraphData[{"Andrasfai",n},"MaximumIrredundantSetCount"],{n,10}]

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

Table[Piecewise[{{2,n==1},{10,n==2},{4,n==3},{55,n==4}},6n-2],{n,10}]

MaximumLeafNumber

seq=Table[GraphData[{"Andrasfai",n},"MaximumLeafNumber"],{n,10}]

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

MaximumVertexDegree

seq=Table[GraphData[{"Andrasfai",n},"MaximumVertexDegree"],{n,10}]

MeanDistance

seq=Table[GraphData[{"Andrasfai",n},"MeanDistance"],{n,10}]

FindSequenceFunction[seq,n]

MinimalDominatingSetCount

A286879

seq=Table[GraphData[{"Andrasfai",n},"MinimalDominatingSetCount"],{n,10}]

seq={2,5,28,66,140,272,489,828,1339,2088,31|60,4662,6726,9512,13211,18048,24285,32224,42210,54634};

FindLinearRecurrence[Drop[DeleteMissing@seq,3]]

Join[{2,5,28},LinearRecurrence[{6,-15,20,-15,6,-1},{66,140,272,489,828,1339},20]]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

Series[((x (2-7 x+28 (x^2)-67 (x^3)+94 (x^4)-75 (x^5)+29 (x^6)+(x^7)-2 (x^8)))/(((-1+x))^6)),{x,0,20}]

seq=CoefficientList[Series[((2-7 x+28 (x^2)-67 (x^3)+94 (x^4)-75 (x^5)+29 (x^6)+(x^7)-2 (x^8))/(((-1+x))^6)),{x,0,100}],x]

FindLinearRecurrence[DeleteMissing@Drop[seq,3]]

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

Factor[(1/120) (-960+3452 n-1880 (n^2)+505 (n^3)-40 (n^4)+3 (n^5))]

Table[Piecewise[{{2,n==1},{5,n==2},{28,n==3}},(3n-1)((n^4)-13(n^3)+164(n^2)-572n+960)/120],{n,20}]

MinimalEdgeCoverCount

A290702

seq=Table[GraphData[{"Andrasfai",n},"MinimalEdgeCoverCount"],{n,10}]

Table[GraphData[{"Andrasfai",n},"EdgeCoverCount"],{n,10}]

FindLinearRecurrence[DeleteMissing@seq]

FindLinearRecurrence[Drop[DeleteMissing@seq,1]]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

MinimumCliqueCoveringCount

seq=Table[GraphData[{"Andrasfai",n},"MinimumCliqueCoveringCount"],{n,10}]

MinimumConnectedDominatingSetCount

seq=Table[GraphData[{"Andrasfai",n},"MinimumConnectedDominatingSetCount"],{n,10}]

FindSequenceFunction[DeleteMissing[seq],n]

MinimumDominatingSetCount

seq=Table[GraphData[{"Andrasfai",n},"MinimumDominatingSetCount"],{n,10}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

MinimumEdgeCoverCount

seq=Table[GraphData[{"Andrasfai",n},"MinimumEdgeCoverCount"],{n,10}]

MinimumVertexDegree

seq=Table[GraphData[{"Andrasfai",n},"MinimumVertexDegree"],{n,10}]

MolecularTopologicalIndex

A192790

seq=Table[GraphData[{"Andrasfai",n},"MolecularTopologicalIndex"],{n,10}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]//Factor

FindGeneratingFunction[seq,x]//Factor

Nonhamiltonian

Table[GraphData[{"Andrasfai",n},"Nonhamiltonian"],{n,10}]

NormalizedLaplacianMatrix

MatrixForm/@Table[GraphData[{"Andrasfai",n},"NormalizedLaplacianMatrix"],{n,10}]

OddChordlessCycleCount

A301771

seq=Table[GraphData[{"Andrasfai",n},"OddChordlessCycleCount"],{n,10}]

FindSequenceFunction[Rest@DeleteMissing@seq,n]//Simplify

FindLinearRecurrence[seq]

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

gf/x

seq=CoefficientList[Series[((x-3 (x^3)+4 (x^4)+(x^5))/(((-1+x))^8)),{x,0,40}],x]

FindLinearRecurrence[seq]

SeriesCoefficient[((x-3 (x^3)+4 (x^4)+(x^5))/(((-1+x))^8)),{x,0,n}]

PathCount

A288034

seq=Table[GraphData[{"Andrasfai",n},"PathCount"],{n,10}]

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

PathPolynomial

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

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

FullSimplify[poly2-poly]

PentagonCount

seq=Table[GraphData[{"Andrasfai",n},"PentagonCount"],{n,10}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]//Factor

Perfect

Table[GraphData[{"Andrasfai",n},"Perfect"],{n,10}]

ProjectivePlaneCrossingNumber

seq=Table[GraphData[{"Andrasfai",n},"ProjectivePlaneCrossingNumber"],{n,10}]

Radius

seq=Table[GraphData[{"Andrasfai",n},"Radius"],{n,10}]

RankPolynomial

(poly=Factor[Table[GraphData[{"Andrasfai",n},"RankPolynomial"],{n,k0=1,kmax=10}]/.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]

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

FullSimplify[poly2-poly]

RectilinearCrossingNumber

seq=Table[GraphData[{"Andrasfai",n},"RectilinearCrossingNumber"],{n,10}]

ReliabilityPolynomial

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

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

FullSimplify[poly2-poly]

SigmaPolynomial

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

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

FullSimplify[poly2-poly]

SpanningTreeCount

A193126

seq=Table[GraphData[{"Andrasfai",n},"SpanningTreeCount"],{n,10}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

SquareCount

seq=Table[GraphData[{"Andrasfai",n},"SquareCount"],{n,10}]

FindSequenceFunction[seq,n]//Factor

StabilityIndex

seq=Table[GraphData[{"Andrasfai",n},"StabilityIndex"],{n,10}]

FindSequenceFunction[Rest@seq,n-1]

gf=x FindGeneratingFunction[seq,x]

TopologicalIndex

seq=Table[GraphData[{"Andrasfai",n},"TopologicalIndex"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

ToroidalCrossingNumber

seq=Table[GraphData[{"Andrasfai",n},"ToroidalCrossingNumber"],{n,10}]

Traceable

Table[GraphData[{"Andrasfai",n},"Traceable"],{n,10}]

TriangleCount

seq=Table[GraphData[{"Andrasfai",n},"TriangleCount"],{n,10}]

TuttePolynomial

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

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

FullSimplify[poly2-poly]

Untraceable

Table[GraphData[{"Andrasfai",n},"Untraceable"],{n,10}]

VertexConnectivity

Table[GraphData[{"Andrasfai",n},"VertexConnectivity"],{n,10}]

VertexCount

seq=Table[GraphData[{"Andrasfai",n},"VertexCount"],{n,10}]

FindSequenceFunction[seq,n]

VertexCoverNumber

vertex cover number == vertex count - independence number

seq=Table[GraphData[{"Andrasfai",n},"VertexCoverNumber"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

VertexCoverPolynomial

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

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

FullSimplify[poly2-poly]

VertexDegrees

seq=Table[GraphData[{"Andrasfai",n},"VertexDegrees"],{n,10}]

VertexTransitive

Table[GraphData[{"Andrasfai",n},"VertexTransitive"],{n,10}]

WienerIndex

A292018

seq=Table[GraphData[{"Andrasfai",n},"WienerIndex"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

seq=Table[(5n-4)(3n-1)/2,{n,50}]

FindLinearRecurrence[seq]

LinearRecurrence[{3,-3,1},{1,15,44},20]

gf=x FindGeneratingFunction[seq,x]

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

WienerSumIndex

seq=Table[GraphData[{"Andrasfai",n},"WienerSumIndex"],{n,10}]

FindSequenceFunction[seq,n]

GraphData

GraphDataClassString

GraphDataClassString["Andrasfai"]

GraphDataString

file=OpenAppend["~/andrasfai.m"]

Do[WriteString[file,GraphDataString[AndrasfaiGraph[n],
"Name"->ToString[n]<>"\[Hyphen]Andrasfai graph",
"StandardName"->{"Andrasfai",n},
"Classes"->{"Andrasfai","Cayley","Circulant"},
"NotationRules"->{
"Andrasfai"->n
},
"Information"->"AndrasfaiGraph",
"Skip"->{"ABCEnergy","Arboricity","ArithmeticGeometricEnergy","ArithmeticGeometricSpectralRadius","BetweennessCentralities","CharacteristicPolynomial","Circumference","CliqueCoveringNumber","ConnectedDominatingSets","ConstructionNumber","ConnectedInducedSubgraphPolynomial","ConnectedIndicedSubgraphs","Curvatures","CyclePolynomial","CyclicEdgeConnectivity","DetourMatrix","EigenvectorCentralities","Embeddings3D","Energy","Genus","GracefulLabeling","HadwigerNumber","HamiltonianPaths","HamiltonianWalk","HamiltonianWalks","HITSCentralities","IdiosyncraticPolynomial","IndependencePolynomial","LinklesslyEmbeddable","MatchingGeneratingPolynomial","MaximalIndependentEdgeSets","MaximalIndependentVertexSet","MaximalIndependentVertexSets","MaximumIndependentEdgeSetCount","MaximumIndependentEdgeSets","MaximumIndependentVertexSet","MaximumIndependentVertexSetCount","MaximumIndependentVertexSets","MaximumIrredundantSets","MetricDimension","Meyniel","MinimumCyclicEdgeCut","MinimumCyclicEdgeCuts","MinimumEdgeCuts","MinimumWeightFractionalEdgeColoring","MinimumWeightFractionalColoring","Minors","Outerplanar","PageRankCentralities","PathCoveringNumber","PathPolynomial","Paths","ProjectivePlanar","QuadraticEmbeddingConstant","RandicEnergy","RandicSpectralRadius","RectilinearCrossingCount","Skewness","SomborEnergy","SomborSpectralRadius","TotalDominationPolynomial","TuttePolynomial"},
Debug->True,
TimeConstraint->10
]],{n,18,20}]

Close[file]