Barnette's Conjecture

Author

Eric W. Weisstein
November 13, 2003

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

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

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

Conjecture 1

BarnetteQ[g_Graph]:=CubicQ[g]&&BipartiteQ[g]&&KConnectedQ[3,g]&&PlanarQ[g]

Enumeration

Length/@(barnette=Select[#,BarnetteQ]&/@Graphs/@Range[9])//Timing

Map[HamiltonianQ,barnette,{2}]

HighlightHamiltonian[g_Graph]:=SetGraphOptions[g,Join[Partition[HamiltonianCycle[g],2,1],{EdgeColor->Blue,EdgeStyle->Thick}]]

ShowGraphArray[HighlightHamiltonian/@{CubicalGraph,
Skeleton[TruncatedOctahedron] (*,
Skeleton[GreatRhombicuboctahedron],
Skeleton[GreatRhombicosidodecahedron]*)
},
VertexStyle->Disk[.05],
VertexColor->Red,
AspectRatio->Automatic]

Special Cases

Table[
{ArchimedeanGraphName[n],BarnetteQ[ArchimedeanGraph[n]]//Timing},
{n,13}]//ColumnForm

HamiltonianQ/@b[[Flatten[Position[b2,True]]]]