Ore Graph

Author

Eric W. Weisstein
February 20, 2016

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

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

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

Counts

Array[ConnectedGraphs,10];//Timing//AbsoluteTiming

Array[Graphs,8];//Timing//AbsoluteTiming

Connected

Hamiltonian

1, 0, 1, 3, 8, 48, 383, 6196, 177083,

Empty non-adjacent pairs

Nonadj[g_System`Graph]:=Module[{
d=VertexDegree[g],
n=VertexCount[g]
},
Complement[Subsets[VertexList[g],{2}],List@@@EdgeList[g]]
]

Table[OreCriteronQ[GraphData[{"Complete",n}]],{n,3,7}]

Table[Nonadj[GraphData[{"Complete",n}]],{n,3,7}]

Nonadj[GraphData["TetrahedralGraph"]]

Select[GraphData[3;;7],Nonadj[GraphData[#]]==={}&]

Satisfies Ore criterion > (Skienna Nonstandard)

A092199

Table[Count[OreCriteronQ[GraphData[#],Greater]&/@GraphData[n],True],{n,7}]//Timing

Table[Count[OreCriteronQ[#,Greater]&/@ConnectedGraphs[n],True],{n,9}]//Timing

Table[Count[OreCriteronQ/@Graphs[n],True],{n,8}]

Satisfies Ore criterion >=

A264683

Total[Boole[Get[#]]]&/@FileNames["*.m",FileNameJoin[{$GraphDataDirectory,"Nodes","Ore"}]]

Table[Total[Boole[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","Ore","Ore_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[DisconnectedGraphIndices[n]]]]],{n,10}]

Table[Count[OreGraphQ[GraphData[#]]&/@GraphData[n],True],{n,7}]//Timing

1+{0,0,0,2,4,20,67,502,4941,128360}

Table[Count[OreGraphQ/@ConnectedGraphs[n],True],{n,10}]//Timing

ore=SortBy[Select[GraphData[;;6],OreGraphQ[GraphData[#]]&],GraphData[#,"V"]&]

GraphicsGrid[Flatten[Partition[#,UpTo[8]]&/@Map[Show[SetProperty[GraphData[#],{System`EdgeStyle->Black,System`VertexStyle->Red,VertexSize->{"Scaled",.1}}],PlotLabel->Style[TextCell[GraphData[#,"Name"],PageWidth->70,TextAlignment->Center],Italic,FontFamily->"Times"]]&,SplitBy[ore,GraphData[#,"V"]&],{2}],1],Dividers->All,ImageSize->600]

Difference between >= and >

5-node

ge=Select[GraphData[5],OreCriteronQ[GraphData[#],GreaterEqual]&]

g=Select[GraphData[5],OreCriteronQ[GraphData[#],Greater]&]

exc=Complement[ge,g]

GraphData/@exc

6-node

ge=Select[GraphData[6],OreCriteronQ[GraphData[#],GreaterEqual]&]

g=Select[GraphData[6],OreCriteronQ[GraphData[#],Greater]&]

exc=Complement[ge,g]

GraphData/@exc

Satisfies Ore criterion but nonhamiltonian

With[{n=50},Complement[
Select[GraphData[;;n],
OreCriteronQ[GraphData[#]]&],GraphData["Hamiltonian",;;n]]
]//Timing

With[{n=50},Complement[
Select[GraphData[;;n],
OreCriteronQ[GraphData[#],Greater]&],GraphData["Hamiltonian",;;n]]
]//Timing

Hamiltonian but does not satisfy the Ore criterion

ham=GraphData["Hamiltonian",;;6]

ore=Select[ham,OreGraphQ[GraphData[#]]&]

exc=SortBy[Complement[ham,ore],GraphData[#,"V"]&]

A264684

Table[Count[Transpose[{OreGraphQ/@ConnectedGraphs[n],HamiltonianGraphQ/@ConnectedGraphs[n]}],{False,True},1],{n,8}]//Timing

Table[Count[Transpose[{OreGraphQ/@ConnectedGraphs[n],HamiltonianGraphQ/@ConnectedGraphs[n]}],{False,True},1],{n,9}]//Timing

Table[Count[Transpose[{OreGraphQ/@ConnectedGraphs[n],HamiltonianGraphQ/@ConnectedGraphs[n]}],{False,True},1],{n,10}]//Timing

GraphicsGrid[Flatten[Partition[#,UpTo[8]]&/@Map[Show[SetProperty[GraphData[#],{System`EdgeStyle->Black,System`VertexStyle->Red,VertexSize->{"Scaled",.1}}],PlotLabel->Style[TextCell[GraphData[#,"Name"],PageWidth->70,TextAlignment->Center],Italic,FontFamily->"Times"]]&,SplitBy[exc,GraphData[#,"V"]&],{2}],1],Dividers->All,ImageSize->600]