Large Witt Graph

Author

Eric W. Weisstein
February 9, 2008

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

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

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

Embeddings

GraphData["LargeWittGraph"]

GraphData["LargeWittGraph","Graph","All"]

Construction

ExtendedBinaryGolayCode

Brouwer et al., p. 366

The large Witt graph treats the 759 vectors of the large Witt design as vertices, with an edge connecting disjoint vectors.  This is a \href{distance-regular graph} with intersection array {30,28, 24; 1, 3, 15}.

should have |(Subscript[M, 24])| = 244823040

Maybe the easiest construction is in terms of the Extended Binary Golay code.  Take the 759 code words of weight 8, and join two words when they have disjoint support. That yields this graph on 759 vertices.

Length[w8=Select[ExtendedBinaryGolayCode,Total[#]==8&]]

(LargeWitt=MakeGraph[w8,#1.#2==0&,Type->Undirected])//Timing

Degrees[LargeWitt]//Union

FastAutomorphismCount[LargeWitt]

distanceregular.org

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

Properties

?DistanceTransitiveQ

DistanceRegularQ[LargeWitt]//Timing

GraphData["ShrikhandeGraph","NotationRules"]

IntersectionArray[LargeWitt]//Timing

StronglyRegularQ[LargeWitt]//Timing

RegularParameters[LargeWitt]//Timing

IntegerSpectrum[LargeWitt]//SpectrumForm//TraditionalForm

FastHamiltonianQ[LargeWitt]//Timing

LCFCycleSearch[LargeWitt,10]//Timing

Figure

GraphPlot[LargeWitt,Method->None]

GraphData

GraphDataString

file=OpenWrite["large_witt.m"]

WriteString[file,GraphDataString[LargeWitt,
"Name"->"large Witt graph",
"StandardName"->"LargeWittGraph",
"Vertices"->None,
"Classes"->{"Integral","Regular"},
"Skip"->{"IndependenceNumber","VertexConnectivity"},
"Spectrum"->Join[Table[-15,{23}],Table[-3,{483}],Table[7,{252}],Table[30,{1}]],
Debug->True,
TimeConstraint->60
]]//Timing

Close[file]