Hypotraceable Graph

Author

Eric W. Weisstein
March 16, 2018

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

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

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

Counts

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

Do[Print[{n,Graphs[n];//Timing}],{n,8}]

Do[Print[{n,Count[Graphs[n],_?(HypotraceableGraphQ[#,"Preprocess"->False]&)]//Timing}],{n,8}]

9

DistributeDefinitions[HypotraceableGraphQ]

Length[Graphs[9]]//AbsoluteTiming

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

Count[p=ParallelMap[HypotraceableGraphQ[#,"Preprocess"->False]&,Graphs[9]],True]//AbsoluteTiming

10

DistributeDefinitions[HypotraceableGraphQ]

Length[Graphs[10]]//AbsoluteTiming

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

Count[p=ParallelMap[HypotraceableGraphQ[#,"Preprocess"->False]&,Graphs[10]],True]//AbsoluteTiming

Graphics

Grid[hypotraceable=SortBy[GraphData["Hypotraceable",{"V","#"}],First],Dividers->All,Alignment->{{Decimal,Left}}]

GraphicsGrid[{Show[GraphData[#]//StyleGraphs[#,VertexSize->{"Scaled",.025}]&,PlotLabel->GraphData[#,"Name"],LabelStyle->{FontFamily->"Times",FontSlant->Italic}]&/@hypotraceable[[All,-1]]},ImageSize->700]

Examples

34

V[g=Graph["ThomassenGraph"]]

V6.0

HypotraceableQ[ThomassenGraph]//Timing

V6.1

HypotraceableQ[g,False]//Timing

HamiltonianPaths[g,{}]//Timing

HamiltonianCycles[g]//Timing

HamiltonianPaths[g]//Timing

41

Construction

v={{220,94},{263,163},{304,224},{341,294},{381,229},{428,161},{475,90},{394,88},{304,93},{354,385},{429,431},{520,390},{657,201},{656,100},{561,47},{323,383},{229,433},{152,394},{37,197},{41,104},{137,52},{387,319},{428,393},{466,299},{384,372},{478,371},{527,204},{570,90},{613,175},{524,119},{616,121},{210,293},{250,392},{282,323},{205,362},{290,373},{155,193},{127,89},{79,172},{170,121},{74,113}};

Length[v]

Mean[v]

v0=(#-Mean[v])&/@v;
vv=v0/Max[Abs[Flatten[v0]]]//N

Length[vv]

ShowLabeledGraph[g=RemoveMultipleEdges[AddEdges[Graph[{},List/@vv],
Join[
Join@@(Partition[#,2,1]&/@{{4,Sequence@@Range[10,15],7},{4,Sequence@@Range[16,21],1},{2,6},{3,8},{5,9},{19,39},{20,41},{21,38},{1,40},{15,28},{14,31},{12,26},{11,23},{18,35},{10,25},{4,22},{17,33},{16,36},{4,34},{24,27},{32,37},{7,30},{29,13}}),
Join@@(Partition[#,2,1,1]&/@{Range[9],Range[37,41],Range[32,36],Range[22,26],Range[27,31]})]]
],VertexStyle->Disk[.02]]

V[g]

Tally[Degrees[g]]

Position[Degrees[g],6]

Girth[g]

RecognizeGraph[g]

ConnectedQ[g]

HypotraceableQ[g,False]//Timing

HamiltonianPaths[g,{}]//Timing

Print@GraphDataString[g,
"Name"->"Thomassen graph 41",
"StandardName"->"ThomassenGraph41",
"Classes"->{"Hypotraceable"},
TimeConstraint->120,
Debug->True
]

Planar

Figure

GraphicsGrid[{GraphPlot[Graph[#],Method->None,PlotLabel->GraphData[#,"Name"],BaseStyle->Italic]&/@GraphData[{"Planar","Hypotraceable"}]}/.AbsolutePointSize[_]:>AbsolutePointSize[4]]