Cubic Hypohamiltonian Graph

Author

Eric W. Weisstein
April 11, 2024

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

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

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

Counts

A305354

BFileSequence[305354]

Length[%]

Length/@Table[GraphData[{"Cubic","Hypohamiltonian"},2n],{n,16}]

Table

named=DeleteCases[
DeleteCases[Table[{2n,GraphData[{"Cubic","Hypohamiltonian"},2n]},{n,16}],{"Snark"|"CubicHypohamiltonian",_},∞],
{_,{}}]

TextGrid[named,Dividers->All]

Figure

GraphicsGrid[Map[Show[StyleGraphs[GraphData[#]],PlotLabel->Style[TextCell[GraphData[#,"Name"],PageWidth->700/4,TextAlignment->Center],Directive[14,Black,Italic,FontFamily->"Times"]]]&,named[[All,2]],{2}],Dividers->All,ImageSize->700,Alignment->Top]

Embeddings

<<MathWorld`Graphs`

GraphData["CubicHypohamiltonian*"]

24

GraphData[{"Cubic","Hypohamiltonian"},24]

{"CubicHypohamiltonian", {24, 1}} == "ThomassenGraph24"

GraphData[{"CubicHypohamiltonian",{24,1}},"StandardName"]

26

GraphData[{"Cubic","Hypohamiltonian"},26]

Length[%]

{"CubicHypohamiltonian", {26, 1}} == {"Snark", {26, 131}}

GraphData[{"CubicHypohamiltonian",{26,1}},"StandardName"]

{"CubicHypohamiltonian", {26, 2}} == {"Snark", {26, 140}}

GraphData[{"CubicHypohamiltonian",{26,2}},"StandardName"]

{"CubicHypohamiltonian", {26, 3}} == {"Snark", {26, 5}}

GraphData[{"CubicHypohamiltonian",{26,3}},"StandardName"]

{"CubicHypohamiltonian", {26, 4}} == {"Snark", {26, 13}}

GraphData[{"CubicHypohamiltonian",{26,4}},"StandardName"]

{"CubicHypohamiltonian", {26, 5}} == {"Snark", {26, 48}}

GraphData[{"CubicHypohamiltonian",{26,5}},"StandardName"]

{"CubicHypohamiltonian", {26, 6}} == {"Snark", {26, 133}}

GraphData[{"CubicHypohamiltonian",{26,6}},"StandardName"]

{"CubicHypohamiltonian", {26, 7}}

GraphData[{"CubicHypohamiltonian",{26,7}},"StandardName"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicHypohamiltonian",{26,7}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicHypohamiltonian",{26,7}},"Edges"]

v={};
g=Graph[Range[Length[v]],Sort[Sort/@(UndirectedEdge@@@{Sequence@@curvededges={}})],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicHypohamiltonian",{26,7}},"Graph","Degenerate"]

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"CubicHypohamiltonian",{26,7}}],All][[All,All,1]]]

Planar

GraphData[{"CubicHypohamiltonian",{26,7}},"Planar"]

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

MinimalCrossing

GraphData[{"CubicHypohamiltonian",{26,7}},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

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

GraphPlot@RotateGraph[,-Pi/2]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicHypohamiltonian",{26,7}},"Circulant"]

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

Halin

GraphData[{"CubicHypohamiltonian",{26,7}},"Halin"]

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

Rigid

GraphData[{"CubicHypohamiltonian",{26,7}},"Rigid"]

GraphData[{"CubicHypohamiltonian",{26,7}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicHypohamiltonian",{26,7}},"Flexible"]

GraphData[{"CubicHypohamiltonian",{26,7}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicHypohamiltonian",{26,7}},"LCF"]

GraphData[{"CubicHypohamiltonian",{26,7}},"HamiltonianCycleCount"]

GraphData[{"CubicHypohamiltonian",{26,7}},"LCFSignature"]

GraphData[{"CubicHypohamiltonian",{26,7}},"LCFNotations"]

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

UnitDistance

GraphData[{"CubicHypohamiltonian",{26,7}},"UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"CubicHypohamiltonian",{26,7}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicHypohamiltonian",{26,7}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicHypohamiltonian",{26,7}}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicHypohamiltonian",{26,7}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"CubicHypohamiltonian",{26,7}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"CubicHypohamiltonian",{26,7}},"Polyhedral"]

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

{"CubicHypohamiltonian", {26, 8}} == {"Snark", {26, 223}}

GraphData[{"CubicHypohamiltonian",{26,8}},"StandardName"]

{"CubicHypohamiltonian", {26, 9}} == {"Snark", {26, 22}}

GraphData[{"CubicHypohamiltonian",{26,9}},"StandardName"]

{"CubicHypohamiltonian", {26, 10}} == {"Snark", {26, 7}}

GraphData[{"CubicHypohamiltonian",{26,10}},"StandardName"]

{"CubicHypohamiltonian", {26, 11}} == {"Snark", {26, 3}}

GraphData[{"CubicHypohamiltonian",{26,11}},"StandardName"]

{"CubicHypohamiltonian", {26, 12}} == {"Snark", {26, 23}}

GraphData[{"CubicHypohamiltonian",{26,12}},"StandardName"]

{"CubicHypohamiltonian", {26, 13}} == {"Snark", {26, 152}}

GraphData[{"CubicHypohamiltonian",{26,13}},"StandardName"]

{"CubicHypohamiltonian", {26, 14}} == {"Snark", {26, 15}}

GraphData[{"CubicHypohamiltonian",{26,14}},"StandardName"]

{"CubicHypohamiltonian", {26, 15}} == {"Snark", {26, 12}}

GraphData[{"CubicHypohamiltonian",{26,15}},"StandardName"]

{"CubicHypohamiltonian", {26, 16}} == {"Snark", {26, 4}}

GraphData[{"CubicHypohamiltonian",{26,16}},"StandardName"]

{"CubicHypohamiltonian", {26, 17}}

GraphData[{"CubicHypohamiltonian",{26,17}},"StandardName"]

Primary

GraphData[{"CubicHypohamiltonian",{26,17}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicHypohamiltonian",{26,17}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicHypohamiltonian",{26,17}},"Edges"]

v={};
g=Graph[Range[Length[v]],Sort[Sort/@(UndirectedEdge@@@{Sequence@@curvededges={}})],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

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

Degenerate

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","Degenerate"]

Bilateral

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicHypohamiltonian",{26,17}},"Planar"]

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicHypohamiltonian",{26,17}},{"RCN","CN"}]

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CubicHypohamiltonian",{26,17}}],TimeConstraint->1])//AbsoluteTiming

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicHypohamiltonian",{26,17}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@RotateGraph[HighlightGraph[GraphicsToGraph@,{27,28,29,30}],{11,5}]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicHypohamiltonian",{26,17}},"Circulant"]

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CubicHypohamiltonian",{26,17}},"Halin"]

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicHypohamiltonian",{26,17}},"Rigid"]

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicHypohamiltonian",{26,17}},"Flexible"]

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicHypohamiltonian",{26,17}},"LCF"]

GraphData[{"CubicHypohamiltonian",{26,17}},"HamiltonianCycleCount"]

GraphData[{"CubicHypohamiltonian",{26,17}},"LCFSignature"]

GraphData[{"CubicHypohamiltonian",{26,17}},"LCFNotations"]

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"CubicHypohamiltonian",{26,17}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicHypohamiltonian",{26,17}}],Debug->True]//Timing

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicHypohamiltonian",{26,17}},"VertexList"],GraphData[{"CubicHypohamiltonian",{26,17}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CubicHypohamiltonian",{26,17}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"CubicHypohamiltonian",{26,17}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicHypohamiltonian",{26,17}}],"CrossingNumber"->5]

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"CubicHypohamiltonian",{26,17}},"Matchstick"]

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicHypohamiltonian",{26,17}},"Edges"]]

3D All

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicHypohamiltonian",{26,17}},"Polyhedral"]

GraphData[{"CubicHypohamiltonian",{26,17}},"Graph",{"3D","Polyhedron"}]

{"CubicHypohamiltonian", {26, 18}} == {"Snark", {26,162}}

GraphData[{"CubicHypohamiltonian",{26,18}},"StandardName"]

{"CubicHypohamiltonian", {26, 19}} == {"Snark", {26, 16}}

GraphData[{"CubicHypohamiltonian",{26,19}},"StandardName"]

{"CubicHypohamiltonian", {26, 20}} == {"Snark", {26,134}}

GraphData[{"CubicHypohamiltonian",{26,20}},"StandardName"]

{"CubicHypohamiltonian", {26, 21}} == {"Snark", {26, 129}}

GraphData[{"CubicHypohamiltonian",{26,21}},"StandardName"]

{"CubicHypohamiltonian", {26, 22}} == {"Snark", {26, 136}}

GraphData[{"CubicHypohamiltonian",{26,22}},"StandardName"]

{"CubicHypohamiltonian", {26, 23}} == {"Snark", {26, 125}}

GraphData[{"CubicHypohamiltonian",{26,23}},"StandardName"]

{"CubicHypohamiltonian", {26, 24}} == {"Snark", {26, 249}}

GraphData[{"CubicHypohamiltonian",{26,24}},"StandardName"]

{"CubicHypohamiltonian", {26, 25}} == {"Snark", {26,122}}

GraphData[{"CubicHypohamiltonian",{26,25}},"StandardName"]

{"CubicHypohamiltonian", {26, 26}} == {"Snark", {26, 6}}

GraphData[{"CubicHypohamiltonian",{26,26}},"StandardName"]

{"CubicHypohamiltonian", {26, 27}} == {"Snark", {26, 126}}

GraphData[{"CubicHypohamiltonian",{26,27}},"StandardName"]

{"CubicHypohamiltonian", {26, 28}} == {"Snark", {26, 174}}

GraphData[{"CubicHypohamiltonian",{26,28}},"StandardName"]

{"CubicHypohamiltonian", {26, 29}} == {"Snark", {26, 49}}

GraphData[{"CubicHypohamiltonian",{26,29}},"StandardName"]

{"CubicHypohamiltonian", {26, 30}} == {"Snark", {26, 47}}

GraphData[{"CubicHypohamiltonian",{26,30}},"StandardName"]

{"CubicHypohamiltonian", {26, 31}} == {"Snark", {26, 46}}

GraphData[{"CubicHypohamiltonian",{26,31}},"StandardName"]

{"CubicHypohamiltonian", {26, 32}} == "CelminsSwartSnark1"

GraphData[{"CubicHypohamiltonian",{26,32}},"StandardName"]

{"CubicHypohamiltonian", {26, 33}} == {"Snark", {26, 141}}

GraphData[{"CubicHypohamiltonian",{26,33}},"StandardName"]

{"CubicHypohamiltonian", {26, 34}} == {"Snark", {26, 238}}

GraphData[{"CubicHypohamiltonian",{26,34}},"StandardName"]

{"CubicHypohamiltonian", {26, 35}} == {"Snark", {26, 143}}

GraphData[{"CubicHypohamiltonian",{26,35}},"StandardName"]

{"CubicHypohamiltonian", {26, 36}} == {"Snark", {26, 256}}

GraphData[{"CubicHypohamiltonian",{26,36}},"StandardName"]

{"CubicHypohamiltonian", {26, 37}} == {"Snark", {26, 9}}

GraphData[{"CubicHypohamiltonian",{26,37}},"StandardName"]

{"CubicHypohamiltonian", {26, 38}} == {"Snark", {26, 120}}

GraphData[{"CubicHypohamiltonian",{26,38}},"StandardName"]

{"CubicHypohamiltonian", {26, 39}} == {"Snark", {26, 250}}

GraphData[{"CubicHypohamiltonian",{26,39}},"StandardName"]

{"CubicHypohamiltonian", {26, 40}}

GraphData[{"CubicHypohamiltonian",{26,40}},"StandardName"]

All

GraphData[{"CubicHypohamiltonian",{26,40}},"Graph","All"]//StyleGraphs

Default embedding

g=GraphPlot@GraphData[{"CubicHypohamiltonian",{26,40}},"Edges"]

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

RecognizeGraph[g]

LCF

GraphData[{"CubicHypohamiltonian",{26,40}},"LCFSignature"]

GraphData[{"CubicHypohamiltonian",{26,40}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"CubicHypohamiltonian",{26,40}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance FindSubgraphIsomorphism

l=FindSubgraphIsomorphism[GraphData[{"CubicHypohamiltonian",{26,40}}],"Results"->All]//Timing

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"CubicHypohamiltonian",{26,40}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicHypohamiltonian",{26,40}},{"RCN","CN"}]

GraphData[{"CubicHypohamiltonian",{26,40}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing Construction

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicHypohamiltonian",{26,40}}],"CrossingNumber"->4]

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

Position[%,2]

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"CubicHypohamiltonian", {26, 41}} == {"Snark", {26, 8}}

GraphData[{"CubicHypohamiltonian",{26,41}},"StandardName"]

{"CubicHypohamiltonian", {26, 42}} == {"Snark", {26, 30}}

GraphData[{"CubicHypohamiltonian",{26,42}},"StandardName"]

{"CubicHypohamiltonian", {26, 43}}

GraphData[{"CubicHypohamiltonian",{26,43}},"StandardName"]

All

GraphData[{"CubicHypohamiltonian",{26,43}},"Graph","All"]//StyleGraphs

Default embedding

g=GraphPlot@GraphData[{"CubicHypohamiltonian",{26,43}},"Edges"]

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

RecognizeGraph[g]

LCF

GraphData[{"CubicHypohamiltonian",{26,43}},"LCFSignature"]

GraphData[{"CubicHypohamiltonian",{26,43}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"CubicHypohamiltonian",{26,43}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance FindSubgraphIsomorphism

l=FindSubgraphIsomorphism[GraphData[{"CubicHypohamiltonian",{26,43}}],"Results"->All]//Timing

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"CubicHypohamiltonian",{26,43}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicHypohamiltonian",{26,43}},{"RCN","CN"}]

GraphData[{"CubicHypohamiltonian",{26,43}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicHypohamiltonian",{26,43}}],"CrossingNumber"->4]

GraphPlot[RotateGraph[HighlightGraph[GraphicsToGraph@,{27,28,29,30}],{5,22}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

...

{"CubicHypohamiltonian", {26, 72}}

GraphData[{"CubicHypohamiltonian",{26,72}},"StandardName"]

All

GraphData[{"CubicHypohamiltonian",{26,72}},"Graph","All"]//StyleGraphs

Default embedding

g=GraphPlot@GraphData[{"CubicHypohamiltonian",{26,72}},"Edges"]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

LCF

GraphData[{"CubicHypohamiltonian",{26,72}},"LCFSignature"]

GraphData[{"CubicHypohamiltonian",{26,72}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"CubicHypohamiltonian",{26,72}},"Graph","UnitDistance"]//StyleGraphs

FindUnitDistanceEmbedding[GraphData[{"CubicHypohamiltonian",{26,72}}],MaxIterations->200]

UnitDistance FindSubgraphIsomorphism

l=FindSubgraphIsomorphism[GraphData[{"CubicHypohamiltonian",{26,72}}],"Results"->All]//Timing

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"CubicHypohamiltonian",{26,72}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicHypohamiltonian",{26,72}},{"RCN","CN"}]

GraphData[{"CubicHypohamiltonian",{26,72}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicHypohamiltonian",{26,72}}],"CrossingNumber"->4]

GraphPlot@RotateGraph[HighlightGraph[GraphicsToGraph@,Range[26+1,26+4]],{23,16}]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

28 [52]

GraphData[{"Cubic","Hypohamiltonian"},28]

30 [202]

GraphData[{"Cubic","Hypohamiltonian"},30]

32 [304]

GraphData[{"Cubic","Hypohamiltonian"},32]

GraphData

GraphDataClassString

GraphDataClassString[{"Cubic","Hypohamiltonian"}]