M22 Graph

Author

Eric W. Weisstein
May 9, 2024

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

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

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

Figure

GraphicsRow[Annotate[#,{EdgeStyle->Directive[Black,AbsoluteThickness[.3]],VertexStyle->Red,VertexSize->{"Scaled",.015}}]&/@Take[GraphData["M22Graph","Graph","All"],2]]

Embeddings

<<MathWorld`Graphs`

Names

GraphData["M22Graph","StandardName"]

GraphData["M22Graph","StandardNames"]

Primary

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

All

GraphData["M22Graph","Graph","All"]//StyleGraphs[#,EdgeStyle->Directive[Black,Thin],VertexSize->{"Scaled",.02}]&

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["M22Graph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData["M22Graph","Configuration"]

GraphData["M22Graph","Graph","Configuration"]//StyleGraphs

Perspective

GraphData["M22Graph","Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData["M22Graph","Polyhedron"]

HoneycombToroidal construction

GraphData["M22Graph","NotationRules","HoneycombToroidal"]

GeneralizedPetersen

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

IGraph

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

Bilateral

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

Circular

GraphData["M22Graph","Graph","Circular"]//StyleGraphs[#,EdgeStyle->Directive[Black,Thin],VertexSize->{"Scaled",.02}]&

Planar

GraphData["M22Graph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["M22Graph","Circulant"]

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

Complement graph

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

Line graph

GraphData["M22Graph","Line"]

LineGraphQ[GraphData["M22Graph"]]//Timing

RootGraph

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

RootGraph[GraphData["M22Graph"]]

Halin

GraphData["M22Graph","Halin"]

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

Rigid

GraphData["M22Graph","Rigid"]

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

Flexible

GraphData["M22Graph","Flexible"]

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

LCF

GraphData["M22Graph","LCF"]

GraphData["M22Graph","HamiltonianCycleCount"]

GraphData["M22Graph","LCFSignature"]

GraphData["M22Graph","LCFNotations"]

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

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

LCF compute random

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

LCF compute 10^4

Tally[(lcf=LCF[GraphData["M22Graph"],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["M22Graph"],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^7

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute all

Divisors[GraphData["M22Graph","V"]]

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

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["M22Graph",".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

UnitDistance

GraphData["M22Graph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData["M22Graph","Matchstick"]

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

3D default

Graph3D[GraphData["M22Graph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["M22Graph","Polyhedral"]

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

Construction

From the Witt design

From the Witt design, 77 vectors contain 0 (0 chosen arbitrarily from 0-22). Eliminating the 0's (${0,1,5,6,7,9,11} \to {1,5,6,7,9,11}$) gives the unique size 77 \href{Steiner system} S(3,6,22) on points 1 to 22. Consider as vertices the 77 vectors ($v \in V$), with $v_j \& v_k$ adjacent if share no terms. This gives the 77-graph.

vecs=(Rest/@Take[Sort[WittDesign],77])-1;

vecs=Rest/@Select[WittDesign,Length[#]==7&&MemberQ[#,1]&];

Length[vecs]

RelationGraph[DisjointQ[##]&,vecs]

RecognizeGraph@%

Design

Code for tuples from Ed Pegg, Jr.
May 8, 2024

v=StringJoin/@(Rest/@With[{poly=x^11+x^9+x^7+x^6+x^5+x+1},
Select[
Union[Select[
Flatten[Position[CoefficientList[#,x],1]]&/@NestList[PolynomialMod[poly #,x^23-1,Modulus->2]&,poly,2047],Length[#]==7&
]
],
First[#]==1&
]
]-1/. Thread[Range[22]->CharacterRange["a","v"]])

Grid[Partition[v,11],Frame->All]

RelationGraph[DisjointQ@@Characters[{##}]&,v,VertexLabels->"Name"]

RecognizeGraph[g]

distanceregular.org

g=DistanceRegularGraph["http://www.distanceregular.org/graphdata/m22graph.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]

Forbes 11-fold from S(3,6,22) design

From Tony Forbes
Sent to Ed Pegg, Fri, 28 Dec 2007

(*
   Draw the graph M22 with 11-fold symmetry.
   
   Vertices: blocks of the S(3, 6, 22).
   Edges: A ~ B iff blocks A and B are disjoint.
*)

(*
   22 different sets of starter blocks for generating the S(3, 6, 22) design.
*)
bb1 = {{0,1,2,3,6,19}, {0,1,5,8,12,13}, {0,1,7,9,14,16}, {0,2,4,7,12,18}, {0,2,11,13,14,21}, {0,3,4,9,10,13}, {0,3,5,7,11,17}};
bb2 = {{0,1,2,3,7,18}, {0,1,4,9,12,13}, {0,1,6,8,15,17}, {0,2,4,8,14,21}, {0,2,5,10,13,15}, {0,3,4,15,16,19}, {0,7,13,17,19,21}};
bb3 = {{0,1,2,3,8,17}, {0,1,4,5,13,14}, {0,1,7,11,12,16}, {0,2,4,12,15,18}, {0,2,5,6,9,11}, {0,2,7,14,19,21}, {0,3,11,13,15,19}};
bb4 = {{0,1,2,3,9,16}, {0,1,4,5,12,15}, {0,1,6,10,13,17}, {0,2,4,8,13,14}, {0,2,5,7,10,19}, {0,2,15,17,18,21}, {0,5,9,11,13,21}};
bb5 = {{0,1,2,3,10,15}, {0,1,4,11,12,19}, {0,1,5,7,9,17}, {0,1,6,14,16,18}, {0,2,5,16,19,21}, {0,2,11,13,17,18}, {0,3,4,7,13,16}};
bb6 = {{0,1,2,3,11,14}, {0,1,4,6,8,16}, {0,1,5,10,13,18}, {0,1,7,15,17,19}, {0,2,5,7,8,21}, {0,2,6,9,13,15}, {0,3,4,10,15,21}};
bb7 = {{0,1,2,4,8,14}, {0,1,3,7,16,20}, {0,1,5,6,10,11}, {0,1,9,15,19,21}, {0,2,7,10,15,17}, {0,2,11,13,16,19}, {0,3,4,11,12,15}};
bb8 = {{0,1,2,4,12,18}, {0,1,3,14,16,17}, {0,1,5,11,19,21}, {0,1,8,10,13,15}, {0,2,6,13,17,19}, {0,3,4,7,10,19}, {0,4,9,13,14,21}};
bb9 = {{0,1,2,5,6,7}, {0,1,3,8,10,11}, {0,1,4,9,14,19}, {0,2,4,11,12,18}, {0,2,8,13,19,21}, {0,3,6,9,13,18}, {0,7,9,11,15,21}};
bb10 = {{0,1,2,5,18,21}, {0,1,3,12,14,15}, {0,1,4,13,16,17}, {0,2,4,8,14,19}, {0,2,7,9,15,16}, {0,3,7,8,17,18}, {0,5,11,15,17,19}};
bb11 = {{0,1,2,6,12,20}, {0,1,3,11,17,21}, {0,1,4,7,16,19}, {0,1,5,10,14,15}, {0,2,5,7,11,18}, {0,2,9,10,17,19}, {0,2,13,15,16,21}};
bb12 = {{0,1,2,6,17,21}, {0,1,3,5,9,15}, {0,1,4,7,10,11}, {0,1,8,14,18,20}, {0,2,7,8,13,15}, {0,2,9,11,14,19}, {0,3,4,13,14,17}};
bb13 = {{0,1,2,7,8,9}, {0,1,3,11,12,20}, {0,1,4,5,10,17}, {0,2,4,12,18,21}, {0,2,6,11,15,17}, {0,3,7,10,15,18}, {0,3,9,17,19,21}};
bb14 = {{0,1,2,7,16,21}, {0,1,3,8,15,20}, {0,1,4,6,17,19}, {0,1,5,11,12,18}, {0,1,9,10,13,14}, {0,2,4,8,11,14}, {0,3,7,9,11,19}};
bb15 = {{0,1,2,8,15,21}, {0,1,3,16,18,19}, {0,1,6,10,12,14}, {0,1,9,11,13,17}, {0,2,5,14,17,19}, {0,3,4,11,14,21}, {0,4,9,10,15,19}};
bb16 = {{0,1,2,9,10,11}, {0,1,3,4,6,7}, {0,1,5,8,15,18}, {0,2,4,8,14,17}, {0,2,5,7,13,16}, {0,3,9,13,15,17}, {0,4,11,15,16,21}};
bb17 = {{0,1,2,9,14,21}, {0,1,3,6,17,20}, {0,1,4,10,13,19}, {0,1,5,7,16,18}, {0,1,8,11,12,15}, {0,2,4,12,17,18}, {0,5,13,15,17,21}};
bb18 = {{0,1,2,10,13,21}, {0,1,3,6,8,9}, {0,1,4,5,11,16}, {0,2,4,7,8,14}, {0,2,9,11,15,18}, {0,3,5,7,15,21}, {0,4,9,12,17,21}};
bb19 = {{0,1,2,10,16,20}, {0,1,3,7,13,21}, {0,1,4,11,14,15}, {0,1,5,6,17,18}, {0,2,5,8,11,13}, {0,2,6,15,19,21}, {0,2,7,9,14,17}};
bb20 = {{0,1,2,13,14,15}, {0,1,3,4,19,20}, {0,1,5,12,16,17}, {0,2,4,9,12,18}, {0,2,8,11,17,19}, {0,3,7,8,12,15}, {0,5,7,9,13,19}};
bb21 = {{0,1,2,15,16,17}, {0,1,3,5,13,19}, {0,1,4,10,18,20}, {0,1,9,11,12,14}, {0,2,7,9,13,18}, {0,3,4,9,16,21}, {0,3,7,10,14,17}};
bb22 = {{0,1,2,17,18,19}, {0,1,3,9,14,20}, {0,1,7,11,13,15}, {0,1,8,10,12,16}, {0,2,7,9,10,21}, {0,3,4,7,12,17}, {0,3,6,10,15,19}};

(*
   Select one of the sets; the one judged 'nicest' by a small panel of lay-persons.
*)
bb = bb8;

(*
   Create the vertices of the graph. 
*)
pp = Table[7i + j, {i, 0, 10}, {j, 0, 6}];

(*
   Return the position of a vertex number p in the graph representation.
*)
ppPos[p_] := Module[{r, s},
  r = 5 + Mod[p, 7]; s = Floor[p/7];
  Return[r{Cos[2 Pi s / 11], Sin[2 Pi s / 11]}]]

(*
   Return the S(3, 6, 22) block corresponding to the vertex p.
*)
ppBlk[p_] := Mod[bb[[Mod[p, 7] + 1]] + 2 Floor[p/7], 22]

(*
   Create the edges.
*)
ee = {}; eeLine = {AbsoluteThickness[1]};
Do[b1 = ppBlk[i]; ct = 0;
   Do[b2 = ppBlk[j];
     If[ Length[Intersection[b1, b2]] == 0, ct++;
         AppendTo[ee, {i, j}];
         AppendTo[eeLine, Line[{ppPos[i], ppPos[j]}]] ],
     {j, i + 1, 76}],
   {i, 0, 75}];
   
mm22 = Graphics[{
 eeLine,
 {AbsolutePointSize[10], Red,Map[Point[ppPos[#]] &, Flatten[pp]]}
}]

MatrixForm[bb]

v=First/@Cases[mm22,_Point,{1,∞}]

e=Sort[Sort/@First/@Cases[mm22,_Line,{1,∞}]/.Thread[v->Range[Length[v]]]]

g=Graph[Range@Length@v,UndirectedEdge@@@e,VertexCoordinates->v]//StyleGraphs

RecognizeGraph@g

Wikipedia circular (but adjacent points not necessarily connected)

https://en.wikipedia.org/wiki/M22_graph

Import["https://upload.wikimedia.org/wikipedia/commons/6/61/M22_graph.svg",ImageSize->Medium]

Head[%]

g0=SVGToGraph[Import["https://upload.wikimedia.org/wikipedia/commons/6/61/M22_graph.svg","String"],ImageSize->Small]//StyleGraphs

RecognizeGraph@g0

g1=ScaleGraph[CenterGraph@g0,1/Mean[Norm/@GraphEmbedding[CenterGraph@g0]]]

vnew=Through[{Cos,Sin}[# Pi/77]]&/@Round[ArcTan@@@GraphEmbedding[g1]77/Pi]

g=Annotate[g0,VertexCoordinates->vnew]

RecognizeGraph@g

Local Higman-Sims

GraphData["M22Graph","LocalGraph","Name"]

What is actually correct

Neighborhood[HigmanSimsGraph,1,1]

v=NeighborhoodVertices[HigmanSimsGraph,1,1]

Length[v]

g1=DeleteVertices[HigmanSimsGraph,v]

RegularParameters[g1]

Factor[CharacteristicPolynomial[ToAdjacencyMatrix[g1],x]]//TraditionalForm

RecognizeGraph[g1]

What van Dam and Haemers Claim

g21=NeighborhoodSubgraph[HigmanSimsGraph,1,1]

g22=InduceSubgraph[HigmanSimsGraph,v]

$IsomorphicQ[g21,g22]

RegularParameters[g22]

RecognizeGraph[g22]

Factor[CharacteristicPolynomial[ToAdjacencyMatrix[g22],x]]//TraditionalForm

M22BipartiteDoubleGraph

BipartiteDoubleGraph[GraphData["M22Graph"]]//RecognizeGraph

GraphData

GraphClassString

GraphClassString["M22Graph"]

GraphDataString

M22

GraphDataString[M22,{"M22Graph","M22-graph","M22Graph"},TimeConstraint->60,Debug->True,Vertices->None]

BipartiteDouble

WriteString[file,GraphDataString[bpd,
"StandardName"->"M22BipartiteDoubleGraph",
"Name"->"bipartite double of the M22 graph",
"Classes"->{"DistanceRegular","Integral"},
"Vertices"->None,
Debug->True,
TimeConstraint->60
]]