Hamiltonian Cycle

Author

Eric W. Weisstein
December 16, 2023

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

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

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

Totals for n nodes

A124964(n)/2

Table[Total[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","HamiltonianCycleCount","HamiltonianCycleCount_"<>StringPadLeft[ToString[n],2,"0"]<>".m"}]]],{n,10}]

% 2

https://oeis.org/A124964

hc=Table[GraphData[#,"HamiltonianCycleCount"]&/@GraphData[n],{n,7}];

{Total/@hc,Mean/@hc}

Do[Print[{n,Total[Length[System`FindHamiltonianCycle[AdjacencyGraph[#],All]]&/@Graphs[n,"Format"->"AdjacencyMatrix"]]//Timing}],{n,10}]

Do[Print[{n,Total[FindHamiltonianCycleCount[AdjacencyGraph[#]]&/@Graphs[n,"Format"->"AdjacencyMatrix"]]//Timing}],{n,8}]

l={{1,{0.001999000000000084`,0}},{2,{0.10698399999999997`,0}},{3,{0.022996999999999934`,1}},{4,{0.024996000000000018`,5}},{5,{0.028996000000000022`,29}},{6,{0.06199100000000013`,308}},{7,{0.30595399999999984`,4966}},{8,{4.138371000000001`,166693}},{9,{113.890686`,12576966}},{10,{10621.698257`,2274288844}}}[[All,2,2]]2

Platonics

This needs to be rewritten for Combinatorica 2

HamiltonianGraphPlot[g_Graph,Arrows]:=Module[{c=HamiltonianCycle[g]},
Graphics[{
showGraph[g,PlotStyles->{PointSize[.05]}][[1]],
{RGBColor[1,0,0],Thickness[.02],(Arrow[Sequence@@Vertices[g][[#]],HeadWidth->.7,HeadLength->.07])&/@Partition[c,2,1]}
},AspectRatio->Automatic,PlotRange->All]
]

HamiltonianGraphPlot[g_Graph,opts___]:=Module[{c=HamiltonianCycle[g]},
ShowGraph[
Highlight[g,List/@Partition[c,2,1,1],HighlightedEdgeColors->{Red},
HighlightedEdgeStyle->Thick],opts,
VertexColor->{Black},
VertexStyle->Disk[.07],
AspectRatio->Automatic
]/.Thickness[.02]:>Thickness[.035]
]

Show[GraphicsArray[
Block[{$DisplayFunction=Identity},
HamiltonianGraphPlot/@PlatonicGraphs
]
],ImageSize->500]

Parametrized family table

GraphDataCountTable["HamiltonianCycleCount",{"Alkane"->000004,"Andrasfai"->307902,"Antiprism"->306447,"Barbell"->000004,"Bishop"->000004,"BlackBishop"->307920,"Camel"->000004,"Centipede"->000007,"CocktailParty"->307923,"Complete"->001710,"CompleteBipartite"->010796,{"CompleteTripartite",3}->307924,"CrossedPrism"->007283,"Crown"->306496,"Cycle"->000012,"CycleComplement"->002816,"DiagonalIntersection"->300513,"Dipyramid"->054000,"Empty"->000007,"FoldedCube"->307925,"Gear"->000004,{"Grid",2}->003763,"HalvedCube"->307926,"Hanoi"->000012,"Helm"->000004,"Hypercube"->066037,"King"->140519,"Knight"->001230,"Ladder"->057427,"LadderRung"->000004,"LucasCube"->000004,"MengerSponge"->000004,,"MoebiusLadder"->103889,"Mycielski"->307927,"Odd"->301557,"Pan"->000007,"Path"->000004,"PathComplement"->242522,"Prism"->103889,"Queen"->307928,"Rook"->269561,"RookComplement"->291865,"SierpinskiGasket"->246959,"Star"->000004,"Sun"->000012,"Sunlet"->000004,"TorusGrid"->222199,"Transposition"->307896,"Triangular"->307930,"TriangularGrid"->112676,"TriangularHoneycombAcuteKnight"->000004,"TriangularHoneycombBishop"->307931,"TriangularHoneycombQueen"->289703,"TriangularHoneycombRook"->000004,"TriangularSnake"->063524,"Web"->000004,"Wheel"->000027,"WheelComplement"->000004,"WhiteBishop"->307929}]

Parametrized families

<<MathWorld`Graphs`

AlternatingGroupGraph

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

Andrasfai

A307902

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

FindSequenceFunction[seq,n]

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

Antelope n×n

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

Antiprism

A306447

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

Table[2 n+RootSum[-1-2 #1-((#1)^2)+((#1)^3)&,((#1)^n)&],{n,40}]

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

FindSequenceFunction[seq,n-2]

FindLinearRecurrence[seq]

seq=LinearRecurrence[{3,-1,-2,0,1},{3,9,16,29,56},20]

gf=x FindGeneratingFunction[seq,x]

Series[gf,{x,0,10}]

FullSimplify[SeriesCoefficient[((x(-3+8 (x^2)+4 (x^3)-3 (x^4)))/((((-1+x))^2) (-1+x+2 (x^2)+(x^3)))),{x,0,n}],n>0]

Apollonian

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

BlackBishop n×n

A282889

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

FindSequenceFunction[DeleteMissing@Drop[seq,3],n]

gf=(x^k0)FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

coef=FindLinearRecurrence[seq]

coef=FindPolynomialRecurrence[seq,Floor[Length[seq/2]]]

LinearRecurrence[coef,seq,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[a[k+k0-1]==seq[[k]],{k,Length[coef]}],ToRecurrence[a,x,n,coef]],a[n],n],n∈Integers&&n>0]

CocktailParty

A307923

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

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

FindLinearRecurrence[Rest@seq]//Head//Timing

Factor[(-68-98 \[FormalN]-48 (\[FormalN]^2)-8 (\[FormalN]^3))]

RecurrenceTable[{-4 (1+\[FormalN]) (2+\[FormalN]) (5+2 \[FormalN]) \[FormalY][\[FormalN]]-2 (2+\[FormalN]) (17+16 \[FormalN]+4 (\[FormalN]^2)) \[FormalY][1+\[FormalN]]+(3+2 \[FormalN]) \[FormalY][2+\[FormalN]]==0,\[FormalY][1]==2,\[FormalY][2]==32},\[FormalY][\[FormalN]],{\[FormalN],10}]

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

(* Geoffrey Critzer, Feb 09 2014 *)

Table[Sum[(-1)^i Binomial[n,i](2n-1-i)!2^i/2,{i,0,n}],{n,20}]

Sum[(-1)^i Binomial[n,i](2n-1-i)!2^i,{i,0,n}]

Table[Piecewise[{{0,n==1}},(2 n-1)! Hypergeometric1F1[-n,1-2 n,-2]/2],{n,20}]

Complete

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

seq=Table[GraphData[{"Complete",n},"HamiltonianCycleCount"],{n,20}]

FindSequenceFunction[Drop[seq,2],n]//FullSimplify

FindLinearRecurrence[Drop[seq,2]]

Table[If[n<3,0,(n-1)!],{n,20}]

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{
{m,n},
Piecewise[{{n! (n-1)!/2,m>1&&m==n}},0],
GraphData[{"CompleteBipartite",{m,n}},"HamiltonianCycleCount"]},{n,20},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

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

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

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

Table[If[n==1,0,n!(n-1)!],{n,20}]

CompleteTripartite n×n×n

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

A234365

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

Table[(2^(-1+n)) (-1+n)! (((n!))^2) HypergeometricPFQ[{(1/2)-(n/2),-(n/2),n},{1,1},1],{n,10}]

FindSequenceFunction[seq,n-k0+1]//FullSimplify

gf=(x^k0)FindGeneratingFunction[seq,x]

FindLinearRecurrence[seq]

Table[2^n*HypergeometricPFQ[{n,(1-n)/2,-n/2},{1,1},1],{n,10}]

FullSimplify[n!^2*(n-1)!*2^n*HypergeometricPFQ[{n,(1-n)/2,-n/2},{1,1},1]]//FunctionExpand

n!^2*(n-1)!*2^n*HypergeometricPFQ[{n,(1-n)/2,-n/2},{1,1},1]//TraditionalForm

Table[n!^2*(n-1)!*2^n*HypergeometricPFQ[{n,(1-n)/2,-n/2},{1,1},1],{n,10}]

CrossedPrism

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

FindSequenceFunction[seq,n-1]

Crown

A094047

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

FindLinearRecurrence[Rest@seq]//Head

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

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

n! (∑_(j=0)^(n-1))(((-1))^j) (-j+n-1)! (Binomial[-j+2 n-1, j])+2 (((-1))^n) (n-1)!

Table[Sum[(-1)^j (n-j-1)!Binomial[2n-j-1,j],{j,0,n-1}],{n,5}]

Sum[(-1)^j (n-j-1)!Binomial[2n-j-1,j],{j,0,n-1}]

bug(323540)

Sum[(-1)^j (n-j-1)!Binomial[2n-j-1,j],{j,0,n-1}]

Sum[(-1)^j (n-j-1)!Binomial[2n-j-1,j],{j,0,n-1}]

Table[(-1)^n 2(n-1)!+n!Sum[(-1)^j (n-j-1)!Binomial[2n-j-1,j],{j,0,n-1}],{n,10}]

Table[(n-1)! Round[2n Exp[-2]BesselK[n,2]],{n,10}]

Table[2n Exp[-2]BesselK[n,2],{n,10}]//N

Cycle

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

seq=Table[GraphData[{"Cycle",n},"HamiltonianCycleCount"],{n,3,20}]

CycleComplement

A002816

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

(n^2 - 7n + 9)a(n) = (n^3 - 8n^2 + 18n - 21)a(n - 1) + 4n(n - 5)a(n - 2) - 2(n - 6)(n^2 - 5n + 3)a(n - 3) + (n^2 - 7n + 9)a(n - 4) + (n - 5)(n^2 - 5n + 3)a(n - 5), for n >= 8. - Poulet.

Join[{1,0},RecurrenceTable[{a[3]==0,a[4]==0,a[5]==1,a[6]==3,a[7]==23,(n^2-7n+9)a[n]==(n^3-8n^2+18n-21)a[n-1]+4n(n-5)a[n-2]-2(n-6)(n^2-5n+3)a[n-3]+(n^2-7n+9)a[n-4]+(n-5)(n^2-5n+3)a[n-5]},a,{n,3,20}]]

RSolve[{a[3]==0,a[4]==0,a[5]==1,a[6]==3,a[7]==23,(n^2-7n+9)a[n]==(n^3-8n^2+18n-21)a[n-1]+4n(n-5)a[n-2]-2(n-6)(n^2-5n+3)a[n-3]+(n^2-7n+9)a[n-4]+(n-5)(n^2-5n+3)a[n-5]},a[n],n]

Table[[n],{n,3,20}]

seq=Table[[n],{n,3,40}]

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

DiagonalIntersection

A300513

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

FibonacciCube

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

FoldedCube

A280847

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

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

FindLinearRecurrence[seq]

FindLinearRecurrence[Rest@seq]

Grid n×n

A143246

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

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

FindSequenceFunction[seq2,n]

FindGeneratingFunction[seq2,x]

FindLinearRecurrence[seq2]

http://flowproblem.ru/cycles/hamilton-cycles

(Undirected)

seq3={1,6,1072,4638576,467260456608,1076226888605605706,56126499620491437281263608,65882516522625836326159786165530572,1733926377888966183927790794055670829347983946,1020460427390768793543026965678152831571073052662428097106,13404209505893761748339786653564937498745897123531041248680272448954956}

FindSequenceFunction[seq3,n]//Timing

FindGeneratingFunction[seq3,x]//Timing

FindLinearRecurrence[seq3]//Timing

Grid n×n×n

A000000

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

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

FindSequenceFunction[seq,n-k0+1]

gf=(x^k0)FindGeneratingFunction[seq,x]

HalvedCube

A281255

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

FindSequenceFunction[seq,n-k0+1]

gf=FindGeneratingFunction[seq,x]

Hanoi

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

Helm

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

Hypercube

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

A003042

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

k0=l[[1,1]]

seq=l[[All,2]]

FindSequenceFunction[seq,n-k0+1]

gf=(x^k0)FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

coef=FindLinearRecurrence[seq]

coef=FindPolynomialRecurrence[seq,Floor[Length[seq/2]]]

LinearRecurrence[coef,seq,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[a[k+k0-1]==seq[[k]],{k,Length[coef]}],ToRecurrence[a,x,n,coef]],a[n],n],n∈Integers&&n>0]

Keller

A000000

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

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

FindSequenceFunction[seq,n-k0+1]

gf=(x^k0)FindGeneratingFunction[seq,x]

King n×n

A140521

seq=Table[GraphData[{"King",{n,n}},"HamiltonianCycleCount"],{n,10}]

Knight n×n

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

A001230

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

Ladder

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

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

MengerSponge

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

MoebiusLadder

A103889(n-4)

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

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

Table[n+2-(((-1))^n),{n,-1,25}]

Table[n-(((-1))^n),{n,25}]

Table[2+(((-1))^(1+n))+n,{n,25}]

Mycielski

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

A143247(n)/2

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

Odd

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

A000000

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

PathComplement

A242522

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

Prism

A014681

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

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

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

Table[(((-1))^n) +(1+n),{n,3,25}]

Queen n×n

A158663

seq=Table[GraphData[{"Queen",{n,n}},"HamiltonianCycleCount"],{n,10}]

Rook n×n

2*A269561

seq=Table[GraphData[{"Rook",{n,n}},"HamiltonianCycleCount"],{n,10}]

RookComplement n×n

A291865

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

2seq

SierpinskiCarpet

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

SierpinskiSieve

A246959

seq=Table[GraphData[{"SierpinskiSieve",n},"HamiltonianCycleCount"],{n,6}]

Table[Piecewise[{{1,n==1||n==2}},8 (12^(((3^(n-2))-3)/2))],{n,8}]

SierpinskiTetrahedron

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

Star

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

seq=Table[GraphData[{"Star",n},"HamiltonianCycleCount"],{n,10}]

Sun

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

Sunlet

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

TorusGrid n×n

2*A222199

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

Transposition

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

A307896

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

k0=l[[1,1]]

seq=l[[All,2]]

FindSequenceFunction[seq,n-k0+1]

gf=(x^k0)FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

coef=FindLinearRecurrence[seq]

coef=FindPolynomialRecurrence[seq,Floor[Length[seq/2]]]

LinearRecurrence[coef,seq,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[a[k+k0-1]==seq[[k]],{k,Length[coef]}],ToRecurrence[a,x,n,coef]],a[n],n],n∈Integers&&n>0]

Triangular

A129349

seq=Table[GraphData[{"Triangular",n},"HamiltonianCycleCount"],{n,2,10}]

TriangularGrid

A112676

seq=Table[GraphData[{"TriangularGrid",n},"HamiltonianCycleCount"],{n,0,20}]

Length@DeleteMissing@seq

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

FindLinearRecurrence[DeleteMissing@Drop[seq,4]]//Head//Timing

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

2seq

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

A289703

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

TriangularHoneycombRook

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

TriangularSnake

A063524

seq=Table[GraphData[{"TriangularSnake",n},"HamiltonianCycleCount"],{n,1,19,2}]

Wheel

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

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

FindSequenceFunction[seq,n-3]

WhiteBishop n×n

A282890

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

Tournaments

?HamiltonianCycle

?HamiltonianQ

Map[HamiltonianQ[#]&,Tournaments/@Range[4],{2}]//ColumnForm

Map[ConnectedQ[#,Strong]&,Tournaments/@Range[4],{2}]//ColumnForm

...these are wrong; a tournament has a Hamiltonian cycle iff it is strongly connected...

Algorithms

FindHamiltonianCycle

DeleteCases[Monitor[{g=#,GraphData[#,"|HC|"],HamiltonianCycleCount[GraphData[#],Method->"FindHamiltonianCycle"]}&/@GraphData["Hamiltonian",;;10],g],{_,x_,x_}]//Timing

FindPath

DeleteCases[Monitor[{g=#,GraphData[#,"|HC|"],HamiltonianCycleCount[GraphData[#],Method->"FindPath"]}&/@GraphData["Hamiltonian",;;10],g],{_,x_,x_}]//Timing