Hall-Janko Graph

Author

Eric W. Weisstein
October 18, 2018

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Hall-JankoGraph.nb.

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

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

Embeddings

Default

GraphData["HallJankoGraph"]//StyleGraphs[#,System`EdgeStyle->Directive[GrayLevel[.3],AbsoluteThickness[.3]],VertexSize->.5]&

All

GraphData["HallJankoGraph","Graph","All"]

LCF

GraphData["HallJankoGraph","LCFSignature"]

GraphData["HallJankoGraph","LCFNotations"]

GraphData["HallJankoGraph","|HC|"]

Wikipedia

g=SVGToGraph[Import["http://upload.wikimedia.org/wikipedia/commons/5/5d/Hall_janko_graph.svg","XML"]]

RecognizeGraph[g]

GraphPlot[g,Method->None,"EdgeColor"->Thickness[.0003],ImageSize->300]

ToCommonEdges[g,Graph["HallJankoGraph"]]

GetGraphData["HallJankoGraph","File"]

Construction

Steiner Quadruple System 10

The Foster graph is an antipodal 3-cover of the Levi graph, which is the graph of Steiner Quadruple System 10, sqs10, adjacent when disjoint.

The 100 vertices of Γ are the 90 vertices of F and the 10 points of the point set X of sqs10. 

X is a 10-coclique in Γ.  (A coclique in a graph is a set of vertices with no pair joined.)
Two vertices of F are adjacent in Γ when they have distance 3, 6, 7 or 8 in F.  (part 1)
A point x in X is adjacent to y in F when x is in the block π(y). (part 2)

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

g = Flatten[Table[If[Intersection[sqs10[[a]],sqs10[[b]]]=={},{a,b},Sequence@@{}],{a,29},{b,a+1,30}],1];

ShowGraph[FromUnorderedPairs[g]]

LeviFoster = FromUnorderedPairs[GraphData["F090A","EdgeIndices"]/.Thread[Flatten[Table[{n,n+30,n+60},{n,1,30}]]->RotateRight[Range[90],-22]]]

ShowGraph[LeviFoster,VertexStyle->Disk[0.02]]

Two vertices of F are adjacent in Γ when they have distance 3, 6, 7 or 8 in F.  (part 1)
A point x in X is adjacent to y in F when x is in the block π(y). (part 2)

part1 =Flatten[Table[If[Intersection[{Length[ShortestPath[LeviFoster,a,b]]},{3, 6, 7 , 8}+1]≠ {},{a,b},Sequence@@{}],{a,1,89},{b,a+1,90}],1];

part2 = Flatten[Table[{n,#}&/@(sqs10[[Ceiling[n/3]]]+90),{n,1,90}],1];

HallJanko = FromUnorderedPairs[Flatten[{part1,part2/.Thread[Range[90]->RotateRight[Range[90],89]]},1]]

distanceregular.org

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

GraphClassString

GraphClassString[{"HallJankoGraph"}]

GraphDataString

GraphDataString[HallJanko,
"Name"->"Hall-Janko graph",
"StandardName"->"HallJankoGraph",
"Vertices"->None,
TimeConstraint->60,
Debug->True
]