TOPICS
Search

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 2024).

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.

ngraphintersection array
4tetrahedral graph{3;1}
6utility graph{3,2;1,3}
8cubical graph{3,2,1;1,2,3}
10Petersen graph{3,2;1,1}
14Heawood graph{3,2,2;1,1,3}
18Pappus graph{3,2,2,1;1,1,2,3}
20Desargues graph{3,2,2,1,1;1,1,2,2,3}
20dodecahedral graph{3,2,1,1,1;1,1,1,2,3}
28Coxeter graph{3,2,2,1;1,1,1,2}
30Tutte 8-cage{3,2,2,2;1,1,1,3}
90Foster graph{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
102Biggs-Smith graph{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
126Tutte 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.vdgraphintersection arrayspectrum
1.51pentatope graph K_5{4;1}4^1(−1)4
2.62octahedron graph K_(3×2){4,1;1,4}4^10^3(-2)^2
3.82complete bipartite graph K_(4,4){4,3;1,4}+/-4^10^6
4.92generalized quadrangle GQ(2,1){4,2;1,2}4^11^4(-2)^4
5.103crown graph K_2 square K_5^_{4,3,1;1,3,4}+/-(4^11^4)
6.143nonincidence graph of PG(2,2) Qt31{4,3,2;1,2,4}+/-(4^1sqrt(2)^6)
7.153line graph of the Petersen graph L(P){4,2,1;1,1,4}4^12^5(-1)^4(-2)^5
8.164hypercube graph Q_4{4,3,2,1;1,2,3,4}+/-(4^12^4)0^6
9.213generalized hexagon GH(2,1){4,2,2;1,1,2}4^1(1+/-sqrt(2))^6(-2)^8
10.263incidence graph of PG(2,3){4,3,3;1,1,4}+/-(4^1sqrt(3)^(12))
11.324incidence graph of AG(4,4) minus parallel class{4,3,3,1;1,1,3,4}+/-(4^12^(12))0^6
12.353odd graph O_4{4,3,3;1,1,2}4^12^(14)(-1)^(14)(-3)^6
13.454generalized octagon GO(2,1){4,2,2,2;1,1,1,2}4^13^91^(10)(-1)^9(-2)^(16)
14.707Danzer graph{4,3,3,2,2,1,1;1,1,2,2,3,3,4}+/-(4^13^62^(14)1^(14))
15.804(4,8)-cage graph{4,3,3,3;1,1,1,4}+/-(4^1sqrt(6)^(24))0^(30)
16.1896generalized 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.7286(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.

casegraphintersection array
(a)odd graph O_4{3,3,3;1,1,2}
(b)Sylvester graph{5,4,2;1,1,4}
(c)second subconstituent of the Hoffman-Singleton graph{6,5,1;1,1,6}
(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.

ngraphintersection array
5pentatope graph{4;1}
6octahedral graph{4,1;1,4}
816-cell graph{6,1;1,6}
9generalized quadrangle (2,1){4,2;1,2}
12icosahedral graph{5,2,1;1,2,5}
14quartic vertex-transitive graph Qt31{4,3,2;1,2,4}
15generalized quadrangle (2,2){6,4;1,3}
15quartic vertex-transitive graph Qt39{4,2,1;1,1,4}
16Clebsch graph{5,4;1,2}
16Shrikhande graph{6,3;1,2}
16tesseract graph{4,3,2,1;1,2,3,4}
21(7,2)-Kneser graph{10,6;1,6}
21generalized 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}
24Klein graph{7,4,1;1,2,7}
2525-Paulus graphs{12,6;1,6}
26(13,9,6)-incidence graph{9,8,3;1,6,9}
2626-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}
27generalized quadrangle (2,4){10,8;1,5}
27generalized quadrangle (2,4) minus spread 1{8,6,1,;1,3,8}
27generalized quadrangle (2,4) minus spread 2{8,6,1,;1,3,8}
27Schläfli graph{16,5;1,8}
28Chang graphs{12,5;1,4}
28(8,2)-Kneser graph{15,8;1,10}
28locally 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}
32Kummer graph{6,5,4;1,2,6}
32Wells graph{5,4,1,1;1,1,4,5}
35Grassmann graph J_2(4,2){18,8;1,9}
354-odd graph{4,3,3;1,1,2}
36hexacode graph{6,5,4,1;1,2,5,6}
36(9,2)-Kneser graph{21,10;1,15}
36Sylvester 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}
42Hoffman-Singleton graph minus star{6,5,1;1,1,6}
45(10,2)-Kneser graph{28,12;1,21}
45generalized octagon (2,1){4,2,2,2;1,1,1,2}
45halved 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}
50Hoffman-Singleton graph{7,6;1,1}
50Hoffman-Singleton graph complement{42,6;1,36}
52generalized hexagon (3,1){6,3,3;1,1,2}
55(11,2)-Kneser graph{36,14;1,28}
56distance 2-graph of the Gosset graph{27,16,1;1,16,27}
56Gewirtz graph{10,9;1,2}
56Gosset graph{27,10,1;1,10,27}
57Perkel 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}
63symplectic 7-cover of K_9{8,6,1;1,1,8}
64(1,1)-Doob graph{9,6,3;1,2,3}
6464-cyclotomic graph{21,12;1,6}
65Hall 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}
72Suetake graph{12,11,8,1;1,4,11,12}
74(37,9,2)-incidence graph{9,8,7;1,2,9}
77M22 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}
81Brouwer-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}
100bipartite double of the Hoffman-Singleton graph{7,6,6,1,1;1,1,6,6,7}
100cocliques in the Hoffman-Singleton graph{15,14,10,3;1,5,12,15}
100Hall-Janko graph{36,21;1,12}
100Higman-Sims graph{22,21;1,6}
105generalized hexagon (4,1){8,4,4;1,1,2}
112bipartite double of the Gewirtz graph{10,9,8,2,1;1,2,8,9,10}
112generalized 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}
1265-odd graph{5,4,4,3;1,1,2,2}
126(9,4)-Johnson graph{20,12,6,2;1,4,9,16}
126Zara graph{45,32;1,18}
130Grassmann graph J_3(4,2){48,27;1,16}
144halved 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}
154bipartite double of the M22 graph{16,15,12,4,1;1,4,12,15,16}
155Grassmann graph J_2(5,2){42,24;1,9}
160generalized octagon (2,1){6,3,3,3;1,1,1,2}
162second subconstituent of the McLaughlin graph{105,32;1,60}
162local McLaughlin graph{56,45;1,24}
162van Lint-Schrijver graph{6,5,5,4;1,1,2,6}
170(5,8)-cage{5,4,4,4;1,1,1,5}
170(5,8)-cage{5,4,4,4;1,1,1,5}
175line 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}
186generalized hexagon (5,1){10,5,5;1,1,2}
189generalized dodecagon (2,1){4,2,2,2,2,2;1,1,1,1,1,2}
200bipartite 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}
243Berlekamp-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}
266Livingstone Graph{11,10,6,1;1,1,5,11}
275McLaughlin graph{112,81;1,56}
288Leonard graph{12,11,8,1;1,4,11,12}
312(6,8)-cage{6,5,5,5;1,1,1,6}
315Hall-Janko near octagon{10,8,8,2;1,1,4,5}
416G_2(4) graph{100,63;1,20}
425generalized octagon (4,1){8,4,4,4;1,1,1,2}
4626-odd graph{6,5,5,4,4;1,1,2,2,3}
506truncated Witt graph{15,14,12;1,1,9}
651Grassmann graph J_2(6,2){90,56;1,9}
759large 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}
1395Grassmann graph J_2(6,3){98,72,32;1,9,49}

See also

Automorphic Graph, Biggs-Smith Graph, Coxeter Graph, Cubic Symmetric Graph, Cubical Graph, Desargues Graph, Distance-Transitive Graph, Dodecahedral Graph, Foster Graph, Global Parameters, Heawood Graph, Intersection Array, Moore Graph, Pappus Graph, Petersen Graph, Regular Graph, Shrikhande Graph, Sylvester Graph, Taylor Graph, Wells Graph

Explore with Wolfram|Alpha

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." 19 Feb 2024. https://arxiv.org/abs/2402.11758.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 Web Resource. https://mathworld.wolfram.com/Distance-RegularGraph.html

Subject classifications