Nonhamiltonian Graph

Author

Eric W. Weisstein
May 3, 2022

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

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

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

Counts

Hamiltonian

A003216

ham={1,0,1,3,8,48,383,6196,177083,9305118,883156024};

Nonhamiltonian

MapIndexed[NumberOfGraphs[#2[[1]]]-#1&,ham]

Connected nonhamiltonian

A126149

con={1,1,1,2,6,21,112,853,11117,261080,11716571,1006700565,164059830476,50335907869219,29003487462848061,31397381142761241960,63969560113225176176277,245871831682084026519528568,1787331725248899088890200576580,24636021429399867655322650759681644};

Take[Rest@con,Length[ham]]-ham

Combinatorica HamiltonianQ

Monitor[ham=Table[HamiltonianQ[Graphs[n][[k]]],{n,9},{k,Length[Graphs[n]]}],{n,k}];//Timing

Count[#,False]&/@ham

HamiltonianGraphQ

Table[
g=Graphs[n];
Print[{n,{c=Count[g,_?HamiltonianGraphQ],Length[g]-c}}//Timing],
{n,10}];

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

Classes that are nonhamiltonian

GraphClassesThatAreClass["Nonhamiltonian"]

GraphClassesThatAreClass["Nonhamiltonian",2;;]

Figure

GraphicsGrid[Flatten[Partition[#,UpTo[7]]&/@Table[StyleGraphs[GraphData[#]&/@GraphData[{"Connected","Nonhamiltonian"},n],VertexSize->{"Scaled",.05}],{n,5}],1],Dividers->{{Thick,{True},Thick},{{Thick,Thick,Thick},True,Thick}},ImageSize->700]

Table

Reverse/@Sort[GraphData[{"Connected","Nonhamiltonian"},{"VertexCount","Name"}]]//TableForm