Local McLaughlin Graph

Author

Eric W. Weisstein
April 29, 2025

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

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

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

Embeddings

<<MathWorld`Graphs`

"LocalMcLaughlinGraph"

Names

GraphData["LocalMcLaughlinGraph","StandardName"]

GraphData["LocalMcLaughlinGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["LocalMcLaughlinGraph"]]

Default embedding

GraphPlot[Graph[GraphData["LocalMcLaughlinGraph","VertexList"],GraphData["LocalMcLaughlinGraph","Edges"]]]

s=Sqrt[3]/2;
v={};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

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

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

GeneralizedPetersen

GraphData["LocalMcLaughlinGraph","Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData["LocalMcLaughlinGraph","Graph","IGraph"]//StyleGraphs

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData["LocalMcLaughlinGraph","Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

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

Circular construction

GraphData["LocalMcLaughlinGraph","Hamiltonian"]

GraphData["LocalMcLaughlinGraph","LCF"]

GraphData["LocalMcLaughlinGraph","HamiltonianCycleCount"]

Planar

GraphData["LocalMcLaughlinGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],"EmbeddingScheme"->1,TimeConstraint->2 86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],"EmbeddingScheme"->2,TimeConstraint->2 86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],TimeConstraint->86400])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinGraph"],TimeConstraint->2 86400])//AbsoluteTiming

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["LocalMcLaughlinGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData["LocalMcLaughlinGraph","V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData["LocalMcLaughlinGraph","V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData["LocalMcLaughlinGraph"],"CrossingNumber"->cn,RandomSeed->n]],{n,50}])//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData["LocalMcLaughlinGraph","V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData["LocalMcLaughlinGraph","V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["LocalMcLaughlinGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData["LocalMcLaughlinGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["LocalMcLaughlinGraph","Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData["LocalMcLaughlinGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["LocalMcLaughlinGraph","Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData["LocalMcLaughlinGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["LocalMcLaughlinGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData["LocalMcLaughlinGraph"],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["LocalMcLaughlinGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData["LocalMcLaughlinGraph","Circulant"]

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

Circulant construction

GraphData["LocalMcLaughlinGraph","NotationRules","Circulant"]

(ci=CirculantIndices[GraphData["LocalMcLaughlinGraph"]])//Timing

CirculantGraph1@@@ci

Cases[GraphData["LocalMcLaughlinGraph","StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData["LocalMcLaughlinGraph","ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData["LocalMcLaughlinGraph","Line"]

LineGraphQ[GraphData["LocalMcLaughlinGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["LocalMcLaughlinGraph"]]

RecognizeGraph[%]

Halin

GraphData["LocalMcLaughlinGraph","Halin"]

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

Rigid

GraphData["LocalMcLaughlinGraph","Rigid"]

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

Flexible

GraphData["LocalMcLaughlinGraph","Flexible"]

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

LCF

GraphData["LocalMcLaughlinGraph","LCF"]

GraphData["LocalMcLaughlinGraph","HamiltonianCycleCount"]

GraphData["LocalMcLaughlinGraph","LCFSignature"]

GraphData["LocalMcLaughlinGraph","LCFNotations"]

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

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

LCFNotation[%212[[1]]]

LCF compute random

Divisors[GraphData["LocalMcLaughlinGraph","V"]]

FindRandomLCFNotation[GraphData["LocalMcLaughlinGraph"],TimeConstraint->120]

FindRandomLCFNotation[GraphData["LocalMcLaughlinGraph"],TimeConstraint->3600]

FindRandomLCFNotation[GraphData["LocalMcLaughlinGraph"],TimeConstraint->86400]

LCF compute 10^4

Tally[(lcf=LCF[GraphData["LocalMcLaughlinGraph"],10^4])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

LCF compute 10^5

Tally[(lcf=LCF[GraphData["LocalMcLaughlinGraph"],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

LCF compute 10^6

Tally[(lcf=LCF[GraphData["LocalMcLaughlinGraph"],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

LCF compute 2*^6

Tally[(lcf=LCF[GraphData["LocalMcLaughlinGraph"],2*^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

LCF compute all

Divisors[GraphData["LocalMcLaughlinGraph","V"]]

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

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["LocalMcLaughlinGraph",".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

UnitDistance

GraphData["LocalMcLaughlinGraph","UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData["LocalMcLaughlinGraph"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData["LocalMcLaughlinGraph","Matchstick"]

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

3D default

Graph3D[GraphData["LocalMcLaughlinGraph","Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["LocalMcLaughlinGraph","Polyhedral"]

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

"LocalMcLaughlinComplementGraph"

Names

GraphData["LocalMcLaughlinComplementGraph","StandardName"]

GraphData["LocalMcLaughlinComplementGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embeddings

GraphDataEmbeddings[GraphData["LocalMcLaughlinComplementGraph"]]

Default embedding

GraphPlot[Graph[GraphData["LocalMcLaughlinComplementGraph","VertexList"],GraphData["LocalMcLaughlinComplementGraph","Edges"]]]

s=Sqrt[3]/2;
v={};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

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

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

GeneralizedPetersen

GraphData["LocalMcLaughlinComplementGraph","Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData["LocalMcLaughlinComplementGraph","Graph","IGraph"]//StyleGraphs

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData["LocalMcLaughlinComplementGraph","Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

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

Circular construction

GraphData["LocalMcLaughlinComplementGraph","Hamiltonian"]

GraphData["LocalMcLaughlinComplementGraph","LCF"]

GraphData["LocalMcLaughlinComplementGraph","HamiltonianCycleCount"]

Planar

GraphData["LocalMcLaughlinComplementGraph","Planar"]

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

MinimalCrossing

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

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

MinimalRectilinearCrossing construction

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["LocalMcLaughlinComplementGraph"],Automatic,All,Method->"SubgraphIsomorphism",Debug->True]]//Timing

Tally[RectilinearCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

gs

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["LocalMcLaughlinComplementGraph"],Automatic,All,Method->"Permutations",Debug->True]]//Timing

Tally[RectilinearCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

gs

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

(cn=CrossingNumber[GraphData["LocalMcLaughlinComplementGraph"],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

(cn=CrossingNumber[GraphData["LocalMcLaughlinComplementGraph"],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinComplementGraph"],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinComplementGraph"],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinComplementGraph"],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

(cn=CrossingNumber[GraphData["LocalMcLaughlinComplementGraph"],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinComplementGraph"],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinComplementGraph"],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["LocalMcLaughlinComplementGraph"],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["LocalMcLaughlinComplementGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData["LocalMcLaughlinComplementGraph","V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData["LocalMcLaughlinComplementGraph","V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData["LocalMcLaughlinComplementGraph"],"CrossingNumber"->cn,RandomSeed->n]],{n,50}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData["LocalMcLaughlinComplementGraph","V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData["LocalMcLaughlinComplementGraph","V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["LocalMcLaughlinComplementGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData["LocalMcLaughlinComplementGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["LocalMcLaughlinComplementGraph","Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData["LocalMcLaughlinComplementGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["LocalMcLaughlinComplementGraph","Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData["LocalMcLaughlinComplementGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["LocalMcLaughlinComplementGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData["LocalMcLaughlinComplementGraph"],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["LocalMcLaughlinComplementGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData["LocalMcLaughlinComplementGraph","Circulant"]

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

Circulant construction

GraphData["LocalMcLaughlinComplementGraph","NotationRules","Circulant"]

(ci=CirculantIndices[GraphData["LocalMcLaughlinComplementGraph"]])//Timing

CirculantGraph1@@@ci

Cases[GraphData["LocalMcLaughlinComplementGraph","StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData["LocalMcLaughlinComplementGraph","ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData["LocalMcLaughlinComplementGraph","Line"]

LineGraphQ[GraphData["LocalMcLaughlinComplementGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["LocalMcLaughlinComplementGraph"]]

RecognizeGraph[%]

Halin

GraphData["LocalMcLaughlinComplementGraph","Halin"]

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

Rigid

GraphData["LocalMcLaughlinComplementGraph","Rigid"]

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

Flexible

GraphData["LocalMcLaughlinComplementGraph","Flexible"]

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

LCF

GraphData["LocalMcLaughlinComplementGraph","LCF"]

GraphData["LocalMcLaughlinComplementGraph","HamiltonianCycleCount"]

GraphData["LocalMcLaughlinComplementGraph","LCFSignature"]

GraphData["LocalMcLaughlinComplementGraph","LCFNotations"]

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

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

LCF compute random

FindRandomLCFNotation[GraphData["LocalMcLaughlinComplementGraph"],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData["LocalMcLaughlinComplementGraph"],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{"LocalMcLaughlinComplementGraph",{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData["LocalMcLaughlinComplementGraph","V"]]

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

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["LocalMcLaughlinComplementGraph",".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

UnitDistance

GraphData["LocalMcLaughlinComplementGraph","UnitDistance"]

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

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

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData["LocalMcLaughlinComplementGraph"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData["LocalMcLaughlinComplementGraph","Matchstick"]

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

3D default

Graph3D[GraphData["LocalMcLaughlinComplementGraph","Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["LocalMcLaughlinComplementGraph","Polyhedral"]

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

Construction

C.f. Godsil and Royle, p. 232

GraphData["McLaughlinGraph","VertexTransitive"]

RecognizeGraph[g=VertexDelete[GraphData["McLaughlinGraph"],VertexList[NeighborhoodGraph[GraphData["McLaughlinGraph"],1]]]]

RecognizeGraph[g]

Tally[RecognizeGraph[VertexDelete[GraphData["McLaughlinGraph"],VertexList[NeighborhoodGraph[GraphData["McLaughlinGraph"],#]]]]&/@GraphData["McLaughlinGraph","VertexList"]]

VertexCount[g]

RegularParameters[g]

Factor[CharacteristicPolynomial[AdjacencyMatrix[g],x]]//TraditionalForm

Not the local graph of the McLaughlinGraph

LocalGraph[GraphData["McLaughlinGraph"]]//RecognizeGraph

RecognizeGraph@%

EgoGraph[GraphData["McLaughlinGraph"],1]//RecognizeGraph

dist1=Position[Normal[GraphDistanceMatrix[GraphData["McLaughlinGraph"]][[1]]],1]//Flatten

Subgraph[GraphData["McLaughlinGraph"],dist1]//RecognizeGraph

Distance-2 graph from a

dist2=Position[Normal[GraphDistanceMatrix[GraphData["McLaughlinGraph"]][[1]]],2]//Flatten

Subgraph[GraphData["McLaughlinGraph"],dist2]//RecognizeGraph

dist3=Position[Normal[GraphDistanceMatrix[GraphData["McLaughlinGraph"]][[1]]],3]//Flatten

Properties

MinimumVertexColoring

coloring=GraphData["LocalMcLaughlinGraph","MinimumVertexColoring"]

VertexColoringQ[GraphData["LocalMcLaughlinGraph"],coloring]

Max[coloring]

GraphData["LocalMcLaughlinGraph","ChromaticNumber"]

(coloring2=FindVertexColoring[GraphData["LocalMcLaughlinGraph"]])//Timing

Max[coloring2]

Construction (non-minimal)

-------- Original Message --------
Subject: LocalMcLaughlin: new small coloring
Date: Wed, 14 Dec 2011 13:02:28 -0600
From: Stan Wagon <wagon@macalester.edu>
To: wendym@csc.uvic.ca, Eric Weisstein <eww@wolfram.com>,        Rob Pratt <Rob.Pratt@sas.com>

Eric computed for me, in half a minute, all the size 15 inde. sets in the LocalMcLaughlin graph. 40000+ of them. And I had the 2200 size-21 ones. 

So here is what I did:

I picked one of the large ones to be in the coloring.
Then I looked only at size-21 sets disjoints from that one and also size-15 sets disjoint from that one. That gave me 11169 sets. 

I ran ISByILP, which is my raw combining of inde. sets by ILP and took merely 153 seconds to find a 10 coloring. I then had to add back to it the first 21-coloring, so in all I have an 11-coloring of this graph.

I realize that some of the 15-sized sets that are not disjoint from the chosen 21-set could be relevant, so this does not disprove a 10-coloring. But it seems as if some combination of thinking and computing might be able to do that. Wendy has disproved 9-coloring...  so I believe chi for this graph is either 10 or 11.

Here is the 11-coloring. 

{1, 4, 4, 3, 3, 7, 1, 2, 3, 2, 1, 4, 4, 10, 1, 1, 1, 2, 7, 3, 2, 11, 11, 11, \
11, 11, 2, 3, 3, 3, 9, 7, 11, 2, 2, 10, 2, 11, 1, 9, 6, 8, 1, 7, 10, 10, 4, \
8, 5, 10, 7, 4, 5, 4, 5, 1, 10, 6, 3, 5, 4, 5, 4, 5, 4, 3, 6, 10, 6, 11, 2, \
10, 6, 1, 10, 7, 2, 11, 4, 4, 5, 2, 7, 7, 3, 5, 1, 3, 10, 10, 10, 5, 1, 2, 7, \
5, 9, 8, 2, 1, 9, 6, 7, 8, 9, 4, 5, 2, 5, 9, 11, 6, 2, 8, 2, 3, 11, 4, 3, 11, \
10, 8, 3, 9, 9, 6, 6, 11, 8, 8, 8, 3, 11, 7, 1, 3, 6, 11, 1, 7, 11, 5, 1, 9, \
2, 1, 1, 11, 6, 7, 1, 7, 11, 7, 1, 4, 10, 11, 1, 4, 11, 11}

Here it is as lists.

{{1, 7, 11, 15, 16, 17, 39, 43, 56, 74, 87, 93, 100, 135, 139, 143, 146, 147, 
  151, 155, 159}, {8, 10, 18, 21, 27, 34, 35, 37, 71, 77, 82, 94, 99, 108, 
  113, 115, 145}, {4, 5, 9, 20, 28, 29, 30, 59, 66, 85, 88, 116, 119, 123, 
  132, 136}, {2, 3, 12, 13, 47, 52, 54, 61, 63, 65, 79, 80, 106, 118, 156, 
  160}, {49, 53, 55, 60, 62, 64, 81, 86, 92, 96, 107, 109, 142}, {41, 58, 67, 
  69, 73, 102, 112, 126, 127, 137, 149}, {6, 19, 32, 44, 51, 76, 83, 84, 95, 
  103, 134, 140, 150, 152, 154}, {42, 48, 98, 104, 114, 122, 129, 130, 
  131}, {31, 40, 97, 101, 105, 110, 124, 125, 144}, {14, 36, 45, 46, 50, 57, 
  68, 72, 75, 89, 90, 91, 121, 157}, {22, 23, 24, 25, 26, 33, 38, 70, 78, 111,
   117, 120, 128, 133, 138, 141, 148, 153, 158, 161, 162}}

I wonder if Rob can attack directly the set of all size-21 and all size-15s as an ILP?  But if not, there must be some good thinning that can be done that would disprove 10 (or find one)

Eric:   For the remaining ones the ind sets might be too large....

coloring={1,4,4,3,3,7,1,2,3,2,1,4,4,10,1,1,1,2,7,3,2,11,11,11,11,11,2,3,3,3,9,7,11,2,2,10,2,11,1,9,6,8,1,7,10,10,4,8,5,10,7,4,5,4,5,1,10,6,3,5,4,5,4,5,4,3,6,10,6,11,2,10,6,1,10,7,2,11,4,4,5,2,7,7,3,5,1,3,10,10,10,5,1,2,7,5,9,8,2,1,9,6,7,8,9,4,5,2,5,9,11,6,2,8,2,3,11,4,3,11,10,8,3,9,9,6,6,11,8,8,8,3,11,7,1,3,6,11,1,7,11,5,1,9,2,1,1,11,6,7,1,7,11,7,1,4,10,11,1,4,11,11};

VertexColoringQ[GraphData["LocalMcLaughlinGraph"],coloring]

GraphData

GraphDataString

Print[GraphDataString[g,
"Name"->"local McLaughlin graph",
"StandardName"->"LocalMcLaughlinGraph",
"Classes"->{"DeterminedBySpectrum"},
TimeConstraint->120,
Debug->True
]]