Polyhedral Nonhamiltonian Graph

Author

Eric W. Weisstein
June 17, 2023

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

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

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

Counts

GraphData

Length/@Table[GraphData[{"Nonhamiltonian","Polyhedral"},n],{n,14}]

Polyhedral

A007033

74, 1600, 43984, 1032208, 2296022

Do[Print[{n,{Length[gs=Select[PolyhedralGraphs[n],(!HamiltonianGraphQ[#]&)]],gs}//Timing}],{n,12}]

Length[g11=]

DeleteCases[RecognizeGraph/@g11,{}]

SetDirectory["/Developer/eww/Graphs/Polyhedral/13"]

files=FileNames["*"]

Total[Count[Import[#,"Sparse6"],_?(!HamiltonianGraphQ[#]&)]&/@files]//Timing//AbsoluteTiming

Smallest nonhamiltonian polyhedral

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

TextGrid[{#[[1,1]],Length[gs=#[[All,2]]],DeleteCases[gs,{"NonhamiltonianPolyhedral",_}]}&/@SplitBy[Sort[GraphData[#,{"M","#"}]&/@GraphData[{"Nonhamiltonian","Polyhedral"},11]],First],Dividers->All]

Examples

SortBy[DeleteCases[GraphData[{"Polyhedral","Nonhamiltonian"}],{"CubicNonhamiltonian"|"NonhamiltonianPolyhedral"|"PlanarHypohamiltonian",_}],GraphData[#,"V"]&]