Chvatál Graph

Author

Eric W. Weisstein
January 20, 2023

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

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

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

Embeddings

GraphData["ChvatalGraph","StandardName"]

Primary

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

Construction from Read and Wilson

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["ChvatalGraph","EdgeList"]]

Default embedding

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

v=Join[CirclePoints[5],CirclePoints[1/2,5],{#/8,0}&/@{-1,1}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,1,7,3,9,5,6,10,1],e[6,2,8,4,10,11,8,12,6],e[11,9,12,7,11]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

v=Join[CirclePoints[4],CirclePoints[1/3,8]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,1,6,7,2,8,9,3,10,11,4,12,5,1],e[5,9,6,10,5],e[12,7,11,8,12]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

gs={,};

Degenerate

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

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

Bilateral

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

Circular

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

Planar

GraphData["ChvatalGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

GraphPlot@RotateGraph[,Pi-Pi/5]

v=Join[{{-1,0},{1,0},{0,Sqrt[3]}},Subdivide[{-1/2,1/4},{1/2,1/4},3],Subdivide[{-1/6,3/4},{1/6,3/4},2],{{-1/6,1},{1/6,1}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,12,8,11,10,12,3,11,1,4,5,6,7,2,5,8],e[10,6,1],e[9,4,3,7,9],e[8,9,10]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["ChvatalGraph","Circulant"]

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

Halin

GraphData["ChvatalGraph","Halin"]

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

Rigid

GraphData["ChvatalGraph","Rigid"]

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

Flexible

GraphData["ChvatalGraph","Flexible"]

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

LCF

GraphData["ChvatalGraph","LCF"]

GraphData["ChvatalGraph","HamiltonianCycleCount"]

GraphData["ChvatalGraph","LCFSignature"]

GraphData["ChvatalGraph","LCFNotations"]

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

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

LCF compute all

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

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

lcf

LCFGraph@@@lcf//StyleGraphs

(gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]}])//Timing

Length[gs]

UnitDistance

GraphData["ChvatalGraph","UnitDistance"]

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["ChvatalGraph","VertexList"],GraphData["ChvatalGraph","EdgeList"]]]

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

Select[%,UnitDistanceGraphEmbeddingQ]

g=LabelGraph@RotateGraph[,{10,9}]

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData["ChvatalGraph","Matchstick"]

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

3D default

Graph3D[GraphData["ChvatalGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["ChvatalGraph","Polyhedral"]

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

Chvatal's theorem

data={Take[#[[1]],2],#[[All,-1]]}&/@SplitBy[Sort[Cases[GraphData[#,{"MaximumVertexDegree","ChromaticNumber","Girth","#"}]&/@GraphData["Regular"],{m_,m_,n_,g_}:>{m,n,g}]],Most]

TextGrid[{Sequence@@#1,Short[#2]}&@@@Cases[data,{{_,2|3},_}|{{2|3,_},_}],Dividers->All,BaseStyle->{ShowStringCharacters->True},Alignment->{{Decimal,Decimal,Left}}]

TextGrid[{Sequence@@#1,#2}&@@@DeleteCases[data,{{_,2|3},_}|{{2|3,_},_}],Dividers->All,BaseStyle->{ShowStringCharacters->True},Alignment->{{Decimal,Decimal,Left}}]

GraphData

GraphClasses

GraphClassString["ChvatalGraph"]