Untraceable Graph

Author

Eric W. Weisstein
May 3, 2022

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

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

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

Counts

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

files=FileNames["*.m"]

traceable=Get/@files;

All

A283420

Count[#,False]&/@traceable

Length/@Table[GraphData["Untraceable",n],{n,7}]

Connected

A283421

Table[Count[traceable[[n]][[ConnectedGraphIndices[n]]],False],{n,10}]

Length/@Table[GraphData[{"Connected","Untraceable"},n],{n,7}]

Polyhedral

TextGrid[Sort[GraphData[#,{"V","#"}]&/@GraphData[{"Polyhedral","Untraceable"}]],Dividers->All,Alignment->{{Decimal,Left}}]

Do[Print[{n,Count[PolyhedralGraphs[n],_?(!TraceableGraphQ[#]&)]//Timing}],{n,10}]

SetDirectory["/Developer/eww/Graphs/Polyhedral/13"]

files=FileNames["*"]

Total[(Print[c=Count[Import[#,"Sparse6"],_?(!TraceableGraphQ[#]&)]];c)&/@files]//Timing//AbsoluteTiming

Classes that are nonhamiltonian

GraphClassesThatAreClass["Untraceable"]

GraphClassesThatAreClass["Untraceable",2;;]

Figure

GraphicsGrid[Flatten[Partition[#,UpTo[7]]&/@Table[StyleGraphs[GraphData[#]&/@GraphData[{"Connected","Untraceable"},n],VertexSize->{"Scaled",.05}],{n,6}],1],Dividers->{{Thick,{True},Thick},{Thick,Thick,Thick,{True},Thick}},ImageSize->700]