Distance-Regular Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A connected graph G is distance-regular if for any vertices x and y of G and any integers i,j=0, 1, ...d (where d is the graph diameter), the number of vertices at distance i from x and distance j from y depends only on i, j, and the graph distance between x and y, independently of the choice of x and y.

In particular, a distance-regular graph is a graph for which there exist integers b_i,c_i,i=0,...,d such that for any two vertices x,y in G and distance i=d(x,y), there are exactly c_i neighbors of y in G_(i-1)(x) and b_i neighbors of y in G_(i+1)(x), where G_i(x) is the set of vertices y of G with d(x,y)=i (Brouwer et al. 1989, p. 434). The array of integers characterizing a distance-regular graph is known as its intersection array.

Distance regularity of a graph G may be checked in the GRAPE package in GAP using the function IsDistanceRegular(G).

A disconnected graph is distance-regular iff it is a disjoint union of cospectral distance-regular graphs.

A deep theorem of Fiol and Garriga (1997) states that a graph is distance-regular iff for every vertex, the number of vertices at a distance d (where d+1 is the number of distinct graph eigenvalues) equals an expression in terms of the spectrum (van Dam and Haemers 2003).

Classes of distance-regular graphs include complete graphs K_n, complete bipartite graphs K_(n,n), complete tripartite graphs K_(n,n,n), cycle graphs C_n (Brouwer et al. 1989, p. 1), empty graphs K^__n (trivially), Hadamard graphs (Brouwer et al. 1989, p. 19), hypercube graphs Q_n (Biggs 1993, p. 161), Kneser graphs K(n,2), ladder rung graphs nP_2 (trivially), odd graphs O_n (Biggs 1993, p. 161), and Platonic graphs (Brouwer et al. 1989, p. 1).

A distance-regular graph with graph diameter d=2 is a strongly regular graph (Biggs 1993, p. 159), and connected distance-regular graphs are conformally rigid (Steinerberger and Thomas 2025).

Every distance-transitive graph is distance-regular, but the converse does not necessarily hold, as first shown by Adel'son-Vel'skii et al. (1969; Brouwer et al. 1989, p. 136). The smallest distance-regular graph that is not distance-transitive is the Shrikhande graph (Brouwer et al. 1989, p. 136) on 16 nodes.

DistanceRegularCubic

All cubic distance-regular graphs are known (Biggs et al. 1986; Brouwer et al. 1989, p. 221; Royle), as illustrated above and summarized in the following table.

n graph intersection array

4 tetrahedral graph {3;1}

6 utility graph {3,2;1,3}

8 cubical graph {3,2,1;1,2,3}

10 Petersen graph {3,2;1,1}

14 Heawood graph {3,2,2;1,1,3}

18 Pappus graph {3,2,2,1;1,1,2,3}

20 Desargues graph {3,2,2,1,1;1,1,2,2,3}

20 dodecahedral graph {3,2,1,1,1;1,1,1,2,3}

28 Coxeter graph {3,2,2,1;1,1,1,2}

30 Tutte 8-cage {3,2,2,2;1,1,1,3}

90 Foster graph {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}

102 Biggs-Smith graph {3,2,2,2,1,1,1;1,1,1,1,1,1,3}

126 Tutte 12-cage {3,2,2,2,2,2;1,1,1,1,1,3}

All quartic distance-regular graphs are known (Brouwer and Koolen 1999) except that there is one graph on the list (the generalized hexagon of order 3) which is not yet known to be uniquely determined by its intersection array (Koolen et al. 2023). In particular, any distance-regular graph of valency 4 has one of the 17 intersection arrays listed below (and hence is one of the 16 graphs described, or is the point-line incidence graph a generalized hexagon of order 3)

No. v d graph intersection array graph spectrum

1. 5 1 pentatope graph K_5 {4;1} 4^1(âˆ’1)4

2. 6 2 cocktail party graph K_(3×2) {4,1;1,4} 4^10^3(-2)^2

3. 8 2 complete bipartite graph K_(4,4) {4,3;1,4} +/-4^10^6

4. 9 2 generalized quadrangle GQ(2,1) {4,2;1,2} 4^11^4(-2)^4

5. 10 3 crown graph K_2 square K_5^_ {4,3,1;1,3,4} +/-(4^11^4)

6. 14 3 nonincidence graph of PG(2,2) Qt31 {4,3,2;1,2,4} +/-(4^1sqrt(2)^6)

7. 15 3 line graph of the Petersen graph L(P) {4,2,1;1,1,4} 4^12^5(-1)^4(-2)^5

8. 16 4 hypercube graph Q_4 {4,3,2,1;1,2,3,4} +/-(4^12^4)0^6

9. 21 3 generalized hexagon GH(2,1) {4,2,2;1,1,2} 4^1(1+/-sqrt(2))^6(-2)^8

10. 26 3 incidence graph of PG(2,3) {4,3,3;1,1,4} +/-(4^1sqrt(3)^(12))

11. 32 4 incidence graph of AG(4,4) minus parallel class {4,3,3,1;1,1,3,4} +/-(4^12^(12))0^6

12. 35 3 odd graph O_4 {4,3,3;1,1,2} 4^12^(14)(-1)^(14)(-3)^6

13. 45 4 generalized octagon GO(2,1) {4,2,2,2;1,1,1,2} 4^13^91^(10)(-1)^9(-2)^(16)

14. 70 7 Danzer graph {4,3,3,2,2,1,1;1,1,2,2,3,3,4} +/-(4^13^62^(14)1^(14))

15. 80 4 (4,8)-cage graph {4,3,3,3;1,1,1,4} +/-(4^1sqrt(6)^(24))0^(30)

16. 189 6 generalized dodecagon GD(2,1) {4,2,2,2,2,2;1,1,1,1,1,2} 4^1(1+/-sqrt(6))^(21)(1+/-sqrt(2))^(27)1^(28)(-2)^(64)

17. 728 6 (4,12)-cage graph {4,3,3,3,3,3;1,1,1,1,1,4} +/-(4^13^(104)sqrt(3)^(168))0^(182)

Koolen et al. (2023) enumerate 18 cases of non-geometric distance-regular graphs of diameter at least 3 with smallest graph eigenvalue at least -3, as summarized in the following table.

case graph intersection array

(a) odd graph O_4 {3,3,3;1,1,2}

(b) Sylvester graph {5,4,2;1,1,4}

(d) Perkel graph {6,5,2;1,1,3}

(e) symplectic 7-cover of the complete graph K_9 {8,6,1;1,1,8}

(f) Coxeter graph {3,2,2,1;1,1,1,2}

(g) dodecahedral graph {3,2,1,1,1;1,1,1,2,3}

(h) Biggs-Smith graph {3,2,2,2,1,1,1;1,1,1,1,1,1,3}

(i) Wells graph {5,4,1,1;1,1,4,5}

(j) icosahedral graph {5,2,1;1,2,5}

(k) Hall graph {10,6,4;1,2,5}

(l) halved cube graph Q_6/2 {15,6,1;1,6,15}

(m) Gosset graph {27,10,1;1,10,27}

(n) halved cube graph Q_7/2 {21,10,3;1,6,15}

(o) 24-Klein graph {7,4,1;1,2,7}

(p) exactly two distance-regular graphs {9,6,1;1,2,9}

(q) more than one distance-regular graph {15,10,1;1,2,15}

(r) putative distance-regular graph {18,12,1;1,2,18}

Note that the odd n-cycle graphs with n>3 (which satisfy all the given criteria) are apparently silently omitted.

The following table summarizes some known distance-regular graphs, excluding a number of named families.

n graph intersection array

5 pentatope graph {4;1}

6 octahedral graph {4,1;1,4}

8 16-cell graph {6,1;1,6}

9 generalized quadrangle (2,1) {4,2;1,2}

12 icosahedral graph {5,2,1;1,2,5}

14 quartic vertex-transitive graph Qt31 {4,3,2;1,2,4}

15 generalized quadrangle (2,2) {6,4;1,3}

15 quartic vertex-transitive graph Qt39 {4,2,1;1,1,4}

16 Clebsch graph {5,4;1,2}

16 Shrikhande graph {6,3;1,2}

16 tesseract graph {4,3,2,1;1,2,3,4}

21 (7,2)-Kneser graph {10,6;1,6}

21 generalized hexagon (2,1) {4,2,2;1,1,2}

22 (11,5,2)-incidence graph {5,4,3;1,2,5}

22 (11,6,3)-incidence graph {6,5,3;1,3,6}

24 24-Klein graph {7,4,1;1,2,7}

25 25-Paulus graphs {12,6;1,6}

26 (13,9,6)-incidence graph {9,8,3;1,6,9}

26 26-Paulus graphs {10,6;1,4}

26 (29,14,6,7)-strongly regular graphs (40) {14,7;1,7}

26 (4,6)-cage {4,3,3;1,1,4}

27 generalized quadrangle (2,4) {10,8;1,5}

27 generalized quadrangle (2,4) minus spread 1 {8,6,1,;1,3,8}

27 generalized quadrangle (2,4) minus spread 2 {8,6,1,;1,3,8}

27 Schläfli graph {16,5;1,8}

28 Chang graphs {12,5;1,4}

28 (8,2)-Kneser graph {15,8;1,10}

28 locally 13-Paley graph {13,6,1;1,6,13}

30 (15,7,3)-incidence graph {7,6,4;1,3,7}

32 (8,1)-Hadamard graph {8,7,4,1;1,4,7,8}

32 Kummer graph {6,5,4;1,2,6}

32 Wells graph {5,4,1,1;1,1,4,5}

35 Grassmann graph J_2(4,2) {18,8;1,9}

35 4-odd graph {4,3,3;1,1,2}

36 hexacode graph {6,5,4,1;1,2,5,6}

36 (9,2)-Kneser graph {21,10;1,15}

36 Sylvester graph {5,4,2;1,1,4}

38 (19,9,4)-incidence graph {9,8,5;1,4,9}

42 (21,16,12)-incidence graph {16,15,4;1,12,16}

42 (5,6)-cage {5,4,4;1,1,5}

42 Hoffman-Singleton graph minus star {6,5,1;1,1,6}

45 (10,2)-Kneser graph {28,12;1,21}

45 generalized octagon (2,1) {4,2,2,2;1,1,1,2}

45 halved Foster graph {6,4,2,1;1,1,4,6}

46 (23,11,5)-incidence graph {11,10,6;1,5,11}

48 (12,1)-Hadamard graph {12,11,6,1;1,6,11;12}

50 Hoffman-Singleton graph {7,6;1,1}

50 Hoffman-Singleton graph complement {42,6;1,36}

52 generalized hexagon (3,1) {6,3,3;1,1,2}

55 (11,2)-Kneser graph {36,14;1,28}

56 distance 2-graph of the Gosset graph {27,16,1;1,16,27}

56 Gewirtz graph {10,9;1,2}

56 Gosset graph {27,10,1;1,10,27}

57 Perkel graph {6,5,2;1,1,3}

62 (31,15,7)-incidence graph {15,14,8;1,7,15}

62 (31,25,20)-incidence graph {25,24,5;1,20,25}

62 (6,6)-cage {6,5,5;1,1,6}

63 (63,32,16,16)-strongly regular graph {32,15;1,16}

63 symplectic 7-cover of K_9 {8,6,1;1,1,8}

64 (1,1)-Doob graph {9,6,3;1,2,3}

64 64-cyclotomic graph {21,12;1,6}

65 Hall graph {10,6,4;1,2,5}

66 (12,2)-Kneser graph {45,16;1,36}

70 (35,17,8)-incidence graph {17,16,9;1,8,17}

70 (7,3)-bipartite Kneser graph {4,3,3,2,2,1,1;1,1,2,2,3,3,4}

70 (8,4)-Johnson graph {16,9,4,1;1,4,9,16}

72 Suetake graph {12,11,8,1;1,4,11,12}

74 (37,9,2)-incidence graph {9,8,7;1,2,9}

77 M22 graph {16,15;1,4}

78 (13,2)-Kneser graph {55,18;1,45}

80 (40,13,4)-incidence graph {13,12,9;1,4,13}

80 (4,8)-cage {4,3,3,3;1,1,1,4}

81 Brouwer-Haemers graph {20,18;1,6}

91 (14,2)-Kneser graph {66,20;1,55}

94 (47,23,11)-incidence graph {23,22,12;1,11,23}

100 bipartite double of the Hoffman-Singleton graph {7,6,6,1,1;1,1,6,6,7}

100 cocliques in the Hoffman-Singleton graph {15,14,10,3;1,5,12,15}

100 Hall-Janko graph {36,21;1,12}

100 Higman-Sims graph {22,21;1,6}

105 generalized hexagon (4,1) {8,4,4;1,1,2}

112 bipartite double of the Gewirtz graph {10,9,8,2,1;1,2,8,9,10}

112 generalized quadrangle (3,9) {30,27;1,10}

114 (57,49,42)-incidence graph {49,48,7;1,42,49}

114 (8,6)-cage {8,7,7;1,1,8}

120 (120,56,28,24)-strongly regular graph {56,27;1,24}

120 (120,63,30,36)-strongly regular graph {63,32;1,36}

126 5-odd graph {5,4,4,3;1,1,2,2}

126 (9,4)-Johnson graph {20,12,6,2;1,4,9,16}

126 Zara graph {45,32;1,18}

130 Grassmann graph J_3(4,2) {48,27;1,16}

144 halved Leonard graph (2) {66,35;1,30}

146 (73,64,56)-incidence graph {64,63,8;1,56,64}

146 (9,6)-cage {9,8,8;1,1,9}

154 bipartite double of the M22 graph {16,15,12,4,1;1,4,12,15,16}

155 Grassmann graph J_2(5,2) {42,24;1,9}

160 generalized octagon (2,1) {6,3,3,3;1,1,1,2}

162 second subconstituent of the McLaughlin graph {105,32;1,60}

162 local McLaughlin graph {56,45;1,24}

162 van Lint-Schrijver graph {6,5,5,4;1,1,2,6}

170 (5,8)-cage {5,4,4,4;1,1,1,5}

175 line graph of the Hoffman-Singleton graph {12,6,5;1,1,4}

176 (176,70,18,34)-strongly regular graph {70,51;1,34}

176 (176,105,68,54)-strongly regular graph {105,35;1,54}

182 (10,6)-cage {10,9,9;1,1,10}

186 generalized hexagon (5,1) {10,5,5;1,1,2}

189 generalized dodecagon (2,1) {4,2,2,2,2,2;1,1,1,1,1,2}

200 bipartite double of the Higman-Sims graph {22,21,16,6,1;1,6,16,21,22}

210 (10,4)-Johnson graph {24,15,8,3;1,4,9,16}

243 Berlekamp-van Lint-Seidel Graph {22,20;1,2}

253 (253,112,36,60)-strongly regular graph {112,75;1,60}

256 (1,2)-Doob graph {15,12,9,6,3;1,2,3,4,5}

266 Livingstone Graph {11,10,6,1;1,1,5,11}

275 McLaughlin graph {112,81;1,56}

288 Leonard graph {12,11,8,1;1,4,11,12}

312 (6,8)-cage {6,5,5,5;1,1,1,6}

315 Hall-Janko near octagon {10,8,8,2;1,1,4,5}

416 G_2(4) graph {100,63;1,20}

425 generalized octagon (4,1) {8,4,4,4;1,1,1,2}

462 6-odd graph {6,5,5,4,4;1,1,2,2,3}

506 truncated Witt graph {15,14,12;1,1,9}

651 Grassmann graph J_2(6,2) {90,56;1,9}

759 large Witt graph {30,28,24;1,3,15}

1024 (1,3)-Doob graph {15,12,9,6,3;1,2,3,4,5}

1024 (2,1)-Doob graph {15,12,9,6,3;1,2,3,4,5}

1170 (9,8)-cage {9,8,8,8;1,1,1,9}

1395 Grassmann graph J_2(6,3) {98,72,32;1,9,49}

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju.; Leman, A. A.; and Faradžev, I. A. "Example of Graph without a Transitive Automorphism Group." Dokl. Akad. Nauk SSSR 185, 975-976, 1969. English version Soviet Math. Dokl. 10, 440-441, 1969.Bendito, E.; Carmona, A.; and Encinas, A. M. "Shortest Paths in Distance-Regular Graphs." Europ. J. Combin. 21, 153-166, 2000.Biggs, N.; Boshier, A.; and Shawe-Taylor, J. "Cubic Distance-Regular Graphs." J. London Math. Soc. S2-33, 385-394, 1986.Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 13 and 159, 1993.Brouwer, A. "The Cubic Distance-Regular Graphs." http://www.win.tue.nl/~aeb/graphs/cubic_drg.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." European J. Combin. 14, 397-407, 1993.Brouwer, A. and Koolen, J. "The Distance-Regular Graphs of Valency Four." J. Algebraic Combin. 10, 5-24, 1999.Eppstein, D. "Cubic Symmetric xyz Graphs." Oct. 16, 2007. http://11011110.livejournal.com/120326.html.Fiol, M. A. and Garriga, E. "From Local Adjacency Polynomials to Locally Pseudo-Distance-Regular Graphs." J. Combin. Th. B 71, 162-183, 1997.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 68-69, 2001.Haemers, W. H. and Spence, E. "Graphs Cospectral with Distance-Regular Graphs." Linear Multilin. Alg. 39, 91-107, 1995.Haemers, W. H. "Distance-Regularity and the Spectrum of Graphs." Linear Alg. Appl. 236, 265-278, 1996.Koolen, J. H.; Yu, K.; Liang, X.; Choi, H.; and Markowsky, G. "Non-Geometric Distance-Regular Graphs of Diameter at Least 3 With Smallest Eigenvalue at Least -3." 15 Nov 2023. https://arxiv.org/abs/2311.09001.Royle, G. "Cubic Symmetric Graphs (The Foster Census): Distance-Regular Graphs" http://school.maths.uwa.edu.au/~gordon/remote/foster/#drgs.Steinerberger, S. and Thomas, R. R. "Conformally Rigid Graphs." J. Graph Th., 1-21, 2025.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.

Referenced on Wolfram|Alpha

Distance-Regular Graph

Cite this as:

Weisstein, Eric W. "Distance-Regular Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Distance-RegularGraph.html

Distance-Regular Graph

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Subject classifications