Folkman Graph

Author

Eric W. Weisstein
November 10, 2022

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

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

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

Embeddings

GraphData["FolkmanGraph","StandardName"]

Primary

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

Construction from Read and Wilson

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["FolkmanGraph","EdgeList"]]

Default embedding

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

RotateGraph[,Pi/10]

v=Join[UnitCirclePoints[10,Pi/2],CirclePoints[1,5],CirclePoints[1/2,5]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,6,7,8,9,10,1,19,5,16,9,18,3,20,7,17,1],e[2,13,10,12,8,11,6,15,4,14,2],e[13,19,15,16,12,18,14,20,11,17,13]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Square rings construction

GraphData["FolkmanGraph","Graph","Labeled"]

ee=Join[
Flatten[{
Table[{{4i+3,4i+6},{4i+3,4i+8}},{i,0,3}],Table[{{4i+1,4i+10},{4i+1,4i+12}},{i,0,2}],{{{2,19},{19,4},{6,17},{8,17},{2,13},{13,4}}}},2],
Flatten[Partition[#,2,1,1]&/@Partition[Range[20],4],1]]

v=Join@@Table[CirclePoints[i/5,4],{i,5}];
g=Graph[Range[Length[v]],UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Degenerate

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

Bilateral

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

Circular

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

Planar

GraphData["FolkmanGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

CrossingNumber[GraphData["FolkmanGraph"],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData["FolkmanGraph"],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["FolkmanGraph","Circulant"]

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

Halin

GraphData["FolkmanGraph","Halin"]

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

LCF

GraphData["FolkmanGraph","LCF"]

GraphData["FolkmanGraph","LCFSignature"]

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

Tally[LCFFromEmbedding[#][[2]]&/@%]

LCF compute

Length[FindHamiltonianCycle[GraphData["FolkmanGraph"],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData["FolkmanGraph"],All])[[All,2]]]//Timing

gs=LCFGraph@@@lcf//StyleGraphs

gs=Join[With[{g=BilateralLCFEmbedding[#]},If[MissingQ[g],#,g]]&/@LCFGraph@@@DeleteCases[lcf,{_,1}],DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]]

UnitDistance

GraphData["FolkmanGraph","UnitDistance"]

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

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

Matchstick

GraphData["FolkmanGraph","Matchstick"]

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

3D default

Graph3D[GraphData["FolkmanGraph","Edges"]]

3D All

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

3D UnitDistance

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

3-D UnitDistance construction

Jeremy Tan, Oct 26, 2021

Since the Folkman graph contains Subscript[K, 2,3] it is not unit-distance embeddable in the plane, but an embedding in Euclidean 3-space is easy

folkmanV[d_]:=Module[{core,hang,verts},
core=Table[d Exp[2I k Pi/5]Csc[Pi/5]/2,{k,0,4}];
hang=Table[Exp[2I k Pi/5](core[[3]]-d Exp[I Pi/6]),{k,0,4}];
verts=RootReduce@Join[Append[ReIm[#],0]&/@core,
Append[ReIm[#],Sqrt[1-d^2]]&/@core,
Append[ReIm[#],-Sqrt[1-d^2]]&/@core,
Append[ReIm[#],0]&/@hang];
Graph[Range[Length[verts]],UnitEdges[verts],VertexCoordinates->verts]
]

g=folkmanV[1/2]

RecognizeGraph[g]

GraphEmbedding[g]

UnitDistanceGraphEmbeddingQ[g]

3D Polyhedron

GraphData["FolkmanGraph","Polyhedral"]

GraphData["FolkmanGraph","Graph",{"3D","Polyhedron"}]

GraphData

GraphClassString

GraphClassString["FolkmanGraph"]