A Quasi-Spectral Characterization of Strongly 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

Submitted: April 30, 2000; Accepted: September 16, 2000.

Abstract

A graph Γ with diameter d is strongly distance-regular if Γ is distanceregular and its distance-d graph Γ_{d} is strongly regular. The known examples are all the connected strongly regular graphs (i.e. d = 2), all the antipodal distanceregular graphs, and some distance-regular graphs with diameter d = 3. The main result in this paper is a characterization of these graphs (among regular graphs with d distinct eigenvalues), in terms of the eigenvalues, the sum of the multiplicities corresponding to the eigenvalues with (non-zero) even subindex, and the harmonic mean of the degrees of the distance-d graph.

AMS subject classifications. 05C50 05E30

1 Preliminaries

Strongly distance-regular graphs were recently introduced by the author [9] by combining the standard concepts of distance-regularity and strong regularity. A strongly distance-regular graph Γ is a distance-regular graph (of diameter d, say) with the property that the distance-d graph Γ_{d}—where two vertices are adjacent whenever they are at distance d in Γ—is strongly regular. The only known examples of these graphs are the strongly regular graphs (with diameter d = 2), the antipodal distance-regular graphs, and the distance-regular graphs with d = 3 and third greatest eigenvalue λ_{2} = −1. (In fact, it has been conjectured that a strongly distance-regular graph is antipodal or has diameter at most three.) For these three families some spectral, or “quasi-spectral”, characterizations are known. Thus, it is well-known that strongly regular graphs are characterized, among regular connected graphs, as those having exactly three distinct eigenvalues. In the other two cases, however, the spectrum is not enough and some other information about the graphs—such as the numbers of vertices at maximum distance from each vertex—is needed to characterize them. Then we speak about quasi-spectral characterizations, as those in [7, 14] (for antipodal distance-regular graphs) and [5, 9] (for strongly distance-regular graphs with diameter d = 3). Quasi-spectral characterizations for general distance-regular graphs were also given in [16, 6] (for diameter three) and [10] (for any diameter).

Following these works, we derive in this paper a general quasi-spectral characterization of strongly distance-regular graphs. This includes, as particular cases, most of the previous results about such graphs, and allows us also to obtain some new results about their spectra. In particular, our approach makes clear some symmetry properties enjoyed by their eigenvalues and multiplicities. Eventually, and after looking at the expressions obtained, one gets the intuitive impression that strongly distanceregular graphs are among the graphs with more hidden “spectral symmetries”.

Before proceeding to our study we devote the rest of this introductory section to fixing the terminology and to recalling some basic results. Let Γ a (simple, finite, and connected) graph with adjacency matrix A := A(Γ) and (set of) eigenvalues ev Γ := {λ_{0} > λ_{1} > ⋯ > λ_{d}}. The alternating polynomial P of Γ is defined as the (unique) polynomial of degree d − 1 satisfying

P (λ_{0}) = max_{p∈ℝ_{d−1}[x]}{p(λ_{0}) : ∥p∥_{∞} ≤ 1}

where ∥p∥_{∞} = max_{1≤i≤d} |p(λ_{i})|. It is known that P is characterized by taking d alternating values ±1 at ev Γ: P (λ_{i}) = (−1)^{i+1}, 1 ≤ i ≤ d, which, together with Lagrange interpolation, yields

P (λ_{0}) = ∑_{i=1}^{d} \frac{π_{0}}{π_{i}} .  (1)

where the π′_{i}s are moment-like parameters defined from the eigenvalues as π_{i} := ∏_{j=0,j≠i}^{d} |λ_{i} − λ_{j}|, 0 ≤ i ≤ d, and satisfying

∑_{i even} \frac{λ_{i}^{l}}{π_{i}} = ∑_{i odd} \frac{λ_{i}^{l}}{π_{i}}  (0 ≤ l < d).  (2)

(See [12, 14] for more details.)

In this work, it is useful to consider the following characterization of distanceregular graphs (see e.g. Biggs [2] or Brouwer et al. [3]): A (connected) graph Γ, with vertex set V = {u, v, …}, adjacency matrix A, and diameter d, is distance-regular if and only if there exists a sequence of polynomials p_{0}, p_{1}, …, p_{d}, called the distance polynomials, such that dgr p_{i} = i, 0 ≤ i ≤ d, and

A_{i} := A(Γ_{i}) = p_{i}(A) (0 ≤ i ≤ d),

where A_{i} is the adjacency matrix of the distance-i graph Γ_{i} and, so, it is called the distance-i matrix of Γ. Let n := |V | and assume that Γ has spectrum sp Γ := {λ_{0}^{m(λ_{0})}, λ_{1}^{m(λ_{1})}, …, λ_{d}^{m(λ_{d})}} (as Γ is connected, m(λ_{0}) = 1). Then the distance polynomials are orthogonal with respect to the scalar product

⟨p, q⟩_{Γ} := \frac{1}{n} tr(p(A)q(A)) = ∑_{i=0}^{d} \frac{m(λ_{i})}{n}p(λ_{i})q(λ_{i}),  (3)

and they are normalized in such a way that ∥p_{i}∥_{Γ}^{2} = p_{i}(λ_{0}), 0 ≤ i ≤ d. (Of course, this inner product makes sense—and it will be used later—for any graph Γ.) Moreover, if Γ_{i}(u) denotes the set of vertices at distance i from a given vertex u, we have p_{i}(λ_{0}) = n_{i}(u) := |Γ_{i}(u)| for any u ∈ V and 0 ≤ i ≤ d. In fact, there are explicit formulas giving the values of the highest degree polynomial p_{d} at ev Γ, in terms of the eigenvalues and their multiplicities. Namely,

p_{d}(λ_{0}) = n (∑_{i=0}^{d} \frac{π_{0}^{2}}{m(λ_{i})π_{i}^{2}} )^{−1} ;  p_{d}(λ_{i}) = (−1)^{i} \frac{π_{0}p_{d}(λ_{0})}{π_{i}m(λ_{i})}.  (4)

(From the second expression one has the known formulas for the multiplicities in terms of p_{d}—see, e.g., Bannai and Ito [1].) Hence, since p_{d}(λ_{0}) (the degree of Γ_{d}) is a positive integer, the polynomial p_{d} must take alternating values at the mesh ev Γ:

p_{d}(λ_{i}) > 0 (i even);  p_{d}(λ_{i}) < 0 (i odd).  (5)

In this paper, we also use the following results about strongly regular graphs (see, for instance, Cameron’s survey [4] or Godsil’s textbook [15]):

Lemma 1.1 (a) A graph Γ, not complete or empty, with adjacency matrix A is (n, k; a, c)-strongly regular if and only if

A^{2} − (a − c)A + (c − k)I = J,  (6)

where J represents the all-1 matrix.

(b) A connected regular graph Γ with exactly three distinct eigenvalues μ_{0} > μ_{1} > μ_{2} is a (n, k; a, c)-strongly regular graph with parameters satisfying

k = μ_{0}, c − k = μ_{1}μ_{2}, a − c = μ_{1} + μ_{2}.  (7)

Notice that, from the above and tr A = 0, it follows that μ_{2} < 0 and μ_{1} ≥ 0 (with μ_{1} = 0 only when Γ is the regular multipartite graph).

2 A quasi-spectral characterization

In this section we derive our main result, which characterizes strongly-regular graphs among regular graphs, and study some of its consequences.

Given any vertex u of a graph with diameter d, we denote by N_{i}(u), 0 ≤ i ≤ d, the i-neighbourhood of u, or set of vertices at distance at most i from u. Using some results from [10, 13], the author proved in [8] the following result, which is basic to our study.

Theorem 2.1 Let Γ be a regular graph with n vertices and d+1 distinct eigenvalues. For every vertex u ∈ V, let s_{d−1}(u) := |N_{d−1}(u)|. Then, any polynomial R ∈ ℝ_{d−1}[x] satisfies the bound

\frac{R(λ_{0})^{2}}{∥R∥_{Γ}^{2}} ≤ \frac{n}{∑u∈V \frac{1}{s_{d−1}(u)}} ,  (8)

and equality is attained if and only if Γ is a distance-regular graph. Moreover, in this case, we have \frac{R(λ_{0})}{∥R∥_{Γ}^{2}}R = q_{d−1} := ∑_{i=0}^{d−1} p_{i}, where the p_{i}’s are the distance polynomials of Γ.

Note that the above upper bound is, in fact, the harmonic mean of the numbers s_{d−1}(u), u ∈ V, which is hereafter denoted by H. Moreover, in case of equality, q_{d−1}(A) = ∑_{i=0}^{d−1} A_{i} = J − A_{d}, and the distance-d polynomial of Γ is just

p_{d} = q_{d} − q_{d−1} = q_{d} − \frac{R(λ_{0})}{∥R∥_{Γ}^{2}}R  (9)

where q_{d} represents the Hoffman polynomial; that is, q_{d} = \frac{n}{π_{0}} ∏_{i=1}^{d}(x − λ_{i}).

At this point it is useful to introduce the following notation: For a graph with n vertices, spectrum {λ_{0}^{m(λ_{0})}, …, λ_{d}^{m(λ_{d})}}, and alternating polynomial P, note that, by (1), the value of P (λ_{0}) + 1 is given by the sum

Σ := ∑_{i=0}^{d} \frac{π_{0}}{π_{i}} = 1 + Σ_{e} + Σ_{o} ,  (10)

where Σ_{e} (respectively Σ_{o}) denotes the sum of the terms π_{0}/π_{i} with even non-zero (respectively, odd) index i. Note also that, by (2) with l = 0, both numbers are closely related: Σ_{o} = Σ_{e} + 1. However, the use of both symbols will reveal the symmetries of the expressions obtained. With the same aim, let us also consider the following sum decomposition:

n = ∑_{i=0}^{d} m(λ_{i}) = 1 + σ_{e} + σ_{o} ,  (11)

where σ_{e} represents the sum of all multiplicities of the eigenvalues with non-zero even subindex σ_{e} := m(λ_{2}) + m(λ_{4}) + ⋯, and σ_{o} := n − σ_{e} − 1 = m(λ_{1}) + m(λ_{3}) + ⋯

The following result generalizes for any diameter a theorem of the author [9] (the case of diameter three).

Theorem 2.2 A regular graph Γ, with n vertices, eigenvalues λ_{0} > λ_{1} > ⋯ > λ_{d}, and parameters σ_{e}, Σ_{e} as above, is strongly distance-regular if and only if the harmonic mean of the numbers s_{d−1}(u), u ∈ V, is

H = n − \frac{nσ_{e}σ_{o}}{nΣ_{e}Σ_{o} + (σ_{e} − Σ_{e})(σ_{o} + Σ_{o})}.  (12)

Moreover, if this is the case, Γ_{d} is a strongly regular graph with degree k = n − H and parameters

c = k − k^{2} \frac{Σ_{e}Σ_{o}}{σ_{e}σ_{o}};  a = c + k (\frac{Σ_{e}}{σ_{e}} − \frac{Σ_{o}}{σ_{o}} ) .  (13)

Proof . Given any real number t, let us consider the polynomial R := (1+\frac{t}{2})P −\frac{t}{2}, where P is the alternating polynomial of Γ. Notice that, from the properties of P, we have R(λ_{i}) = 1 for any odd i, 1 ≤ i ≤ d, and R(λ_{i}) = −1 − t for every even i ≠ 0. Then, the square norm of R satisfies

n∥R∥_{Γ}^{2} = R^{2}(λ_{0}) + ∑_{i=1}^{d} R^{2}(λ_{i})m(λ_{i}) = R^{2}(λ_{0}) + σ_{e}(1 + t)^{2} + σ_{o}.  (14)

Hence, by Theorem 2.1, we must have, for any t,

Ψ(t) := \frac{n [(1 + \frac{t}{2})P (λ_{0}) − \frac{t}{2}]^{2}}{[(1 + \frac{t}{2})P (λ_{0}) − \frac{t}{2}]^{2} + σ_{e}(1 + t)^{2} + σ_{o}} = \frac{R(λ_{0})^{2}}{∥R∥_{Γ}^{2}} ≤ H.  (15)

Since we are interested in the case of equality, we must find the maximum of the function Ψ. Such a maximum is attained at

t_{0} = \frac{σ_{o}}{σ_{e}} \frac{P (λ_{0}) − 1}{P (λ_{0}) + 1} − 1  (16)

and its value is

Ψ_{max} := Ψ(t_{0}) = n − \frac{4nσ_{e}σ_{o}}{(n − 1)Σ^{2} + 4σ_{o}(σ_{e} − Σ)}  (17)
= n − \frac{nσ_{e}σ_{o}}{nΣ_{e}Σ_{o} + (σ_{e} − Σ_{e})(σ_{o} + Σ_{o})},  (18)

where we have used (10) and (11). Consequently, Ψ_{max} ≤ H and, from the same theorem, the equality case occurs if and only if Γ is a distance-regular graph with distance d-polynomial given by (9). From this fact, let us now see that Γ_{d} is strongly regular. In our case, all inequalities in (15) and (14) become equalities with t = t_{0} given by (16), so giving

R(λ_{0}) = (1 + \frac{t_{0}}{2} ) P (λ_{0}) − \frac{t_{0}}{2} ; ∥R∥_{Γ}^{2} = R^{2}(λ_{0}) + σ_{e}(1 + t_{0})^{2} + σ_{o}.

This allows us to compute, through (9), the distance-d polynomial and its relevant values:

μ_{0} := p_{d}(λ_{0}) = n − H;
μ_{1} := p_{d}(λ_{i}) = −\frac{R(λ_{0})}{∥R∥_{Γ}^{2}}R(λ_{i}) = \frac{R(λ_{0})}{∥R∥_{Γ}^{2}}(1 + t_{0}) (even i ≠ 0);
μ_{2} := p_{d}(λ_{i}) = −\frac{R(λ_{0})}{∥R∥_{Γ}^{2}}R(λ_{i}) = −\frac{R(λ_{0})}{∥R∥_{Γ}^{2}}  (odd i).

Then Γ_{d} is a regular graph with degree k = μ_{0} and has at most three eigenvalues μ_{0} ≥ μ_{1} > μ_{2} (with multiplicities m(μ_{0}) = 1, m(μ_{1}) = σ_{e}, and m(μ_{2}) = σ_{o}). If it has exactly three eigenvalues, μ_{0} > μ_{1}, then Γ_{d} must be connected and Lemma 1.1 applies. Otherwise, if μ_{0} = μ_{1}, the graph Γ_{d} is simply constituted by disjoint copies of the complete graph on k + 1 vertices. (See [9] for more details.) In both cases Γ_{d} is strongly regular, as claimed. Moreover, after some algebraic manipulations, the above formulas yield

k = \frac{nσ_{e}σ_{o}}{nΣ_{e}Σ_{o} + (σ_{e} − Σ_{e})(σ_{o} + Σ_{o})};  (19)
μ_{1} = \frac{nΣ_{e}σ_{o}}{nΣ_{e}Σ_{o} + (σ_{e} − Σ_{e})(σ_{o} + Σ_{o})} = k \frac{Σ_{e}}{σ_{e}};  (20)
μ_{2} = \frac{−nσ_{e}Σ_{o}}{nΣ_{e}Σ_{o} + (σ_{e} − Σ_{e})(σ_{o} + Σ_{o})} = −k \frac{Σ_{o}}{σ_{o}};  (21)

and the values of c and a follow from (7).

Conversely, if Γ is a strongly distance-regular graph, its distance-d graph Γ_{d}, with adjacency matrix p_{d}(A), is a strongly regular graph with either three or two eigenvalues, μ_{0} ≥ μ_{1} > μ_{2}, satisfying μ_{0} = p_{d}(λ_{0}) = n_{d}(u) := |Γ_{d}(u)| for every u ∈ V, μ_{1} = p_{d}(λ_{i}) ≥ 0 for every even i ≠ 0, and μ_{2} = p_{d}(λ_{i}) for every odd i. Thus, by adding up the corresponding multiplicities, obtained from the second expression in (4), we get

σ_{e} = ∑_{i even (i≠0)} \frac{π_{0}}{π_{i}} \frac{μ_{0}}{μ_{1}} = \frac{μ_{0}}{μ_{1}} Σ_{e}; σ_{o} = − ∑_{i odd} \frac{π_{0}}{π_{i}} \frac{μ_{0}}{μ_{2}} = −\frac{μ_{0}}{μ_{2}} Σ_{o} .

These two equations give the values of μ_{1} and μ_{2}—compare with (20) and (21)— which, substituted into

n∥p_{d}∥_{Γ}^{2} = μ_{0}^{2} + σ_{e}μ_{1}^{2} + σ_{o}μ_{2}^{2} = nμ_{0},

and solving for μ_{0} = n_{d}(u), give

n_{d}(u) = \frac{nσ_{e}σ_{o}}{nΣ_{e}Σ_{o} + (σ_{e} − Σ_{e})(σ_{o} + Σ_{o})}  (22)

for every vertex u ∈ V. Hence, all the numbers s_{d−1}(u) = n − n_{d}(u), u ∈ V, are the same and their harmonic mean H satisfies (12). This completes the proof of the theorem. □

From the above proof, notice that, alternatively, we can assert that the regular graph Γ is strongly distance-regular if and only if the distance-d graph Γ_{d} is k-regular with degree k = n_{d}(u) given by (19) or (22).

As a by-product of such a proof, we can also give bounds for the sum of “even multiplicities” σ_{e} in any regular graph, in terms of its eigenvalues and harmonic mean H.

Corollary 2.3 Let Γ be a regular graph , with n vertices, eigenvalues λ_{0} > λ_{1} > ⋯ > λ_{d}, and harmonic mean H. Set α := \frac{n}{2}(1 − \frac{1}{H}) and β := Σ_{e}(\frac{n}{H} − 1). Then the sum σ_{e} of even multiplicities satisfies the bounds

α − β − \sqrt{α(1 − αβΣ)} ≤ σ_{e} ≤ α − β + \sqrt{α(1 − αβΣ)}.

Proof . Solve for σ_{e} the inequality

n − Ψ_{max} = \frac{4nσ_{e}(n − σ_{e} − 1)}{(n − 1)Σ^{2} + 4(n − σ_{e} − 1)(σ_{e} − Σ)} ≥ n − H,

which comes from (17), (11), and Ψ_{max} ≤ H, and use (10). □

Let us now consider some particular cases of the above theorem, which contain some previous results of Van Dam, Garriga, and the author. Note first that, for some particular cases, we do not need to know the multiplicity sum σ_{e} (and hence nor σ_{o}), since it can be deduced from the eigenvalues. For instance, for diameter d = 3, the multiplicities m_{1}, m_{2}, m_{3} of a regular graph must satisfy the system

\begin{aligned}1 + m_{1} + m_{2} + m_{3} & = & n \\ λ_{0} + m_{1}λ_{1} + m_{2}λ_{2} + m_{3}λ_{3} & = & 0 \\ λ_{0}^{2} + m_{1}λ_{1}^{2} + m_{2}λ_{2}^{2} + m_{3}λ_{3}^{2} & = & nλ_{0} \end{aligned}

whence we get

σ_{e} = m_{2} = \frac{π_{0} − n(λ_{1}λ_{3} + λ_{0})(λ_{0} − λ_{2})}{π_{2}}.  (23)

Thus, Theorem 2.2 gives the following result.

Corollary 2.4 A connected δ-regular graph Γ with n vertices and eigenvalues λ_{0}(= δ) > λ_{1} > λ_{2} > λ_{3} is strongly distance-regular if and only if the harmonic mean of the numbers s_{2}(u) = 1 + δ + n_{2}(u), u ∈ V, satisfies

H = n − \frac{4nσ_{o}σ_{e}}{(n − 1)Σ^{2} + 4σ_{o}(σ_{e} + 1 − Σ)},  (24)

where σ_{e} is given by (23), σ_{o} = n − σ_{e} − 1 and Σ = ∑_{i=0}^{3}(π_{0}/π_{i}). □

The above result slightly improves a similar characterization given in [9], in terms of the degree of the graph Γ_{3}, and where the additional condition λ_{2} = −1 was required.

Let us now consider the case a = c. In this case, an strongly regular graph satisfying this condition is also called an (n, k, c)-graph (see Cameron [4]) and, consequently, we will speak about an (n, k, c)-strongly distance-regular graph.

Corollary 2.5 Let Γ be a regular graph with eigenvalues λ_{0} > λ_{1} > ⋯ > λ_{d} and alternating polynomial P. Then Γ is an (n, k, c)-strongly distance-regular graph if and only if any of the following conditions hold.

(a) The harmonic mean H of the numbers s_{d−1}(u), u ∈ V, is

H = \frac{nP (λ_{0})}{P (λ_{0})^{2} + n − 1}.  (25)

(b) The distance-d graph Γ_{d} is k-regular with degree

k = \frac{n(n − 1)}{P (λ_{0})^{2} + n − 1}.  (26)

In such a case, the other parameters of Γ_{d} are (a =)c = k(k − 1)/(n − 1).

Proof . We only prove sufficiency for condition (a), the other reasonings being almost straightforward from previous material. Note that the right-hand expression in (25) corresponds to the value of the function Ψ at t = 0 satisfying

Ψ(0) ≤ Ψ(t_{0}) = Ψ_{max} ≤ H.

Then, if equality (25) holds, it must be t_{0} = 0, Ψ_{max} = H and, by Theorem 2.2, Γ is strongly distance-regular. Moreover, for such a value of t_{0}, and using that P (λ_{0}) = 2Σ_{e} + 1 = 2Σ_{o} − 1 and σ_{o} = n − σ_{e} − 1, Eq. (16) yields

\frac{σ_{o}}{σ_{e}} \frac{P (λ_{0}) − 1}{P (λ_{0}) + 1} = \frac{σ_{o}}{σ_{e}} \frac{Σ_{e}}{Σ_{o}} = 1 ⇒ \frac{Σ_{e}}{σ_{e}} = \frac{Σ_{o}}{σ_{o}} and σ_{e} = \frac{(n − 1)(P (λ_{0}) − 1)}{2P (λ_{0})}

whence (13) gives

a = c = k − k^{2} \frac{Σ_{e}^{2}}{σ_{e}^{2}} = k − k^{2} \frac{P (λ_{0})^{2}}{(n − 1)^{2}} = \frac{k(k − 1)}{n − 1}

(where we have used that P (λ_{0})^{2} = (\frac{n}{k−1} − 1)(n − 1)), as claimed. □

Notice that, as before, the characterization in (a) implies that of (b). The latter was given in [5] for diameter d = 3, whereas the general case was solved in [11].

Let us now consider the antipodal case. Note that a distance-regular graph Γ is an antipodal r-cover if and only if its distance-d graph Γ_{d} is constituted by disjoint copies of the complete graph K_{r}, which can be seen as a (unconnected) (n, r − 1; r − 2, 0)- strongly regular graph.

Corollary 2.6 Let Γ be a regular graph with n vertices, eigenvalues λ_{0} > λ_{1} > ⋯ > λ_{d}, Σ = ∑_{i=0}^{d}(π_{0}/π_{i}), and sum of even multiplicities σ_{e}. Then Γ is an r-antipodal distance-regular graph if and only if σ_{e} = Σ_{e} and the harmonic mean of the numbers s_{d−1}(u), u ∈ V, is

H = n (1 − \frac{2}{Σ}) − 1.  (27)

In this case, r = 2n/Σ.

Proof . Again we only prove sufficiency. Let Σ = P (λ_{0}) + 1. With σ_{e} = Σ_{e}, Eq. (18) particularizes to

Ψ_{max} = n − \frac{σ_{o}}{Σ_{o}} = n − \frac{n − Σ_{e} − 1}{Σ_{o}} = n − \frac{2n}{Σ} − 1,

where we have used that Σ_{o} = Σ_{e} + 1 = Σ/2. Hence, by Theorem 2.2, Γ is strongly distance-regular, with Γ_{d} having degree k = (2n/Σ) − 1. Finally, the antipodal character comes from (13), giving c = 0 and a = k − 1, so that r = k + 1 = 2n/Σ. □

A similar result in terms of r can be found in [7] without using the condition on the multiplicity sum σ_{e} = Σ_{e}.

References

[1] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes. Benjamin/Cummings, Menlo Park, CA, 1984.

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

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

[4] P.J. Cameron, Strongly regular graphs, in: Selected Topics in Graph Theory, edited by L.J. Beineke and R.J. Wilson. Academic Press, New York, 1978, 337– 360.

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

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

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

[8] M.A. Fiol, Algebraic characterizations of distance-regular graphs, Discrete Math. (Proc. 11th Inter. Conf. on Formal Power Series and Algebraic Combinatorics, Barcelona, 7-11 June 1999), to appear.

[9] M.A. Fiol, Some spectral characterizations of strongly distance-regular graphs. Combin. Probab. Comput., to appear.

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

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

[12] 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.

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

[14] 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.

[15] C.D. Godsil, Algebraic Combinatorics. Chapman and Hall, London/New York, 1993.

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