Hamilton-Connected Graph

Author

Eric W. Weisstein
March 13, 2016

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Hamilton-ConnectedGraph.nb.

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

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

Figure

Graph[g={"Wheel",5}]//ShowGraph

hp=GraphData[g,"HamiltonianPaths"];

st=SplitBy[Sort[{Sort[#[[{1,-1}]]],#}&/@hp],First][[All,1]][[All,2]]

edges=GraphData[g,"EdgeIndices"]

st=SplitBy[Select[Sort[{Sort[#[[{1,-1}]]],#}&/@hp],MemberQ[edges,First[#]]&],First][[All,1]][[All,2]]

#[[{1,-1}]]&/@st

edges

GraphicsGrid[Partition[SetProperty[GraphData[g],
{
System`VertexStyle->{Black,#[[1]]->Red,#[[-1]]->Red},
System`VertexSize->{Medium},
System`EdgeStyle->Prepend[Thread[UndirectedEdge@@@Partition[#,2,1]->Directive[Thick,Red]],Gray]
}
]&/@st,4,4,{1,1}]]

Counts

?HamiltonConnectedQ

Table[ConnectedGraphs[n],{n,8}];//AbsoluteTiming

Parallel "FindPath"

SetDirectory[FileNameJoin[{$GraphDataDirectory,"Nodes","HamiltonConnected"}]]

DistributeDefinitions[HamiltonConnectedQ];

Table[Count[ParallelMap[HamiltonConnectedQ,Graphs[n]],True],{n,7}]//AbsoluteTiming

Serial "FindPath"

Table[Count[ConnectedGraphs[n],_?(HamiltonConnectedQ[#,Method->Automatic]&)],{n,7}]//AbsoluteTiming

Table[Count[ConnectedGraphs[n],_?(HamiltonConnectedQ[#,Method->"FindPath"]&)],{n,7}]//AbsoluteTiming

Serial "FindHamiltonianPath"

Table[Count[ConnectedGraphs[n],_?(HamiltonConnectedQ[#,Method->"FindHamiltonianPath"]&)],{n,7}]//AbsoluteTiming

Serial "MyFindHamiltonianPath"

Table[Count[ConnectedGraphs[n],_?(HamiltonConnectedQ[#,Method->"MyFindHamiltonianPath"]&)],{n,7}]//AbsoluteTiming

7

Parallel FindPath

Count[p=ParallelMap[HamiltonConnectedQ,Graphs[7]],True]//AbsoluteTiming

Serial "FindPath"

Count[ConnectedGraphs[7],_?(HamiltonConnectedQ[#,Method->"FindPath"]&)]//AbsoluteTiming

Count[ConnectedGraphs[7],_?(HamiltonConnectedQ[#,Method->"FindPath","Preprocess"->True]&)]//AbsoluteTiming

Serial "FindHamiltonianPath"

Count[ConnectedGraphs[7],_?HamiltonConnectedQ]//AbsoluteTiming

Count[HamiltonConnectedQ/@ConnectedGraphs[7],True]//AbsoluteTiming

Serial "MyFindHamiltonianPath"

Count[ConnectedGraphs[7],_?(HamiltonConnectedQ[#,Method->"MyFindHamiltonianPath"]&)]//AbsoluteTiming

8

Parallel FindPath

Count[p=ParallelMap[HamiltonConnectedQ,Graphs[8]],True]//AbsoluteTiming

Put[p,"HamiltonConnected_8.m"]

Serial "FindPath"

Count[ConnectedGraphs[8],_?(HamiltonConnectedQ[#,Method->"FindPath"]&)]//AbsoluteTiming

Count[ConnectedGraphs[8],_?(HamiltonConnectedQ[#,Method->"FindPath","Preprocess"->True]&)]//AbsoluteTiming

Serial "FindHamiltonianPath"

Count[ConnectedGraphs[8],_?(HamiltonConnectedQ[#,Method->"FindHamiltonianPath","Preprocess"->True]&)]//AbsoluteTiming

...wrong...

Serial "MyFindHamiltonianPath"

Count[ConnectedGraphs[8],_?(HamiltonConnectedQ[#,Method->"MyFindHamiltonianPath","Preprocess"->True]&)]//AbsoluteTiming

9

Count[p=ParallelMap[HamiltonConnectedQ,Graphs[9]],True]//AbsoluteTiming

Put[p,"HamiltonConnected_9.m"]

10

Count[p=ParallelMap[HamiltonConnectedQ,Graphs[10]],True]//AbsoluteTiming

Put[p,"HamiltonConnected_10.m"]

Parametrized families

Alkane

seq=Table[GraphData[{"Alkane",n},"HamiltonConnected"],{n,10}]

FindSequenceFunction[seq,n]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"HamiltonConnected"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"HamiltonConnected"],{n,10}]

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]//FullSimplify

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"HamiltonConnected"],{n,15}]

Antiprism

Entity["Graph",{"Antiprism",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Antiprism",n},"HamiltonConnected"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"HamiltonConnected"],{n,5}]

FindSequenceFunction[seq,n]

Barbell

seq=Table[GraphData[{"Barbell",n},"HamiltonConnected"],{n,3,20}]

FindSequenceFunction[seq,n]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"HamiltonConnected"],{n,10}]

FullSimplify[FindSequenceFunction[Rest@seq,n-1],n∈Integers]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"HamiltonConnected"],{n,10}]

Book

seq=Table[GraphData[{"Book",n},"HamiltonConnected"],{n,20}]

FindSequenceFunction[seq,n]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"HamiltonConnected"],{n,6}]

FindSequenceFunction[seq,n]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"HamiltonConnected"],{n,10}]

Centipede

seq=Table[GraphData[{"Centipede",n},"HamiltonConnected"],{n,10}]

FindSequenceFunction[seq,n]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"HamiltonConnected"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Complete",n},"HamiltonConnected"],{n,30}]

FindSequenceFunction[seq,n]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["HamiltonConnected"]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["HamiltonConnected"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"HamiltonConnected"],{n,20}]

FindSequenceFunction[seq,n]//FullSimplify

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["HamiltonConnected"]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["HamiltonConnected"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"HamiltonConnected"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"HamiltonConnected"],{n,2,10}]

FindSequenceFunction[seq,n-1]//Factor

Crown

seq=Table[GraphData[{"Crown",n},"HamiltonConnected"],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["HamiltonConnected"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"HamiltonConnected"],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Cycle",n},"HamiltonConnected"],{n,3,30}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"HamiltonConnected"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"HamiltonConnected"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"HamiltonConnected"],{n,3,20}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"HamiltonConnected"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Empty",n},"HamiltonConnected"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"HamiltonConnected"],{n,15}]

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

Flower

seq=Table[GraphData[{"Flower",n},"HamiltonConnected"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"HamiltonConnected"],{n,2,10}]

FindSequenceFunction[seq,n]

Gear

seq=Table[GraphData[{"Gear",n},"HamiltonConnected"],{n,3,20}]

FindSequenceFunction[seq,n]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"HamiltonConnected"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"HamiltonConnected"],{n,2,10}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["HamiltonConnected"]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["HamiltonConnected"]

seq=Table[GraphData[{"Grid",{n,n}},"HamiltonConnected"],{n,20}]

FindSequenceFunction[seq,n]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["HamiltonConnected"]

Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"HamiltonConnected"],
(((k+m+n) (k m n-1))/(3 k m n))
},{n,5},{m,n},{k,m}],2]

Tally[GraphData[{"Grid",{2,3,4}},"DistanceMatrix"]//Normal//Flatten]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["HamiltonConnected"]

seq=Table[GraphData[{"Grid",{n,n,n}},"HamiltonConnected"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"HamiltonConnected"],{n,10}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

Hanoi

seq=Table[GraphData[{"Hanoi",n},"HamiltonConnected"],{n,5}]

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

FindSequenceFunction[Rest@seq,n-1]//Head//Timing

Helm

seq=Table[GraphData[{"Helm",n},"HamiltonConnected"],{n,3,20}]

FindSequenceFunction[seq,n]

Hypercube

Entity["Graph",{"Hypercube",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Hypercube",n},"HamiltonConnected"],{n,0,10}]

FindSequenceFunction[seq,n+1]

Keller

Entity["Graph",{"Keller",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Keller",n},"HamiltonConnected"],{n,5}]

FindSequenceFunction[seq,n]

King n×n

seq=Table[GraphData[{"King",{n,n}},"HamiltonConnected"],{n,20}]

FindSequenceFunction[seq,n]//Factor

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["HamiltonConnected"]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["HamiltonConnected"]

seq=Table[GraphData[{"Knight",{n,n}},"HamiltonConnected"],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Ladder",n},"HamiltonConnected"],{n,20}]

FindSequenceFunction[seq,n]//Factor

LadderRung

seq=Table[GraphData[{"LadderRung",n},"HamiltonConnected"],{n,20}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"HamiltonConnected"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["HamiltonConnected"]

seq=Table[GraphData[{"MoebiusLadder",n},"HamiltonConnected"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Mycielski",n},"HamiltonConnected"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Odd",n},"HamiltonConnected"],{n,7}]

FindSequenceFunction[Rest@seq,n-1]//Head//Timing

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

Pan

seq=Table[GraphData[{"Pan",n},"HamiltonConnected"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Path",n},"HamiltonConnected"],{n,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"HamiltonConnected"],{n,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

Prism

Entity["Graph",{"Prism",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Prism",n},"HamiltonConnected"],{n,3,25}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

Queen n×n

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

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]//Factor

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"HamiltonConnected"],{n,20}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]//Factor

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"HamiltonConnected"],{n,10}]

FindSequenceFunction[Drop[seq,2],n-2]//Factor

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"HamiltonConnected"],{n,4}]

FindSequenceFunction[seq,n]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"HamiltonConnected"],{n,5}]

FindSequenceFunction[seq,n]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"HamiltonConnected"],{n,6}]

FindSequenceFunction[seq,n]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"HamiltonConnected"],{n,5}]

FindSequenceFunction[seq,n]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"HamiltonConnected"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"HamiltonConnected"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Star",n},"HamiltonConnected"],{n,25}]

FindSequenceFunction[seq,n]//Factor

Sun

seq=Table[GraphData[{"Sun",n},"HamiltonConnected"],{n,3,20}]

FindSequenceFunction[seq,n-2]//Factor

Sunlet

seq=Table[GraphData[{"Sunlet",n},"HamiltonConnected"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"HamiltonConnected"],{n,3,10}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

Transposition

Entity["Graph",{"Transposition",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Transposition",n},"HamiltonConnected"],{n,6}]

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

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Trapezohedron",n},"HamiltonConnected"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

Triangular

seq=Table[GraphData[{"Triangular",n},"HamiltonConnected"],{n,2,20}]

FindSequenceFunction[seq,n-1]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"HamiltonConnected"],{n,0,10}]

FindSequenceFunction[seq,n+1]//FullSimplify

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"HamiltonConnected"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"HamiltonConnected"],{n,9}]

FindSequenceFunction[seq,n]//Factor

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"HamiltonConnected"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"HamiltonConnected"],{n,10}]

FindSequenceFunction[seq,n]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"HamiltonConnected"],{n,10}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"HamiltonConnected"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"HamiltonConnected"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["HamiltonConnected"]

seq=Table[GraphData[{"Wheel",n},"HamiltonConnected"],{n,4,20}]

FindSequenceFunction[seq,n-3]//FullSimplify

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"HamiltonConnected"],{n,4,20}]

FindSequenceFunction[seq,n-3]//FullSimplify

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"HamiltonConnected"],{n,2,10}]

FullSimplify[FindSequenceFunction[Rest@seq,n-2],n∈Integers]

Factor[%]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"HamiltonConnected"],{n,20}]

Images

V5

Show[GraphicsArray[{
Graphics[showGraph[#,PlotStyles->{PointSize[.1]}]]&/@Select[Graphs[2],HamiltonConnectedQ],
Graphics[showGraph[#,PlotStyles->{PointSize[.1]}]]&/@Select[Graphs[3],HamiltonConnectedQ],
Graphics[showGraph[#,PlotStyles->{PointSize[.1]}]]&/@Select[Graphs[4],HamiltonConnectedQ],
Graphics[showGraph[#,PlotStyles->{PointSize[.1]}]]&/@Select[Graphs[5],HamiltonConnectedQ],
Sequence@@partition[Graphics[showGraph[#,PlotStyles->{PointSize[.1]}]]&/@Select[Graphs[6],HamiltonConnectedQ],7]
}]]

V7

l=Flatten[Partition[#,5,5,{1,1},{}]&/@Table[GraphData["HamiltonConnected",n],{n,6}],1]

GraphicsGrid[Map[GraphPlot[Graph[#],Method->None,PlotLabel->TextCell[GraphData[#,"Name"],PageWidth->400/6,TextAlignment->Center],BaseStyle->{9,Italic}]&,l,{2}],ImageSize->400]

Algorithm (old)

Stan Wagon: 4/2/2013

Input: Graph G

For all pairs A, B of vertices:

Step 1: Add a new vertex v. 
Step 2:  Add new edges vA and vB.
Step 3: Check if this graph is Hamiltonian. If not, Return False; if yes, go to next pair A,B.

Pretty simple....
If the edge AB is already there, no matter: it can be ignored.

HC[g_System`Graph]:=Module[{n=VertexCount[g]},
!((FindHamiltonianCycle[EdgeAdd[VertexAdd[g,n+1],{UndirectedEdge[#[[1]],n+1],UndirectedEdge[#[[2]],n+1]}]]==={})&/@Or@@Developer`ToPackedArray[Subsets[Range[n],{2}]])
]

Select[GraphData[3;;7],HC[GraphData[#]]=!=GraphData[#,"HamiltonConnected"]&]//Timing

HC2[g_System`Graph]:=Module[{n=VertexCount[g],edges=EdgeList[g]},
!((FindHamiltonianCycle[Graph[Range[n+1],Join[edges,{#[[1]]\[UndirectedEdge]n+1,#[[2]]\[UndirectedEdge]n+1}]]]==={})&/@Or@@Developer`ToPackedArray[Subsets[Range[n],{2}]])
]

Select[GraphData[3;;7],HC2[GraphData[#]]=!=GraphData[#,"HamiltonConnected"]&]//Timing

HC3[g_System`Graph]:=Module[{n=VertexCount[g],edges=EdgeList[g]},
If[BipartiteGraphQ[g]||FindHamiltonianCycle[g]==={},Return[False]];
!((FindHamiltonianCycle[Graph[Range[n+1],Join[edges,{#[[1]]\[UndirectedEdge]n+1,#[[2]]\[UndirectedEdge]n+1}]]]==={})&/@Or@@Developer`ToPackedArray[Subsets[Range[n],{2}]])
]

Select[GraphData[3;;7],HC2[GraphData[#]]=!=GraphData[#,"HamiltonConnected"]&]//Timing

Profiling

FindHamiltonianPath seems to get faster than FindPath around n≈60

{"Fullerene",{44,1}}

GraphData[{"Fullerene",{44,1}},"HamiltonConnected"]

HamiltonConnectedQ[GraphData[{"Fullerene",{44,1}}],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{44,1}}],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{44,1}}],Method->"FindPath"]//AbsoluteTiming

{"Fullerene",{46,1}}

GraphData[{"Fullerene",{46,1}},"HamiltonConnected"]

HamiltonConnectedQ[GraphData[{"Fullerene",{46,1}}],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{46,1}}],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{46,1}}],Method->"FindPath"]//AbsoluteTiming

{"Fullerene",{48,1}}

GraphData[{"Fullerene",{48,1}},"HamiltonConnected"]

HamiltonConnectedQ[GraphData[{"Fullerene",{48,1}}],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{48,1}}],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{48,1}}],Method->"FindPath"]//AbsoluteTiming

{"JohnsonSkeleton",80}

DeleteCases[GraphData["HamiltonConnected",50],{"Fullerene",_}]

GraphData[{"JohnsonSkeleton",80},"HamiltonConnected"]

HamiltonConnectedQ[GraphData[{"JohnsonSkeleton",80}],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"JohnsonSkeleton",80}],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"JohnsonSkeleton",80}],Method->"FindPath"]//AbsoluteTiming

{"Fullerene",{50,1}}

GraphData[{"Fullerene",{50,1}},"HamiltonConnected"]

HamiltonConnectedQ[GraphData[{"Fullerene",{50,1}}],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{50,1}}],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{50,1}}],Method->"FindPath"]//AbsoluteTiming

{"Fullerene",{50,100}}

GraphData[{"Fullerene",{50,100}},"HamiltonConnected"]

HamiltonConnectedQ[GraphData[{"Fullerene",{50,100}}],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{50,100}}],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{50,100}}],Method->"FindPath"]//AbsoluteTiming

"Foster050A"

GraphData["Foster050A","HamiltonConnected"]

HamiltonConnectedQ[GraphData["Foster050A"],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData["Foster050A"],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData["Foster050A"],Method->"FindPath"]//AbsoluteTiming

{"Fullerene",{60,1}}

GraphData[{"Fullerene",{60,1}},"HamiltonConnected"]

HamiltonConnectedQ[GraphData[{"Fullerene",{60,1}}],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{60,1}}],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{60,1}}],Method->"FindPath"]//AbsoluteTiming

{"Cubic",{60,1}}

GraphData["HamiltonConnected",60]

GraphData[{"Cubic",{60,1}},"HamiltonConnected"]

HamiltonConnectedQ[GraphData[{"Cubic",{60,1}}],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Cubic",{60,1}}],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Cubic",{60,1}}],Method->"FindPath"]//AbsoluteTiming

{"Fullerene",{70,4085}}

GraphData[{"Fullerene",{70,4085}},"HamiltonConnected"]

HamiltonConnectedQ[GraphData[{"Fullerene",{70,4085}}],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{70,4085}}],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{70,4085}}],Method->"FindPath"]//AbsoluteTiming

{"Fullerene",{80,6877}}

GraphData[{"Fullerene",{80,6877}},"HamiltonConnected"]

HamiltonConnectedQ[GraphData[{"Fullerene",{80,6877}}],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{80,6877}}],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonConnectedQ[GraphData[{"Fullerene",{80,6877}}],Method->"FindPath"]//AbsoluteTiming

Check

FindHamiltonianPath

Monitor[Select[GraphData["Connected",;;10],HamiltonConnectedGraphQ[GraphData[g=#],Method->"FindHamiltonianPath"]=!=GraphData[#,"HamiltonConnected"]&],g]//Timing

MyFindHamiltonianPath

Monitor[Select[GraphData["Connected",;;5],HamiltonConnectedGraphQ[GraphData[g=#],Method->"MyFindHamiltonianPath"]=!=GraphData[#,"HamiltonConnected"]&],g]//Timing

Monitor[Select[GraphData["Connected",;;10],HamiltonConnectedGraphQ[GraphData[g=#],Method->"MyFindHamiltonianPath"]=!=GraphData[#,"HamiltonConnected"]&],g]//Timing

FindPath

Monitor[Select[GraphData["Connected",;;5],HamiltonConnectedGraphQ[GraphData[g=#],Method->"FindPath"]=!=GraphData[#,"HamiltonConnected"]&],g]//Timing

Monitor[Select[GraphData["Connected",;;10],HamiltonConnectedGraphQ[GraphData[g=#],Method->"FindPath"]=!=GraphData[#,"HamiltonConnected"]&],g]//Timing

HamiltonianPaths

Monitor[Select[GraphData["Connected",;;5],HamiltonConnectedGraphQ[GraphData[g=#],Method->"HamiltonianPaths"]=!=GraphData[#,"HamiltonConnected"]&],g]//Timing

Monitor[Select[GraphData["Connected",;;10],HamiltonConnectedGraphQ[GraphData[g=#],Method->"HamiltonianPaths"]=!=GraphData[#,"HamiltonConnected"]&],g]//Timing

VertexAddition

Monitor[Select[GraphData["Connected",;;5],HamiltonConnectedGraphQ[GraphData[g=#],Method->"VertexAddition"]=!=GraphData[#,"HamiltonConnected"]&],g]//Timing

Monitor[Select[GraphData["Connected",;;10],HamiltonConnectedGraphQ[GraphData[g=#],Method->"VertexAddition"]=!=GraphData[#,"HamiltonConnected"]&],g]//Timing

Wagon

Monitor[Select[GraphData["Connected",;;10],HamiltonConnectedGraphQ[GraphData[g=#],Method->"Wagon"]=!=GraphData[#,"HamiltonConnected"]&],g]//Timing

Monitor[Select[GraphData["Connected",;;15],HamiltonConnectedGraphQ[GraphData[g=#],Method->"Wagon"]=!=GraphData[#,"HamiltonConnected"]&],g]//Timing

DetourMatrix

Listed as HamiltonConnected but isn't

Monitor[Select[GraphData["HamiltonConnected"],ListQ[d=GetGraphData[g=#,"DetourMatrix"]]&&d!=With[{n=GraphData[#,"V"]},ConstantArray[n-1,{n,n}]-DiagonalMatrix[ConstantArray[n-1,n]]]&],g]//Timing

Not listed as HamiltonConnected but is

Monitor[Select[Complement[GraphData["Hamiltonian"],GraphData["HamiltonConnected"]],ListQ[d=GetGraphData[g=#,"DetourMatrix"]]&&d==With[{n=GraphData[#,"V"]},ConstantArray[n-1,{n,n}]-DiagonalMatrix[ConstantArray[n-1,n]]]&],g]//Timing