Maximally Nonhamiltonian Graph

Author

Eric W. Weisstein
April 28, 2023

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

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

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

Example

g=GraphData["ButterflyGraph"]

e=EdgeList[System`GraphComplement[g]]

gs=System`Graph[EdgeList[EdgeAdd[g,#]]]&/@e

RecognizeGraph/@gs

HamiltonianGraphQ/@gs

List

l=SortBy[GraphData["MaximallyNonhamiltonian"],GraphData[#,"V"]&]

Length/@Table[GraphData["MaximallyNonhamiltonian",n],{n,10}]

Select[l,EdgeList[System`GraphComplement[GraphData[#]]]==={}&]

GraphData["P2","Hamiltonian"]

Select[l,GraphData[#,"Snark"]&]

Select[l,GraphData[#,"Snark"]&]

Select[GraphData["Snark"],GraphData[#,"MaximallyNonhamiltonian"]===False&]

Enumeration

class=Table[{n,GraphData["MaximallyNonhamiltonian",n]},{n,7}];

Length/@class[[All,2]]

Grid[class,Dividers->All,Alignment->Left]

GraphicsGrid[Map[GraphPlot[GraphData[#],PlotLabel->TextCell[Style[If[Head[not=GraphData[#,"Notation"]]===Missing,StringReplace[GraphData[#,"Name"],"\[Hyphen]"->"-"],not],Italic,FontFamily->"Times"],PageWidth->75,TextAlignment->Center]]&,Flatten[Partition[#,7,7,{1,1},{}]&/@DeleteCases[class[[All,2]],{}],1],{2}],Spacings->{-30,10},ImageSize->520,Dividers->All]

7 vertices

Graphs[7];ConnectedGraphs[7];

RecognizeGraph/@Select[Graphs[7],MaximallyNonhamiltonianGraphQ]//Timing

RecognizeGraph/@Select[ConnectedGraphs[7],MaximallyNonhamiltonianGraphQ]//Timing

8 vertices

Graphs[8];ConnectedGraphs[8];

RecognizeGraph/@Select[Graphs[8],MaximallyNonhamiltonianGraphQ]//Timing

RecognizeGraph/@Select[ConnectedGraphs[8],MaximallyNonhamiltonianGraphQ]//Timing

Algorithms

<<MathWorld`Graphs`

"Edges"

DeleteCases[Monitor[{gn=#,GraphData[#,"MaximallyNonhamiltonian"],MaximallyNonhamiltonianGraphQ[GraphData[#],Method->"Edges"]}&/@GraphData[;;10],gn],{_,x_,x_}]//Timing

DeleteCases[Monitor[{gn=#,GraphData[#,"MaximallyNonhamiltonian"],MaximallyNonhamiltonianGraphQ[GraphData[#],Method->"Edges"]}&/@GraphData[;;15],gn],{_,x_,x_}]//Timing

"SymmetricallyDistinctEdges"

DeleteCases[Monitor[{gn=#,GraphData[#,"MaximallyNonhamiltonian"],MaximallyNonhamiltonianGraphQ[GraphData[#],Method->"SymmetricallyDistinctEdges"]}&/@GraphData[;;10],gn],{_,x_,x_}]//Timing

DeleteCases[Monitor[{gn=#,GraphData[#,"MaximallyNonhamiltonian"],MaximallyNonhamiltonianGraphQ[GraphData[#],Method->"SymmetricallyDistinctEdges"]}&/@GraphData[;;15],gn],{_,x_,x_}]//Timing