Meredith Graph

Author

Eric W. Weisstein
June 19, 2023

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

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

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

Regular Nonhamiltonian Graphs with Vertex Connectivity ≥4

Select[GraphData[{"Nonhamiltonian","Regular"}],GraphData[#,"VertexConnectivity"]≥4&]

Embeddings

Names

GraphData["MeredithGraph","StandardName"]

GraphData["MeredithGraph","StandardNames"]

Primary

GraphData["MeredithGraph"]//StyleGraphs[#,ImageSize->Small]&

All

GraphData["MeredithGraph","Graph","All"]//StyleGraphs

Inexact

Select[GraphData["MeredithGraph","Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData["MeredithGraph","EdgeList"]]

Default embedding

GraphPlot@GraphData["MeredithGraph","Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Construction from Read and Wilson

g=Graph[Range[70],UndirectedEdge@@@{{1,3},{1,4},{1,5},{1,7},{2,3},{2,4},{2,5},{2,33},{3,6},{3,8},{4,6},{4,8},{5,6},{5,8},{6,10},{7,9},{7,13},{7,19},{8,12},{9,11},{9,15},{9,22},{10,14},{10,17},{10,18},{11,13},{11,16},{11,19},{12,14},{12,17},{12,18},{13,15},{13,22},{14,21},{14,24},{15,19},{15,56},{16,20},{16,25},{16,27},{17,21},{17,24},{18,21},{18,24},{19,22},{20,23},{20,26},{20,34},{21,37},{22,26},{23,25},{23,27},{23,28},{24,47},{25,26},{25,34},{26,27},{27,34},{28,29},{28,35},{28,39},{29,30},{29,38},{29,40},{30,31},{30,35},{30,39},{31,32},{31,36},{31,42},{32,33},{32,41},{32,43},{33,36},{33,42},{34,50},{35,38},{35,40},{36,41},{36,43},{37,44},{37,46},{37,51},{38,39},{38,48},{39,40},{40,41},{41,42},{42,43},{43,69},{44,45},{44,48},{44,55},{45,46},{45,49},{45,51},{46,48},{46,55},{47,53},{47,54},{47,57},{48,51},{49,52},{49,58},{49,62},{50,53},{50,54},{50,57},{51,55},{52,56},{52,60},{52,64},{53,59},{53,61},{54,59},{54,61},{55,60},{56,58},{56,62},{57,59},{57,61},{58,60},{58,64},{59,63},{60,62},{61,65},{62,64},{63,66},{63,67},{63,68},{64,70},{65,66},{65,67},{65,68},{66,69},{66,70},{67,69},{67,70},{68,69},{68,70}},VertexCoordinates->(10^(-4)){{4836,-6670},{5779,-3767},{6287,-7141},{6758,-5690},{7230,-4239},{7737,-7613},{8229,-17117},{8680,-4710},{9126,-15882},{9188,-8084},{10022,-14648},{10131,-5182},{10360,-16779},{10639,-8556},{10697,-18911},{10919,-13413},{11110,-7105},{11582,-5653},{11594,-17676},{11816,-12179},{12090,-9027},{12491,-16442},{12712,-10944},{13032,-6125},{13050,-13076},{13387,-15207},{14284,-13973},{14662,-4940},{14662,-3414},{14662,-1888},{14662,-362},{14662,1164},{14662,2690},{15180,-12738},{16188,-3414},{16188,1164},{17195,-12738},{17713,-4940},{17713,-3414},{17713,-1888},{17713,-362},{17713,1164},{17713,2690},{18092,-13973},{18988,-15207},{19326,-13076},{19343,-6125},{19663,-10944},{19885,-16442},{20286,-9027},{20560,-12179},{20782,-17676},{20794,-5653},{21265,-7105},{21456,-13413},{21678,-18911},{21737,-8556},{22016,-16779},{22245,-5182},{22353,-14648},{23187,-8084},{23250,-15882},{23695,-4710},{24146,-17117},{24638,-7613},{25146,-4239},{25617,-5690},{26089,-7141},{26597,-3767},{27539,-6670}}]

Construction

k43=With[{g=CompleteGraph[{4,3}]},Annotate[g,VertexCoordinates->(3/2{#,4#2}&@@@Round[8GraphEmbedding[g]]/8)]]

BipartiteRotate[r_,c_,t_,t0_]:=r{Cos[t+t0],Sin[t+t0]}+{{Cos[t],-Sin[t]},{Sin[t],Cos[t]}}.(#-c)&/@GraphEmbedding[k43]
tenk43=GraphDisjointUnion@@Table[k43,10];
v=RotationMatrix[-Pi/10].#&/@Flatten[Join[Table[BipartiteRotate[5,{3/2,0},2Pi i/5,Pi],{i,5}],Table[BipartiteRotate[15,{3/2,0},2Pi i/5+Pi/5,0],{i,5}]],1];
edges=Flatten[Join[Table[{{i+1,If[i≤21,i+49,i+14]},{i,If[i≤21,i+50,i+15]}},{i,2,30,7}],{{{4,22},{25,8},{15,32},{18,1},{29,11},{43,39},{36,67},{64,60},{57,53},{50,46}}}],1];
g=Graph[Range@Length@v,UndirectedEdge@@@Join[EdgeList[tenk43],edges],VertexCoordinates->v/12]

RecognizeGraph@g

g//StyleGraphs[#,ImageSize->Small]&

GraphData["MeredithGraph"]//StyleGraphs[#,ImageSize->Small]&

Degenerate

GraphData["MeredithGraph","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["MeredithGraph","Graph","Degenerate"]

Bilateral

GraphData["MeredithGraph","Graph","Bilateral"]//StyleGraphs

Circular

GraphData["MeredithGraph","Graph","Circular"]//StyleGraphs

Circular construction

GraphData["MeredithGraph","Hamiltonian"]

Length[hc=FindHamiltonianCycle[GraphData["MeredithGraph"],All][[All,All,1]]]

Planar

GraphData["MeredithGraph","Planar"]

GraphData["MeredithGraph","Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData["MeredithGraph",{"RCN","CN"}]

GraphData["MeredithGraph","Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData["MeredithGraph"],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["MeredithGraph"],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData["MeredithGraph"],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData["MeredithGraph"],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData["MeredithGraph","V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData["MeredithGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["MeredithGraph","Circulant"]

GraphData["MeredithGraph","Graph","Circulant"]//StyleGraphs

Line graph

GraphData["MeredithGraph","Line"]

LineGraphQ[GraphData["MeredithGraph"]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== "MeredithGraph"&]

RootGraph[GraphData["MeredithGraph"]]

Halin

GraphData["MeredithGraph","Halin"]

GraphData["MeredithGraph","Graph","Halin"]//StyleGraphs

Rigid

GraphData["MeredithGraph","Rigid"]

GraphData["MeredithGraph","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["MeredithGraph","Flexible"]

GraphData["MeredithGraph","Graph","Flexible"]//StyleGraphs

LCF

GraphData["MeredithGraph","LCF"]

GraphData["MeredithGraph","HamiltonianCycleCount"]

GraphData["MeredithGraph","LCFSignature"]

GraphData["MeredithGraph","LCFNotations"]

GraphData["MeredithGraph","Graph","LCF"]//StyleGraphs

UnitDistance

GraphData["MeredithGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["MeredithGraph"],Debug->True]//Timing

GraphData["MeredithGraph","Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["MeredithGraph","VertexList"],GraphData["MeredithGraph","EdgeList"]],MaxIterations->500]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData["MeredithGraph","Graph",#]&/@{"All","UnitDistance"})

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["MeredithGraph"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData["MeredithGraph","Matchstick"]

GraphData["MeredithGraph","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["MeredithGraph","Edges"]]

3D All

GraphData["MeredithGraph","Graph",{"3D","All"}]

3D UnitDistance

GraphData["MeredithGraph","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["MeredithGraph","Polyhedral"]

Matrices

GraphicsRow[GraphMatrixPlot[GraphData["MeredithGraph"]]]

Table

GraphClassString["MeredithGraph"]