Subhamiltonian Graph

Author

Eric W. Weisstein
January 26,, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/SubhamiltonianGraph.nb.

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

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

Source

Lindgren-SousselierGraph.html

Classes

Classes that are Subhamiltonian

classes1=GraphClassesThatAre["Subhamiltonian"]

Classes for which all members are Hamiltonian and planar

classes2=Select[
GraphData["Classes"],
GraphData[{#,"Hamiltonian"}]===GraphData[{#,"Planar"}]===GraphData[#]&
]

Complement[classes2,classes1]

GraphDataCountTable

table=GraphDataCountTable["Subhamiltonian"]

DateString[]

TextGrid[OEISUpdates[table],Dividers->All]

Parametrized families

<<MathWorld`Graphs`

Alkane

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

AlternatingGroupGraph

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

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"Subhamiltonian"],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"Subhamiltonian"],{n,20}]

Antiprism

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

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

Apollonian

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

Barbell

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

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Subhamiltonian"],{n,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"Subhamiltonian"],{n,20}]

Book

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

Bruhat

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

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"Subhamiltonian"],{n,20}]

Cameron

seq=Table[GraphData[{"Cameron",n},"Subhamiltonian"],{n,20}]

Centipede

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

Circulant

GraphData[{"Circulant","Subhamiltonian"}]

CocktailParty

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

Complete

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

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

CompleteBipartite n×n

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

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

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Subhamiltonian"],
Piecewise[{{True,Min[m,n]<=2}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteTripartite n×n×n

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

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

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"Subhamiltonian"],
Piecewise[{{True,k==m==n==2||(Min[k,m,n]==1&&k m n<=2Max[k,m,n])}},False]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CossidentePenttila

GraphData[{"CossidentePenttila","Subhamiltonian"}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"Subhamiltonian"],{n,2,12}]

Crown

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

CubeConnectedCycle

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

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

Cycle

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

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

CycleComplement

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

DiagonalIntersection

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

Dipyramid

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

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"Subhamiltonian"],{n,0,7}]

DoubleCone

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

Empty

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

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

FibonacciCube

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

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"Subhamiltonian"],{n,20}]

Flower

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

FoldedCube

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

Gear

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

GeneralizedPetersen

Entity["Graph",{"GeneralizedPetersen",{n,k}}]["Subhamiltonian"]

GraphData[{"GeneralizedPetersen","Subhamiltonian"}]

GraphData[{"GeneralizedPetersen","Planar"}]

Giraffe n×n

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

Goldberg

seq=Table[GraphData[{"Goldberg",n},"Subhamiltonian"],{n,3,20}]

Grid n×n

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

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

Grid m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"Subhamiltonian"],
True
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

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

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

Grid k×m×n

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

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"Subhamiltonian"],
Piecewise[{{True,Min[k, m, n] == 1 || (Min[k, m, n] == 2 && k m n == 4Max[k, m, n])}},False]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

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

Hanoi

seq=Table[GraphData[{"Hanoi",n},"Subhamiltonian"],{n,6}]

Helm

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

Hypercube

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

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

KC

GraphData[{"KC","Subhamiltonian"}]

Keller

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

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

King n×n

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

King m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"Subhamiltonian"],
False
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

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

Knight m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"Subhamiltonian"],
False
},{n,10},{m,n}],1],{_,x_,x_}]

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

KP

GraphData[{"KP","Subhamiltonian"}]

Ladder

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

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

LadderRung

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

LindgrenSousselier

seq=Table[GraphData[{"LindgrenSousselier",n},"Subhamiltonian"],{n,11}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"Subhamiltonian"],{n,15}]

MengerSponge

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

MoebiusLadder

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

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

Mycielski

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

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

Odd

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

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

Paley

GraphData[{"Paley","Subhamiltonian"}]

Pan

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

Path

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

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

PathComplement

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

Peisert

GraphData[{"Peisert","Subhamiltonian"}]

Pell

seq=Table[GraphData[{"Pell",n},"Subhamiltonian"],{n,9}]

PlummerToft

seq=Table[GraphData[{"PlummerToft",n},"Subhamiltonian"],{n,20}]

Prism

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

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

Queen n×n

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

Rook n×n

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

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"Subhamiltonian"],{n,20}]

SierpinskiCarpet

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

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"Subhamiltonian"],{n,7}]

SierpinskiTetrahedron

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

Spoke n×n

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

StackedBook m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedBook",{m,n}},"Subhamiltonian"],
False
},{n,10},{m,n}],1],{_,x_,x_}]

StackedBook n×n

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

StackedPrism m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedPrism",{m,n}},"Subhamiltonian"],
True
},{m,3,8},{n,5}],1],{_,x_,x_}]

StackedPrism n×n

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

Star

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

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

Sun

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

Sunlet

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

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"Subhamiltonian"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"Subhamiltonian"],{n,3,20}]

Transposition

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

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

Trapezohedron

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

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

Triangular

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

TriangularGrid

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

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"Subhamiltonian"],{n,20}]

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"Subhamiltonian"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"Subhamiltonian"],{n,20}]

TriangularSnake

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

Turan

GraphData[{"Turan","Subhamiltonian"}]

Web

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

Wheel

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

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

WheelComplement

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

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"Subhamiltonian"],{n,2,20}]

WhiteCamel n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Subhamiltonian"],{n,{5}}]

Zebra n×n

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

Algorithm

Clear[SubhamiltonianEmbeddingILP]

SubhamiltonianEmbeddingILP[g_Graph, admissibleEdges_List] :=
 Module[
	{
		V = VertexList[g],
		baseEdges = EdgeList[g],
		allEdges,
		vars,
		degConstraints,
		cutConstraints
	},

	allEdges = Join[baseEdges, admissibleEdges];

	vars = AssociationThread[
		allEdges -> Array[x, Length[allEdges]]
	];

	(* Degree-2 constraints *)
	degConstraints =
		Table[
			Total @
				(vars /@
					Select[
						allEdges,
						MemberQ[List @@ #, v] &
					]
				) == 2,
			{v, V}
		];

	(* Subtour elimination constraints *)
	cutConstraints =
		Flatten @ Table[
			Total @
				(vars /@
					Select[
						allEdges,
						With[{u = #[[1]], w = #[[2]]},
							Xor[MemberQ[S, u], MemberQ[S, w]]
						] &
					]
				) >= 2,
			{S, Rest @ Most @ Subsets[V]}
		];

	{
		Join[degConstraints, cutConstraints],
		vars
	}
 ]

Clear[SubhamiltonianEmbeddingQ]

SubhamiltonianEmbeddingQ[g_Graph, admissibleEdges_List] :=
 Module[
	{constraints, vars, sol},

	{constraints, vars} =
		SubhamiltonianEmbeddingILP[g, admissibleEdges];

	sol =
		Quiet @ FindInstance[
			constraints &&
				And @@ Thread[Values[vars] ∈ Integers] &&
				And @@ Thread[0 <= Values[vars] <= 1],
			Values[vars],
			Method -> "MOSEK"
		];

	sol =!= {}
 ]

g=PathGraph[Range@5];

admissibleEdges=EdgeList@GraphComplement[g]

SubhamiltonianEmbeddingQ[g,admissibleEdges]

GraphDataClassString

GraphDataClassString["Subhamiltonian"]