Algebraic Characterizations of Distance-Regular Graphs ^{∗}

M.A. Fiol

Departament de Matemàtica Aplicada i Telemàtica Universitat Politècnica de Catalunya Jordi Girona, 1–3 , Mòdul C3, Campus Nord 08034 Barcelona, Spain; email: fiol@mat.upc.es

Abstract We survey some old and some new characterizations of distance-regular graphs,

which depend on information retrieved from their adjacency matrix.

Distance-regular graphs were introduced by Biggs around 1970, by changing a symmetrytype requirement, that of distance-transitivity, by a regularity-type condition concerning the cardinality of some vertex subsets. Thus, one common way of looking at distanceregularity is to “hang” the graph from a given vertex and observe the resulting different layers; that is, the subsets of vertices at a given distance from the root. Then, if vertices in the same layer are “indistinguishable” from each other, and the whole configuration does not depend on the chosen vertex, the graph is said to be distance-regular. More precisely, a (connected) graph G = (V, E) with diameter D is distance-regular if and only if, for any two vertices u, v ∈ V at distance dist(u, v) = k, 0 ≤ k ≤ D, the numbers c_{k}, a_{k}, b_{k}, of vertices which are adjacent to v, and at distance k − 1, k, k + 1 respectively from u, do not depend on the chosen vertices u and v, but only on their distance k.

Since their introduction, distance-regular graphs and their main generalization, the association schemes, have proved to be a key concept in algebraic combinatorics, having important connections with other branches of mathematics, such as geometry, coding theory, group theory, design theory, as well as to other areas of graph theory. As stated in the preface of the comprehensive textbook of Brouwer, Cohen and Neumaier [?], this is because most finite objects bearing “enough regularity” are closely related to certain distance-regular graphs. Apart from the above definition, there are other well-known combinatorial characterizations of distance-regular, such as the following:

(a) A graph G with diameter D is distance-regular if and only if, for any pair of vertices u, v ∈ V and integers 0 ≤ i, j ≤ D, the number of vertices which are at distance i from u and at distance j from v only depends on dist(u, v).

∗11th Inter. Conf. on Formal Power Series and Algebraic Combinatorics, Barcelona, 1999.

Work supported in part by the Spanish Research Council (Comisión Interministerial de Ciencia y Tecnología, CICYT) under projects TIC 94-0592 and TIC 97-0963.

(b) A graph G is distance-regular if and only if for any integer k ≥ 0, the number of walks of length k between two vertices u, v ∈ V only depends on dist(u, v).

In this work, we aim to survey some characterizations of distance-regular graphs which are of an algebraic nature. Such characterizations rely mainly on the adjacency matrix A of the graph and/or some of its invariants, such as its spectrum

sp G := sp A = {λ_{0}^{m_{0}}, λ_{1}^{m_{1}}, …, λ_{d}^{m_{d}}}

where the eigenvalues λ_{l}, 0 ≤ l ≤ d are in decreasing order and the superscripts denote multiplicities, or their corresponding eigenspaces

E_{l} := Ker(A − λ_{l}I) (0 ≤ l ≤ d).

Thus, as the number a_{uv}^{k} of walks of length k between vertices u, v is no more than the uv-entry of the k-th power of A, we can see (b) as a simple characterization in terms of the adjacency matrix of G. In fact, it can be easily proved that we do not need to impose the invariance condition on all such numbers of walks. For instance, if G is regular we have the following result:

(c) A regular graph G with diameter D is distance-regular if and only if for any two vertices u, v ∈ V at distance dist(u, v) = k, 1 ≤ k ≤ D, the numbers of walks a_{uv}^{k} and a_{uv}^{k+1} only depend on k.

Another characterization involving adjacency matrices states that a graph G with diameter D is distance-regular if and only if, for any k, the distance-k matrix A_{k} —whose uv-entry is 1 if dist(u, v) = k and 0 otherwise— is a polynomial of degree k in A; that is:

A_{k} = p_{k}(A)  (0 ≤ k ≤ D).  (1)

Notice that the existence of such p_{0} and p_{1} is always guaranteed since A_{0} = I and A_{1} = A. In general, the polynomial p_{k} is referred to as the distance-k polynomial of the graph. See, for instance, Biggs [?] or Brouwer et.al. [?]. In fact, if every vertex u ∈ V has the maximum possible eccentricity “allowed by the spectrum”; that is, the number of distinct eigenvalues minus one: ecc(u) = d, the existence of the highest degree distance polynomial suffices, and hence we need only to require that

A_{D} = p_{D}(A).  (2)

This was proved in the context of pseudo-distance-regularity —a generalization of distanceregularity that makes sense even for non-regular graphs— by Garriga, Yebra and the author in [?].

For each eigenvalue λ_{l}, 0 ≤ l ≤ d, let U_{l} be the matrix whose columns form an orthonormal basis of its eigenspace E_{l}. The (principal) idempotents of A are the matrices E_{l} := U_{l}U_{l}^{⊤} representing the orthogonal projections onto E_{l}. Accordingly, such matrices satisfy E_{0} + E_{1} + ⋯ + E_{d} = I (as expected, since the sum of all orthogonal projections gives the original vector), and the so-called spectral decomposition theorem

∑_{l=0}^{d} λ_{l}E_{l} = A

(see for instance, Godsil [?]). Since both {I, A, …, A^{d}} and {E_{0}, E_{1}, …, E_{d}} are basis of A(A), the adjacency or Bose-Mesner algebra of matrices which are polynomials in A, it is not strange to have characterizations of distance-regularity in terms of the entries of the above idempotents. These numbers are called the crossed uv-local multiplicities of λ_{l}, and they are denoted by m_{uv}(λ_{l}). Notice that, if z_{ul} represents the orthogonal projection of the u-canonical vector e_{u} on E_{l}, the crossed local multiplicities correspond to the scalar products:

m_{uv}(λ_{l}) := (E_{l})_{uv} = ⟨E_{l}e_{u}, e_{v}⟩ = ⟨E_{l}e_{u}, E_{l}e_{v}⟩ = ⟨z_{ul}, z_{vl}⟩ (u, v ∈ V).

For instance, if the graph is regular, then the eigenvector of λ_{0} is the all-1 vector j, and the above gives m_{uv}(λ_{0}) = ⟨\frac{1}{n}j, \frac{1}{n}j⟩ = 1/n for any u, v ∈ V. Moreover, Godsil [?] proved that, if G is distance-regular, then for any given eigenvalue λ_{l}, 0 ≤ l ≤ d, the crossed uv-local multiplicity m_{uv}(λ_{l}) depends only on the distance dist(u, v), and it is not difficult to realize that the converse is also true. In fact, in the spirit of characterization (c), we can prove the following result (see [?]):

(d) A regular graph G, with eigenvalues λ_{0} > λ_{1} > ⋯ > λ_{d} and diameter D, is distanceregular if and only if the crossed uv-local multiplicities m_{uv}(λ_{1}) and m_{uv}(λ_{d}) depend only on the distance dist(u, v) = k, for any 0 ≤ k ≤ D.

Of course, we may also ask for some characterizations involving only the spectrum. Then, the question would now be: Can we see from the spectrum of a graph whether it is distance-regular? In this context, it has been known for a long time that the answer is ‘yes’ when D ≤ 2 and ‘not’ if D ≥ 4, whereas the case D = 3 was undecided until recently, when Haemers [?] gave also a negative answer. Thus, in general the spectrum is not sufficient to assure distance-regularity and, if we want to go further, we must require the graph to satisfy some additional conditions. In this direction, Van Dam and Haemers [?] showed that, in the case D = 3, such a condition could be the number n_{d}(u) of vertices at “extremal distance” D = d from each vertex u ∈ V. Then, Garriga and the author [?] solved the general case, characterizing distance-regular graphs as those regular graphs whose number of vertices at distance d from each vertex is what it should be (a number that depends only on the spectrum of the graph). To be more precise, they proved that a (connected) regular graph G with n vertices and spectrum sp G = {λ_{0}^{m_{0}}, λ_{1}^{m_{1}}, …, λ_{d}^{m_{d}}} is distance-regular if and only if the number of vertices at distance d from each vertex u is

n_{d}(u) = n (∑_{l=0}^{d} \frac{π_{0}^{2}}{m_{l}π_{l}^{2}} )^{−1}  (3)

where the π′_{l}s are moment-like parameters defined by π_{l} := ∏_{k=0,k≠l}^{d} |λ_{l} − λ_{k}|, 0 ≤ l ≤ d. In fact, since the right-hand expression in (??) is the value at λ_{0} of a degree-d polynomial, the characterization (??) can now be seen as a corollary.

Notice that the cases d = 1, 2 of the above result are trivial, in the sense that every (connected) regular graph G with two or three different eigenvalues is distance-regular (G = K_{n} if d + 1 = 2 and G is strongly regular when d + 1 = 3—see, for instance, Godsil [?]). As we have already mentioned, the first “non-trivial” case d = 3 is due to Haemers and Van Dam [?], while the case n_{d}(u) = 1 (that is, 2-antipodal graphs) was also studied by Garriga, Yebra and the author in a previous paper [?]. In fact, in this case only the distinct eigenvalues matter, as their multiplicities can be deduced from them by the formulae m_{l} = π_{0}/π_{l}, 0 ≤ l ≤ d. Furthermore, in this case we do not need to require regularity since it is inferred by condition (??). Then it turns out that a graph G with eigenvalues λ_{0} > λ_{1} > ⋯ > λ_{d} is a 2-antipodal distance-regular graph if and only if

n_{d}(u) = n (∑_{l=0}^{d} \frac{π_{0}}{π_{l}} )^{−1} = 1  (4)

for each u ∈ V. The graphs satisfying the second equality of (??), that is ∑_{l=0}^{d}(π_{0}/π_{l}) = n, are called boundary graphs since they satisfy an extremal property that arises from a bound for the diameter of a graph in terms of its distinct eigenvalues. Namely, it was proved in [?] that, if G is regular and ∑_{l=0}^{d}(π_{0}/π_{l}) > n, then D ≤ d − 1.

From the result in (??), some other spectral characterizations have been given for special classes of distance-regular graphs. Thus, as a generalization of the above 2-antipodal case, it was proved in [?] that a regular graph G, with eigenvalues λ_{0} > λ_{1} > ⋯ > λ_{d}, is an r-antipodal distance-regular graph if and only if the distance graph G_{d} (that is, the graph whose adjacency matrix is A_{d}) is constituted by disjoint copies of the complete graph K_{r}, with r satisfying an expression in terms of n and the distinct eigenvalues. Namely,

r = 2n (∑_{l=0}^{d} \frac{π_{0}}{π_{l}} )^{−1} .  (5)

Note that the case r = 2 corresponds to (??).

Recall that a δ-regular graph G on n vertices is called (n, δ; a, c)-strongly regular if every pair of adjacent (respectively, nonadjacent) vertices u, v have a (respectively c) common neighbours. Thus, if connected, a strongly regular graph G is the same as a distanceregular graph (with diameter two). Otherwise, it is known that G is constituted by several copies of K_{r}. Furthermore, a graph G with diameter D = d is called (n, δ; a, c)-strongly distance-regular if G is distance-regular and its distance-d graph G_{d} is strongly regular with the indicated parameters. Some known examples of such graphs are the connected strongly regular graphs, with G_{d} = \overline{G} (the complement of G), and the r-antipodal distance-regular graphs with G_{d} = mK_{r} so that they are (n, δ; r − 1, 0)-strongly distance-regular graphs. Hence, some spectral conditions for a (regular or distance-regular) graph to be strongly distance-regular have been already given above. In particular, notice that 2-antipodal distance-regular graphs characterized in (??) correspond to the case a = c = 0. In this context, the more general case a = c was dealt with in [?], where one can find the following result. Let G be a regular graph on n vertices, with distinct eigenvalues λ_{0} > λ_{1} > ⋯ > λ_{d}, d > 1. Then G is (n, δ; c, c)-strongly distance-regular if and only if

n_{d}(u) = \frac{n(n − 1)}{(∑_{l=1}^{d} \frac{π_{0}}{π_{l}} )^{2} + n − 1}  (6)

for every vertex u ∈ V. Moreover, in such a case, the above parameters are δ = n_{d} := n_{d}(u), c = n_{d}(n_{d} − 1)/(n − 1), and the multiplicity of eigenvalue λ_{i} is

m_{i} = \frac{π_{0}}{π_{i}} \sqrt{\frac{(n − 1)n_{d}}{n − n_{d}}} = (n − 1)\frac{\frac{1}{π_{i}}}{∑{d \atop l=1} \frac{1}{π_{l}}}  (1 ≤ i ≤ d).  (7)

The necessity of condition (??) was proved by Van Dam [?] using the Laplace matrix of G and Haemers’ method of eigenvalue interlacing [?]. He also proved that (??) is sufficient to assure the strong regularity of G_{d} and that, in the case d = 3, it also implies the distanceregularity of G. In such a case, Van Dam also offered examples of graphs satisfying the result. Namely, the odd graph O_{4} (4-regular, n = 35, n_{3} = 18), and the generalized hexagons GH(q, q), with q a prime power, ((q + 1)-regular, n = 2(q + 1)(q^{4} + q^{2} + 1), n_{3} = q^{5}); for a description of these graphs, see for instance [?, ?]. On the other hand, notice that for the case n_{d}(u) = 1, studied in [?], the values in (??) and (??) coincide since, in both cases, G must be a 2-antipodal distance-regular graph.

Finally, for general values of a and c, and d = 3, the following characterization has been recently given in [?]. A regular (connected) graph G, with n vertices and distinct eigenvalues λ_{0} > λ_{1} > λ_{2} > λ_{3}, is strongly distance-regular if and only if λ_{2} = −1, and

n_{3}(u) = \frac{(n − λ_{0} − 1)[π_{0}/(λ_{0} + 1) − n(λ_{0} + λ_{1}λ_{3})]}{π_{0} − n(λ_{0} + λ_{1}λ_{3})}.  (8)

for every vertex u ∈ V. (In this case, a and c satisfy also expressions in terms of the eigenvalues.)

Although, up to now, we are not aware of any generalization of the above theorem for d > 3, we neither know, if fact, of any example of strongly distance-regular graph with diameter greater than three (apart from the r-antipodal ones). This suggests to end with the following conjecture: A (connected) regular graph G, with n vertices and distinct eigenvalues λ_{0} > λ_{1} > ⋯ > λ_{d}, is strongly distance-regular if and only if one of the three following conditions holds.

1. G is strongly regular (d = 2);

2. d = 3, λ_{2} = −1, and G_{3} is k-regular with degree k satisfying (??);

3. G_{d} is constituted by disjoint copies of K_{r} with r satisfying (??) (that is, G is an antipodal distance-regular graph).

References

[1] N. Biggs, Algebraic Graph Theory. Cambridge University Press, Cambridge, 1974; second edition: 1993.

[2] A.E. Brouwer, A.M. Cohen and A. Neumaier, Distance-Regular Graphs. Springer-Verlag, Berlin, 1989.

[3] E.R. van Dam, Bounds on special subsets in graphs, eigenvalues and association schemes, J. Algebraic Combin. 7 (1998), no. 3, 321–332.

[4] E.R. van Dam and W.H. Haemers, A characterization of distance-regular graphs with diameter three, J. Algebraic Combin. 6 (1977), no. 3, 299–303.

[5] M.A. Fiol, An eigenvalue characterization of antipodal distance-regular graphs. Electron. J. Combin. 4 (1997), no. 1, #R30.

[6] M.A. Fiol, Some spectral characterizations of strongly distance-regular graphs, submitted.

[7] M.A. Fiol, On pseudo-distance-regularity, submitted.

[8] M.A. Fiol and E. Garriga, From local adjacency polynomials to locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B 71 (1997), 162–183.

[9] M.A. Fiol and E. Garriga, Pseudo-strong regularity around a set, submitted.

[10] M.A. Fiol, E. Garriga, and J.L.A. Yebra, On a class of polynomials and its relation with the spectra and diameters of graphs, J. Combin. Theory Ser. B 67 (1996), 48–61.

[11] M.A. Fiol, E. Garriga, and J.L.A. Yebra, Locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B 68 (1996), 179–205.

[12] M.A. Fiol, E. Garriga and J.L.A. Yebra, From regular boundary graphs to antipodal distance-regular graphs, J. Graph Theory 27 (1998), no. 3, 123–140.

[13] C.D. Godsil, Bounding the diameter of distance regular graphs, Combinatorica 8 (1988), 333–343.

[14] C.D. Godsil, Algebraic Combinatorics. Chapman and Hall, New York, 1993.

[15] W.H. Haemers, Distance-regularity and the spectrum of graphs, Linear Algebra Appl. 236 (1996), 265–278.

[16] W.H. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 227–228 (1995), 593–616.