Distance-Regular Graph

Author

Eric W. Weisstein
November 21, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Distance-RegularGraph.nb.

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

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

Counts

Connected

A241814

Total[Boole[Get[#]]]&/@FileNames["*.m",FileNameJoin[{$GraphDataDirectory,"Nodes","DistanceRegular"}]]

Length/@Table[GraphData["DistanceRegular",n],{n,10}]

Table[Count[GraphData[n],_?(DistanceRegularGraphQ[GraphData[#]]&)],{n,7}]//Timing

Enumeration

All

SortBy[GraphData["DistanceRegular"],GraphData[#,"V"]&]

Cubic

Brouwer et al., p. 221

TextGrid[cdr=Sort[{GraphData[#,"V"],GraphData[#,"Name"],GraphData[#,"IntersectionArray"]}&/@GraphData[{"Cubic","DistanceRegular","Connected"}]],Dividers->All]

GraphicsGrid[Partition[Show[GraphData[#],PlotLabel->TextCell[GraphData[#,"Name"],PageWidth->120,TextAlignment->Center],BaseStyle->FontSlant->Italic]&/@SortBy[GraphData[{"Cubic","DistanceRegular"}],GraphData[#,"V"]&],4,4,{1,1},{}]/.AbsolutePointSize[_]:>AbsolutePointSize[4],ImageSize->500,Alignment->Top]

Quartic

http://emis.icm.edu.pl/journals/JACO/Volume10_1/k874104356256466.fulltext.pdf

Journal of Algebraic Combinatorics 10 (1999), 5–24, 1999
The Distance-Regular Graphs of Valency Four
A.E. BROUWER aeb@win.tue.nl J.H. KOOLEN

<<MathWorld`Graphs`

TextGrid[MapIndexed[
Prepend[#,#2[[1]]]&,
Sort[Append[GraphData[#,{"VertexCount","Diameter","#","Notation","IntersectionArray"}],GraphData[#,"Spectrum"]//SpectrumForm]&/@GraphData[{"Connected","DistanceRegular","Quartic"}]]],Dividers->All,Alignment->{{Decimal,Decimal,{Left}}}]

Noncubic

TextGrid[cdr=Sort[{GraphData[#,"V"],GraphData[#,"Name"],GraphData[#,"IntersectionArray"]}&/@Select[GraphData[{"Connected","DistanceRegular"}],GraphData[#,"MaximumVertexDegree"]>3&]],Dividers->All]

Non-geometric smallest eigenvalue ≥ -3, diameter ≥ 3

https://arxiv.org/pdf/2311.09001.pdf

Select[GraphData["DistanceRegular"],GraphData[#,"IntersectionArray"]==={{9,6,1},{1,2,9}}&]

Select[GraphData["DistanceRegular"],GraphData[#,"IntersectionArray"]==={{15,10,1},{1,2,15}}&]

Select[GraphData["DistanceRegular"],GraphData[#,"IntersectionArray"]==={{18,12,1},{1,2,18}}&]

theorem1=Select[GraphData[{"Connected","DistanceRegular"}],GraphData[#,"Diameter"]≥3&&Min[GraphData[#,"Spectrum"]]≥-3&];

special={{"Odd",4},"SylvesterGraph","HoffmanSingletonMinusStarGraph","PerkelGraph",{"CompleteGraphSymplecticCover",{9,7}},"CoxeterGraph","DodecahedralGraph","BiggsSmithGraph","WellsGraph","IcosahedralGraph",(*"DoroGraph"*)"HallGraph",{"HalvedCube",6},"GossetGraph",{"HalvedCube",7},"KleinGraph24"};

Complement[special,theorem1]

Complement[theorem1,special]

GraphData["DoroGraph","Diameter"]

GraphData["DoroGraph","DistanceRegular"]

GraphData["DoroGraph","IntersectionArray"]

Select[GraphData["DistanceRegular"],GraphData[#,"IntersectionArray"]==={{10,6,4},{1,2,5}}&]

GraphData["DoroGraph","Spectrum"]//Min

TextGrid[DeleteCases[
table=Sort[{GraphData[#,"V"],#,GraphData[#,"Geometric"],GraphData[#,"IntersectionArray"]}&/@theorem1],
{_,_,True,_}
],Dividers->All]

These should be false:

todo=Cases[table,{_,gn_,_Missing,_}:>gn]

Disconnected

https://en.wikipedia.org/wiki/Distance-regular_graph

A distance-regular graph is disconnected if and only if it is a disjoint union of cospectral distance-regular graphs.

Select[{#,GraphData[#,"ConnectedComponents","Name"]}&/@GraphData[{"Disconnected","DistanceRegular"}],UnsameQ@@#[[2]]&]

Sort[{GraphData[#[[1]],"V"],#}&/@Select[SplitBy[SortBy[GraphData[#,{"Spectrum","#"}]&/@GraphData[{"DistanceRegular","Connected"}],First],First][[All,All,2]],Length[#]>1&]]

g=GraphDisjointUnion@@GraphData/@{"ShrikhandeGraph",{"Rook",{4,4}}}

IGDistanceRegularQ[g]

IGIntersectionArray[g]

DistanceRegularGraphQ[g]

IntersectionArray[g]

distanceregular.org

<<MathWorld`Graphs`

DateString[]

OneOrList[op_,expr_]:=Which[
MatchQ[expr,_Graph],
	op[expr],
MatchQ[expr,{_Graph..}],
	op/@expr,
True,
	$Failed
]

adjacency matrix

<<MathWorld`Graphs`

am=Select[Import["https://www.distanceregular.org/graphdata/","Hyperlinks"],StringMatchQ[__~~".am"~~EndOfString]]

Length[am]

am[[1]]

i=0;
graphs=Monitor[{
i++;
g=DistanceRegularGraph[gn=#];
OneOrList[VertexCount,g],
r=OneOrList[RecognizeGraph,g],
OneOrList[Identity,g],
Hyperlink[gn]
}&/@Take[am,All],
Column[{gn,r,ProgressIndicator[i,{1,Length[am]}]}]];//Timing//AbsoluteTiming

TextGrid[Sort[graphs],Dividers->All]

Failed

Select[graphs,!FreeQ[#,$Failed]&]

Not in GraphData

TextGrid[Select[Sort[graphs],!FreeQ[#,{}]&],Dividers->All]

cvs

csv=Select[Import["https://www.distanceregular.org/graphdata/","Hyperlinks"],StringMatchQ[__~~".csv"]]

Length[csv]

i=0;
graphs=Monitor[{
i++;
g=DistanceRegularGraph[gn=#];
OneOrList[VertexCount,g],
r=OneOrList[RecognizeGraph,g],
OneOrList[Identity,g],
Hyperlink[gn]
}&/@Take[csv,All],
Column[{gn,r,ProgressIndicator[i,{1,Length[csv]}]}]];//Timing//AbsoluteTiming

TextGrid[Sort[graphs],Dividers->All]

Failed

Select[graphs,!FreeQ[#,$Failed]&]

Not in GraphData

TextGrid[Select[Sort[graphs],!FreeQ[#,{}]&],Dividers->All]

Constructions

PGammaU(3,4) on nonisotropic points

(208 vertices, Brouwer etal., p. 225)

gap> LoadPackage("Grape");;
gap> G:=PrimitiveGroup(208,1);
PSU(3, 4)
gap> NrMovedPoints(G);
208
gap> S:=Stabilizer(G,1);
<permutation group of size 300 with 2 generators>
gap> OrbitLengths(S);
[ 60, 60, 75, 12 ]....
gap> gamma:=NullGraph(G);
gap> Orbits(S)[4];
[ 8, 34, 180, 17, 38, 109, 138, 124, 31, 19, 162, 176 ]
gap> AddEdgeOrbit(gamma,[1,8]);
gap> IsDistanceRegular(gamma);
true
gap> GlobalParameters(gamma);
[ [ 0, 0, 12 ], [ 1, 1, 10 ], [ 1, 6, 5 ], [ 8, 4, 0 ] ]
PrintTo("~/PGammaU3,4.gap",UndirectedEdges( gamma ));

Algorithms

IGraph/M

data=Monitor[{g=#,GraphData[#,"DistanceRegular"],IGDistanceRegularQ[GraphData[#]]}&/@GraphData[All],g];//AbsoluteTiming

DeleteCases[data,{_,x_,x_}]

Graphs.m

data=Monitor[{g=#,GraphData[#,"DistanceRegular"],TimeConstrained[DistanceRegularGraphQ[GraphData[#]],60]}&/@GraphData[All],g];//AbsoluteTiming

DeleteCases[data,{_,x_,x_}]