Leonard Graph

Author

Eric W. Weisstein
October 18, 2018

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

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

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

Embeddings

GraphData["LeonardGraph","Graph","All"]

Construction

GAP

Date: Sun, 14 Jun 2009 15:43:10 +0200                                                                     
From: Andries E. Brouwer

The group is M12.2 on 288 points, valency 12.
The graph is bipartite, and the group is not transitive.
More work. First make one half.

gap> ga:=PrimitiveGroup(144,4);
M_12.2
gap> gamma:=NullGraph(ga);
gap> sga:=Stabilizer(ga,1);
<permutation group of size 1320 with 3 generators>
gap> OrbitLengths(sga);
[ 55, 66, 22 ]
gap> Orbits(sga)[2][1];
6
gap> AddEdgeOrbit(gamma,[1,6]);
gap> Diameter(gamma);
2
gap> IsDistanceRegular(gamma);
true
gap> GlobalParameters(gamma);
[ [ 0, 0, 66 ], [ 1, 30, 35 ], [ 30, 36, 0 ] ]

That was the halved graph. Find its 12-cliques.

gap> C:=CompleteSubgraphsOfGivenSize(gamma,12,2);
[ [ 1, 6, 18, 33, 38, 64, 68, 72, 98, 128, 132, 142 ] ]
gap> C12:=C[1];
[ 1, 6, 18, 33, 38, 64, 68, 72, 98, 128, 132, 142 ]
gap> O12:=Orbit(ga,C12,OnSets);;
gap> Size(O12);
144

It is easiest to have all vertices of the same type.  But right now we have points and sets. Convert the points into singleton sets.

gap> C1:=[1];;
gap> O1:=Orbit(ga,C1,OnSets);;
gap> Size(O1);
144
gap> O:=Union(O1,O12);;
gap> Size(O);
288

OK. These are the 288 vertices of the graph: 144 singletons, and 144 12-sets.

gap> delta:=Graph(ga,O,OnSets,function(x,y) return x<>y and (IsSubset(x,y) or IsSubset(y,x)); end, true);;
gap> Diameter(delta);
4
gap> IsDistanceRegular(delta);
true
gap> GlobalParameters(delta);
[ [ 0, 0, 12 ], [ 1, 0, 11 ], [ 2, 0, 10 ], [ 5, 0, 7 ], [ 12, 0, 0 ] ]
PrintTo("~/leon.gap",UndirectedEdges( delta ));

That was the Leonard graph.

e=ReadGAPEdgeList["~/leon.gap"]

g=FromUnorderedPairs[e]

distanceregular.org

g=DistanceRegularGraph["http://www.distanceregular.org/graphdata/leonard.am"]

RecognizeGraph[g]

VertexCount[g]

GraphDiameter[g]//Timing

RegularParameters[g]//Timing

DistanceRegularGraphQ[g]//Timing

IntersectionArray[g]//Timing

IntegerSpectrum[g]//SpectrumForm

GroupOrder[GraphAutomorphismGroup[g]]

HamiltonianGraphQ[g]

GraphData

GraphDataString

WriteString[file,
GraphDataString[g,
"StandardName"->"LeonardGraph",
"Name"->"Leonard graph",
"Information"->{"LeonardGraph"},
"Skip"->{"ChromaticPolynomial","ClawFree","IndependencePolynomial","MatchingPolynomial"},
"Classes"->{"DistanceRegular","Integral"},
"NotationRules"->{"DistanceRegular"->{{12,11,10,7},{1,2,5,12}}},
Vertices->None,
Debug->True,
TimeConstraint->60
]]//Timing

Halved Leonard graphs

Construction

Halved

halved=HalvedGraphs[GraphData["LeonardGraph"]]

RecognizeGraph/@halved

IsomorphicGraphQ@@halved

VertexCount/@halved

Tally/@IntegerSpectrum/@halved

DistanceRegularGraphQ/@halved

GraphData

file=OpenWrite["~/halvedleonard.m"]

MapIndexed[WriteString[file,GraphDataString[g,
"StandardName"->{"HalvedLeonard",#2[[1]]},
"Name"->"halved Leonard graph "<>ToString[#2[[1]]],
"Embeddings"->None,
"Information"->None,
"Classes"->{"DistanceRegular","Noncirculant","Nongrid"},
Debug->True,
TimeConstraint->10]]&,halved]

Close[file]