Bicubic Graph

Author

Eric W. Weisstein
July 28, 2009

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

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

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

Enumeration

On n Nodes

Count[#,_?BicubicQ]&/@Graphs/@Range[9]//Timing

Count[#,_?BicubicQ]&/@Graphs/@Range[2,9,2]//Timing

g=Select[#,BicubicQ]&/@Graphs/@Range[2,9,2];

g=Table[GraphData["Bicubic",n],{n,8}]//Timing

Length/@(g=Prepend[Table[Cases[If[n<14,ImportRegularGraphs,ImportRegularGraphs2][3,n],_?BicubicQ],{n,4,16,2}],{}])//Timing//AbsoluteTiming

Length/@(g=Prepend[Table[Cases[If[n<14,ImportRegularGraphs,ImportRegularGraphs2][3,n],_?BicubicQ],{n,4,18,2}],{}])//Timing//AbsoluteTiming

Length/@(g=Prepend[Table[Cases[If[n<14,ImportRegularGraphs,ImportRegularGraphs2][3,n],_?BicubicQ],{n,4,20,2}],{}])//Timing//AbsoluteTiming

DeleteCases[#,{}]&/@Map[RecognizeGraph,Most[g],{2}]//Column

Graph[{"MoebiusLadder",6}]

r=Map[RecognizeGraph,g,{2}]

GraphicsGrid[DeleteCases[Map[GraphPlot[Graph[#],Method->None,PlotLabel->TextCell[GraphData[#,"Name"],PageWidth->80,TextAlignment->Center]]&,Take[r,6],{2}],{}],ImageSize->400,BaseStyle->Italic]

GraphData

TableForm[Take[Sort[GraphData["Bicubic",{"V","Name"}]],30],TableDepth->2]

Ellingham-Horton 54-Graph (3-connected bicubic nonhamiltonian)

Image

GraphData["EllinghamHortonGraph54"]

Properties

Through[{V,M}[g=Graph["EllinghamHortonGraph54"]]]

Through[{BicubicQ,VertexConnectivity}[g]]

TimeConstrained[HamiltonianQ[g],60]//Timing

TimeConstrained[FastHamiltonianQ[g],60]//Timing

Through[{Diameter,Girth,Radius}[g]]//Timing

Construction

ShowLabeledGraph[h=AddEdges[DeleteEdges[ChangeVertices[
g=GraphUnion[
ChangeVertices[Cycle[16],Through[{Sin,Cos}[Pi/16+2Pi#/16.]]&/@Range[0,15]],WebGraph[6,3],WebGraph[6,3],Path[2]],
Join[Table[{0,0},{16}],Table[{-3.,-1.5},{18}],Table[{-3.,-1.5},{18}],{{-5.5,-2.},{-6.,-1.8}}]+Vertices[g]],
{{29,30},{47,48},{23,24},{24,25},{25,26},{26,27},{27,28},{23,28},{41,42},{42,43},{43,44},{44,45},{45,46},{41,46},{17,18},{35,36}}],
{{2,7},{10,15},{4,9},{5,16},{8,13},{1,12},{17,30},{18,29},{36,47},{35,48},{25,28},{43,46},{11,23},{14,24},{3,41},{6,42},{27,54},{45,54},{26,53},{44,53}}],
AspectRatio->Automatic,VertexStyle->Disk[.02]
]

Ellingham-Horton 78-Graph (3-connected bicubic nonhamiltonian)

Image

GraphData["EllinghamHortonGraph78"]

Properties

Through[{V,M}[g=Graph["EllinghamHortonGraph78"]]]

Through[{BicubicQ,VertexConnectivity}[g]]//Timing

TimeConstrained[HamiltonianQ[g],60]//Timing

TimeConstrained[FastHamiltonianQ[g],60]//Timing

Through[{Diameter,Girth,Radius}[g]]//Timing

Owens 78-Graph (3-connected bicubic nonhamiltonian)

Image

GraphData["OwenGraph78"]

Properties

Through[{V,M}[g=Graph["OwenGraph78"]]]

Through[{Diameter,Girth,Radius}[g]]//Timing

Through[{BicubicQ,VertexConnectivity}[g]]//Timing

TimeConstrained[HamiltonianQ[g],60]//Timing

TimeConstrained[FastHamiltonianQ[g],3600]//Timing

Construction

ShowLabeledGraph[g1=DeleteEdges[GeneralizedPetersenGraph[8,3],{{2,10},{6,14}}]]

ShowLabeledGraph[g2=AddEdges[GraphUnion[2,g1],{{10,26},{2,18},{6,22},{14,30}}]]

BicubicQ[g2]

ShowLabeledGraph[g22=AddEdges[GraphUnion[2,g1],{{10,30},{2,18},{6,22},{14,26}}]]

BicubicQ[g22]

FastIsomorphicQ[g2,g22]

ShowLabeledGraph[g3=DeleteVertices[g2,{10,26}]]

ShowLabeledGraph[g33=DeleteVertices[g2,{10,30}]]

FastIsomorphicQ[g3,g33]

ShowLabeledGraph[g5=AddEdges[AddVertices[ChangeVertices[g4=GraphUnion[GraphUnion[2,g3],g1],Join[Take[Vertices[g4],60],.2#+{0,-.3}&/@Take[Vertices[g4],-16]]],{{.5,.2},{.5,.27}}],{{77,78}}],VertexStyle->PointSize[.015],ImageSize->700]

ShowLabeledGraph[g6=AddEdges[g5,{{77,78},
{10,78},{25,77},{9,70},{24,66},
{54,78},{39,77},{40,62},{55,74}}
],VertexStyle->PointSize[.015],ImageSize->700]

TimeConstrained[FastHamiltonianQ[g6],3600]//Timing

l=Flatten[Outer[List,Permutations@{9,10,24,25},Permutations@{39,40,54,55},1],1];

Length[l]

Select[l,
(g=AddEdges[g5,Join[{{77,78}},
Transpose[{First[#],{66,70,77,78}}],
Transpose[{Last[#],{62,74,77,78}}]
]];BicubicQ[g]&&!Unequal[TimeConstrained[FastHamiltonianQ[g],10],$Aborted,True])&,1]//Timing

Select[l,
(g=AddEdges[g5,Join[{{77,78}},
Transpose[{First[#],{66,70,77,78}}],
Transpose[{Last[#],{62,74,77,78}}]
]];BicubicQ[g]&&!Unequal[TimeConstrained[FastHamiltonianQ[g],10],$Aborted,True])&,1]//Timing

Through[{V,M}[g]]

FastIsomorphicQ[g6,Graph["EllinghamHortonGraph78"]]

TimeConstrained[FastHamiltonianQ[g6],3600]//Timing

HamiltonianCycles[g6]//Timing

GraphDataString

GraphDataString[g6,
"Name"->"Owen's nonhamiltonian bicubic graph",
"StandardName"->"OwensGraph",
"Information"->"BicubicGraph",
TimeConstraint->600,
MemoryConstraint->2*^9,
Debug->True
]

Horton 92-Graph (3-connected bicubic nonhamiltonian)

Image

GraphData["HortonGraph92"]

Properties

Through[{V,M}[g=Graph["HortonGraph92"]]]

Through[{Diameter,Girth,Radius}[g]]//Timing

Through[{BicubicQ,VertexConnectivity}[g]]//Timing

TimeConstrained[HamiltonianQ[g],60]//Timing

TimeConstrained[FastHamiltonianQ[g],3600]//Timing

GraphData String

GraphDataString[HortonGraph92,
"StandardName"->"HortonGraph92",
"Name"->"Horton's nonhamiltonian bicubic graph",
"Skip"->{"Perfect"},
"Classes"->{"Nonhamiltonian"},
TimeConstraint->60,
Debug->True
]

Horton 96-Graph (3-regular 3-connected nonhamiltonian)

Image

GraphData["HortonGraph96"]

Properties

Through[{V,M}[g=Graph["HortonGraph96"]]]

Through[{Diameter,Girth,Radius}[g]]//Timing

Through[{Union[Degrees[g]],VertexConnectivity}[g]]//Timing

TimeConstrained[HamiltonianQ[g],60]//Timing

TimeConstrained[FastHamiltonianQ[g],300]//Timing

Construction

ShowLabeledGraph[h=AddEdges[DeleteEdges[DeleteVertices[ChangeVertices[
g=GraphUnion[Sequence@@Table[Cycle[16],{6}],EmptyGraph[3]],
Join[Join@@Table[2Through[{Cos,Sin}[2Pi i/6.]]+.7Through[{Cos,Sin}[2Pi j/16.]],{i,0,5},{j,16}],{{-.5,.4},{0,0},{.5,.4}}]
],
{25,83,62}
],{{17,18},{1,2},{9,10},{89,88},{66,67},{74,75},{53,54},{37,38},{45,46}}],
{{32,37},{36,41},{43,38},{33,44},{40,45},{46,35},{47,42},{39,34},
{18,23},{19,29},{22,26},{24,28},
{18,9},{25,1},{27,17},{31,21},{30,25},{17,2},{81,74},
{75,88},{89,66},{53,38},{61,37},
{94,46},{94,67},{94,10},{95,56},{95,20},{95,91},{96,60},{96,24},{96,80},
{1,12},{16,5},{3,14},{4,9},{6,11},{7,2},{8,13},{10,15},
{81,86},{82,93},{83,88},{84,80},{85,90},{87,92},{89,79},
{66,77},{65,70},{64,75},{63,68},{76,71},{67,72},{69,74},{73,78},
{61,51},{62,58},{49,60},{48,53},{52,57},{54,59},{55,50},{45,54}
}
],
AspectRatio->Automatic,VertexStyle->Disk[.02],ImageSize->400
]