An Eigenvalue Characterization of Antipodal 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: July 19, 1997; Accepted: November 14, 1997.

Abstract

Let Γ be a regular (connected) graph with n vertices and d + 1 distinct eigenvalues. As a main result, it is shown that Γ is an r-antipodal distanceregular graph if and only if the distance graph Γ_{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.

AMS subject classifications. 05C50 05E30

1 Introduction

The core of spectral graph theory is to describe the properties of a graph by its spectrum and find conditions that cospectral graphs may not share. For instance, consider the following question: Can we see from the spectrum of a graph with diameter D, say, whether it is distance-regular? Since a long time it was known that the answer to this question is ‘yes’ when D ≤ 2 and ‘not’ if D ≥ 4. Then, on the basis of these results, it had been conjectured (cf. Cvetković, Doob, and H. Sachs [5]) that the answer is also ‘yes’ for D = 3, but recently Haemers [19] disproved the conjecture constructing some counterexamples. So, 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 [8] showed that, in the case D = 3, such a condition could be the number n_{d} of vertices at “extremal distance” D = d (where d + 1 is the number of distinct eigenvalues) from each vertex. Independently, Garriga, Yebra and the author [13] settled the case n_{d} = 1 (for any value of D), that is the case of 2-antipodal distance-regular graphs. Finally, Garriga and the author [11] solved the general case, characterizing distanceregular 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.)

An striking peculiarity of the case n_{d} = 1 (2-antipodal graphs) is that, in fact, we do not need to look at the whole spectrum, but only at the distinct eigenvalues (its multiplicities can be deduced from them.) The main contribution of this paper is to show that this is also true for r-antipodal distance-regular graphs. As a main result it is shown that an antipodal regular graph is distance-regular if, and only if, its ‘fibres’ (that is, the sets of antipodal vertices) have all cardinality r, a number depending on the order and the eigenvalues of the graph. This result is obtained via an spectral bound for the k-independence number, or (standard) independence number of the k-th power of the graph, and the study of the limit case in which such a bound is attained.

Let us now fix the terminology and notation used throughout the paper. Thus, Γ = (V, E) denotes a connected (simple and finite) graph with order n := |V | and adjacency matrix A = A(Γ). The distance between two vertices u, v ∈ V is represented by dist(u, v). The eccentricity of a vertex u is ecc(u) := max_{v∈V} dist(u, v), and the diameter of Γ is D := max_{u∈V} ecc(u). As usual, Γ_{k}(u), 0 ≤ k ≤ ecc(u), denotes the set of vertices at distance k from u, and Γ_{1}(u) is simply written as Γ(u). The distance-k graph Γ_{k}, 0 ≤ k ≤ D, is the (possibly non-connected) graph on V where two vertices are adjacent whenever they are at distance k in Γ. Thus, in particular, Γ_{0} is the trivial graph on n vertices, and Γ_{1} = Γ. The adjacency matrix of Γ_{k}, denoted by A_{k}, is usually referred as the distance-k matrix of Γ. A graph Γ of diameter D is called antipodal if, for any given vertex u ∈ V, the set {u}∪Γ_{D}(u) consists of vertices which are mutually at distance D. In other words, there exists a partition of the vertex set into classes (called the fibres of Γ) with the property that two distinct vertices are in the same class iff they are at distance D (see, for instance, Godsil [17].) If all the fibres have the same cardinality, say r, we say that Γ is an r-antipodal graph.

We index all the involved matrices and vectors by the vertices of Γ. Moreover, for any vertex u ∈ V, we denote by e_{u} the u-th unitary vector of the canonical basis of ℝ^{n}. Thus, the characteristic vector of a vertex set U ⊂ V is just e_{U} := ∑_{u∈U} e_{u}. As usual, the adjacency matrix A of Γ is seen as an endomorphism of ℝ^{n}. We let a polynomial p ∈ ℝ_{k}[x] operate on ℝ^{n} by the rule pw := p(A)w, where w ∈ ℝ^{n}, and the matrix is not specified unless some confusion may arise. As usual, J denotes the n × n matrix with all entries equal to 1, and similarly j ∈ ℝ^{n} is the all-1 vector. The spectrum of Γ is the set of eigenvalues of A together with their multiplicities:

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

where the superscripts denote multiplicities. Recall that the largest positive eigenvalue λ_{0} (with multiplicity one if Γ is connected) has an eigenvector ν = (ν_{1}, ν_{2}, …, ν_{n})^{⊤}, which can be taken with all its entries positive, and we will consider it normalized in such a way that its smallest entry is 1. Thus, ν = j when Γ is regular. In some of our results we do not use the whole spectrum, but only the mesh (set) constituted by all the distinct eigenvalues, that is

ev Γ := {λ_{0}, λ_{1}, …, λ_{d}}

in decreasing order: λ_{0} > λ_{1} > ⋯ > λ_{d}. (We follow here the notation of Godsil [17].) Associated to such a mesh, we make ample use of the moment-like positive numbers π_{i}, which are defined as

π_{i} = ∏_{j=0,j≠i}^{d} |λ_{i} − λ_{j}| (0 ≤ i ≤ d).  (1)

As it is well-known, if Γ is connected, its diameter is at most d = | ev Γ| − 1 (see, for instance, Biggs [2].) Then, we say that Γ is extremal when it has “spectrally maximum” diameter D = d. We also say that Γ is diametral when all its vertices have eccentricity equal to the diameter.

In order to obtain bounds on the diameter of a graph in terms of its eigenvalues, Garriga, Yebra and the author [12] used the so-called alternating polynomial P_{k}, 0 ≤ k ≤ d − 1, which is the (unique) polynomial satisfying

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

where ∥p∥_{∞} = max_{1≤i≤d} |p(λ_{i})|. When k = d−1, we simply speak about the alternating polynomial, P := P_{d−1}. In [12] it was proved that the k-alternating polynomial is characterized by taking k + 1 alternating values ±1 at ev Γ, with P_{k}(λ_{1}) = 1 and P_{k}(λ_{d}) = (−1)^{k}. In particular, for k = d − 1, this characterization gives P (λ_{i}) = (−1)^{i+1}, 1 ≤ i ≤ d, which together with Lagrange interpolation yields

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

Some particular cases of these polynomials were also considered by Van Dam and Haemers in [7].

We finally recall that the Kronecker product of two matrices A = (a_{ij}) and B, denoted by A ⊗ B, is obtained by replacing each entry a_{ij} with the matrix a_{ij}B, for all i and j. Then, if u and v are eigenvectors of A and B, with corresponding eigenvalues λ and μ, respectively, then u ⊗ v (seeing u and v as matrices) is an eigenvector of A ⊗ B, with eigenvalue λμ.

2 The k-independence number

Let Γ = (V, E) be a graph with diameter D. A vertex set U ⊂ V is said to be kindependent, for some integer k ≥ 0, if their vertices are mutually at distance greater than k. By convention, U = {u} will be supposed to be k-independent for every k. The k-independence number α_{k} of Γ is then defined as the cardinality of a maximum k-independent set. Thus, trivially, α_{0} = n and α_{k} = 1 if k ≥ D. Moreover, α_{1} ≡ α is the standard independence or stability number. Notice also that α_{k} is, in fact, the independence number of the k-th power of Γ. In [10], Garriga and the author showed that, when 0 ≤ k ≤ d − 1, the k-independence number of a regular graph satisfies the following spectral upperbound

α_{k} < \frac{2n}{P_{k}(λ_{0}) + 1} + 1.

where P_{k} is the k-alternating polynomial of Γ. This was derived as a consequence of a result on the (s, t)-diameter, which is the maximum distance between two subsets of s ant t vertices. Here we begin with a result which slightly improves this bound and, more important, tell us what happens when the bound is attained. Although both bounds are very similar, the method used here is quite different from that used in [10]. Roughly speaking, we must now use a more precise technique, which, rather than the distance between two subsets, should take into account all the distances between vertices of a unique subset. As noted by the referee, the improved bound can also be derived by using ‘eigenvalue interlacing’ (see Haemers’ survey [18] on this versatile technique.) More details about this approach can be found in [9].

Theorem 2.1 Let Γ be a connected regular graph with n vertices, mesh of eigenvalues ev Γ = {λ_{0}, λ_{1}, …, λ_{d}}, and k-alternating polynomial P_{k}. Then, for any 0 ≤ k ≤ d − 1, its k-independence number satisfies

α_{k} ≤ \frac{2n}{P_{k}(λ_{0}) + 1}.  (3)

If equality holds for some (maximum) k-independent set U, then there exists a polynomial p ∈ ℝ_{d}[x] (independent of U) such that

pe_{u} = e_{U\{u}}.  (4)

for every vertex u ∈ U.

P roof. Let U = {u_{0}, u_{1}, …, u_{r−1}} be a maximum k-independent set, where r = |U| = α_{k}. From the k-alternating polynomial P_{k} of Γ, we consider the polynomial Q_{k} := \frac{r}{2}P_{k} + \frac{r}{2} −1. Then, since P_{k}(λ_{0}) ≥ 1 and −1 ≤ P_{k}(λ_{i}) ≤ 1 for i ≠ 0, the matrix Q_{k}(A) has eigenvalues Q_{k}(λ_{0}) ≥ r − 1 and Q_{k}(λ_{i}) satisfying −1 ≤ Q_{k}(λ_{i}) ≤ r − 1 for 1 ≤ i ≤ d. Now consider the matrix B := A(K_{r}) ⊗ Q_{k}(A). For instance, for r = 3 we have

B = ( \begin{matrix}O & Q_{k}(A) & Q_{k}(A) \\ Q_{k}(A) & O & Q_{k}(A) \\ Q_{k}(A) & Q_{k}(A) & O \end{matrix} ) .

The complete graph K_{r} has eigenvalues r − 1 and −1 (with multiplicity r − 1), with corresponding orthogonal eigenvectors j ∈ ℝ^{r} and ϕ_{i} = (1, ω^{i}, ω^{2i}, …, ω^{(r−1)i})^{⊤}, 1 ≤ i ≤ r − 1, where ω is a primitive r-th root of 1, say ω := e^{j \frac{2π}{r}}. Consequently, each eigenvector u of Q_{k}(A) with eigenvalue Q_{k}(λ), λ ∈ ev Γ, gives rise to the eigenvalues (r − 1)Q_{k}(λ) and −Q_{k}(λ) (with multiplicity r − 1), with corresponding orthogonal eigenvectors u_{0} := j ⊗ u and u_{i} := ϕ_{i} ⊗ u, 1 ≤ i ≤ r − 1. Thus, when λ ≠ λ_{0}, we have −1 ≤ Q_{k}(λ) ≤ r − 1 and hence the corresponding eigenvalues of B are within the interval [−(r − 1), (r − 1)^{2}]. Moreover, B has maximum eigenvalue (r − 1)Q_{k}(λ_{0}) ≥ (r − 1)^{2}. Now take the vector f_{U} := (e_{u_{0}}^{⊤}|e_{u_{1}}^{⊤}| ⋯ |e_{u_{r−1}}^{⊤})^{⊤} ∈ ℝ^{rn}, and consider its spectral decomposition:

f_{U} = ∑_{i=0}^{r−1} \frac{⟨f_{U}, j_{i}⟩}{∥j_{i}∥^{2}}j_{i} + z_{U} = \frac{1}{n}j_{0} + z_{U}  (5)

where z_{U} ∈ ⟨j_{0}, j_{1}, …, j_{r−1}⟩^{⊥}, and we have used that ⟨f_{U}, j_{0}⟩ = r, ∥j_{i}∥^{2} = rn, and ⟨f_{U}, j_{i}⟩ = ∑_{j=0}^{r−1} ω^{ij} = 0, for any 1 ≤ i ≤ r − 1. From (5), we get

∥z_{U}∥^{2} = ∥f_{U}∥^{2} − \frac{1}{n^{2}} ∥j_{0}∥^{2} = r (1 − \frac{1}{n}) .

Since there is no path of length ≤ k between any pair of vertices of U, (Q_{k}(A))_{u_{i}u_{j}} = 0 for any i ≠ j. Thus,

0 = ⟨Bf_{U}, f_{U}⟩ = ⟨\frac{(r − 1)Q_{k}(λ_{0})}{n}j_{0} + Bz_{U}, \frac{1}{n}j_{0} + z_{U} ⟩

= \frac{r(r − 1)Q_{k}(λ_{0})}{n} + ⟨Bz_{U}, z_{U}⟩
≥ \frac{r(r − 1)Q_{k}(λ_{0})}{n} − (r − 1)∥z_{U}∥^{2} = \frac{r(r − 1)}{n}(Q_{k}(λ_{0}) − n + 1).

Therefore, we get

Q_{k}(λ_{0}) = \frac{α_{k}}{2} P_{k}(λ_{0}) + \frac{α_{k}}{2} − 1 ≤ n − 1

and (3) follows.

From the above, notice that equality holds iff

Bz_{U} = −(r − 1)z_{U}.  (6)

By (5), we infer that, if e_{u_{i}} = \frac{1}{n}j +z_{i}, z_{i} ∈ j^{⊥}, represents the spectral decomposition of e_{u_{i}} in ℝ^{n} ≅ ⨁_{j=0}^{d} Ker(A − λ_{j}I), 0 ≤ i ≤ r − 1, then z_{U} = (z_{0}^{⊤}|z_{1}^{⊤}| ⋯ |z_{r−1}^{⊤})^{⊤}. Hence, (6) gives the r vectorial equations:

∑_{i=0,i≠j}^{r−1} Q_{k}z_{i} = −(r − 1)z_{j} (0 ≤ j ≤ r − 1)

which are equivalent to

Q_{k}z_{i} = (r − 2)z_{i} − ∑_{j=0,j≠i}^{r−1} z_{j} (0 ≤ i ≤ r − 1).  (7)

Let H be the Hoffman polynomial defined by its values at ev Γ, namely H(λ_{0}) = n, H(λ_{i}) = 0, 1 ≤ i ≤ d, and satisfying H(A) = J (see Hoffman [20].) Now we claim that the searched polynomial is p = H − Q_{k} + (r − 2), whose value at λ_{0} is p(λ_{0}) = n − (n − 1) + (r − 2) = r − 1. Indeed, using (7), we get

pe_{u_{i}} = p (\frac{1}{n}j + z_{i}) = \frac{r − 1}{n}j − Q_{k}z_{i} + (r − 2)z_{i}
= \frac{r − 1}{n}j + ∑_{j=0,j≠i}^{r−1} z_{j} = ∑_{j=0,j≠i}^{r−1} e_{u_{j}} = e_{U\\{u_{i}\}} (0 ≤ i ≤ r − 1),

which concludes the proof of the theorem. □

For general k, the given bound (3) is sharp. For instance, in [14] it was shown that the alternating polynomial P (k = d − 1) of an r-antipodal distance-regular graph on n vertices satisfies P (λ) = \frac{2}{r}n − 1, whence we get α_{d−1} ≤ r. In the next section we prove again, for completeness, such a result on P by using Theorem 2.1, but first we will pay attention to some other straightforward consequences of the theorem.

Using the language of Coding Theory, notice that (3) yields a bound for the size of any code C in Γ with minimum distance δ (that is the minimum distance between two distinct ‘code words’ —vertices of Γ.) Namely,

|C| ≤ \frac{2n}{P_{δ−1}(λ_{0}) + 1}.

In the spirit of [21], where a spectral upper bound is given on the minimum distance between t subsets of same size, we can consider the t-diameter D_{t} defined by

D_{t} := max_{U⊂V,|U|=t}{ min_{u,v∈U} dist(u, v)},

as it was done in [4, 16]. The standard diameter is then D = D_{2}. From our theorem we have the following result.

Corollary 2.2 Let Γ be a regular graph on n vertices, and with t-diameter D_{t}. Then,

P_{k}(λ_{0}) > \frac{2n}{t} − 1 ⇒ D_{t} ≤ k.  (8)

P roof. From the hypothesis and Theorem 2.1 we get α_{k} < t, which implies the result. □

By using the positive eigenvector ν of the Introduction, similar results can be obtained for non-regular graphs. So, from the vector f_{U} = ∑_{i=0}^{r−1} \frac{1}{ν_{u_{i}}} e_{u_{i}}, instead of (3) we now get

α_{k} ≤ \frac{2∥ν∥^{2}}{P_{k}(λ_{0}) + 1}  (9)

whence

P_{k}(λ_{0}) > \frac{2∥ν∥^{2}}{t} − 1 ⇒ D_{t} ≤ k.  (10)

Spectral bounds on the t-diameter, in terms of the i-th largest eigenvalue (in absolute value) of the adjacency and Laplacian matrices can be found in Kahale [21] and Chung, Delorme, and Solé [4], respectively.

3 Antipodal Distance-Regular Graphs

In this section we study two spectral characterizations of antipodal distance-regular graphs. The fist one establishes that the distance-regular graphs which are antipodal are characterized by their eigenvalue multiplicities. The second characterization was already commented in the Introduction, and states that we can see from the spectrum of a regular graph, and the cardinalities of the “extremal fibres” (the sets of antipodal vertices at extremal distance) whether the graph is an antipodal distance-regular graph. Let us begin by recalling some definitions and known results which are on the basis of our work.

3.1 Distance-regular graphs

A (connected) graph Γ with diameter D is distance-regular if, for any two vertices u and v ∈ Γ_{k}(u), 0 ≤ k ≤ D, the numbers a_{k}(u) = |Γ_{k}(u) ∩ Γ(v)|, b_{k}(u) = |Γ_{k+1}(u) ∩ Γ(v)|, and c_{k}(u) = |Γ_{k−1}(u) ∩ Γ(v)| do not depend on u and v, but only on k. Some basic references dealing with this topic are Bannai and Ito [1], Biggs [2], and Brouwer, Cohen and Neumaier [3]. A well-known characterization of such graphs is the following: a graph Γ, with adjacency matrix A and diameter D, is distanceregular if and only if, for any 0 ≤ k ≤ D, its distance-k matrix A_{k} is a polynomial of degree k in A. Recently, Garriga, Yebra, and the author [14] showed that, if Γ is extremal and diametral, the condition on A_{D} suffices, as stated in the following theorem.

Theorem 3.1 A graph Γ with adjacency matrix A and diameter D is distanceregular if and only if Γ is extremal, diametral, and its distance-D matrix A_{D} is a polynomial of degree D in A. □

From this result, and generalizing some results of Haemers and Van Dam [19, 6, 8] (the case d = 3) , and Garriga, Yebra and the author [13] (the case |Γ_{d}(u)| = 1), the following spectral characterization was also obtained in [11]:

Theorem 3.2 A regular graph Γ on n vertices, with spectrum sp Γ = {λ_{0}, λ_{1}^{m_{1}}, ⋯, λ_{d}^{m_{d}}}, is distance-regular if and only if

|Γ_{d}(u)| = \frac{n}{π_{0}^{2} ∑_{i=0}^{d} \frac{1}{m_{i}π_{i}^{2}}}  (11)

for every vertex u of Γ. □

Notice that the cases d = 1, 2 are trivial, in the sense that every (connected) regular graph Γ with two or three different eigenvalues is distance-regular. More precisely, Γ = K_{n} if d + 1 = 2, and Γ is strongly regular when d + 1 = 3. See, for instance, Godsil [17].

3.2 Antipodal graphs

Let us now turn our attention to the antipodal graphs. In this context, another consequence of Theorem 2.1 is the following result, already proved in [15] using a different approach (see also [16].)

Proposition 3.3 Let Γ be an extremal r-antipodal regular graph, with n vertices and diameter D, and let A_{D} be the adjacency matrix of Γ_{D}. If A_{D} belongs to the algebra generated by A, then A_{D} = J −R(A), where R := \frac{r}{2}P − \frac{r}{2} +1 and P is the alternating polynomial of Γ.

P roof. The first part of the proof goes as in [15]: We know that sp Γ_{D} = {(r −1)^{σ}, −1^{n−σ}}, where σ = n/r stands for the number of fibres. By the hypothesis, there exists a polynomial p ∈ ℝ_{d}[x] such that p(A) = A_{D}, so that p(λ_{0}) = r − 1 and p(λ_{i}) ∈ {r − 1, −1} for 1 ≤ i ≤ d. Since Γ is regular, the polynomial R := H − p ∈ ℝ_{d}[x] satisfies R(A) = J − A_{D} and hence R(λ_{0}) = n − r + 1, R(λ_{i}) ∈ {1, 1 − r} for 1 ≤ i ≤ d. Moreover, since each entry of R(A) corresponding to a diametral pair of vertices is zero, it must be R ∈ ℝ_{d−1}[x]. Let P := \frac{2}{r}R + 1 − \frac{2}{r}. Then, P (λ_{0}) = \frac{2n}{r} − 1, and P (λ_{i}) = ±1 for i ≠ 0. The second part of the proof consists in proving that P is indeed the alternating polynomial P_{d−1} of Γ. But, from the above, r = α_{d−1} = 2n/(P (λ_{0}) + 1), so that, using (3) we get P (λ_{0}) ≥ P_{d−1}(λ_{0}) and hence P = P_{d−1}. □

An interesting example of graphs satisfying the above hypotheses are the rantipodal distance-regular graphs. Indeed, they are extremal, D = d, and its ‘distanced polynomial’ p_{d} satisfies A_{d} = p_{d}(A). Thus, from p_{d} = H − \frac{r}{2}P + \frac{r}{2} − 1, we infer that their alternating polynomial satisfies P (λ_{0}) = \frac{2n}{r} − 1 and hence

r = \frac{2n}{P (λ_{0}) + 1} = 2n (∑_{i=0}^{d} \frac{π_{0}}{π_{i}} )^{−1} ,  (12)

where we have used (2). As mentioned above, this property of antipodal distanceregular graphs was already proved in [15]. At the end of the section, we will see that this condition is also sufficient to assure that an r-antipodal (regular) graph is distance-regular. Next, we use the above results to give a characterization of those distance-regular graphs which are antipodal, in terms of their eigenvalue multiplicities. With this aim, note first that, from the above expression of p_{d}, we have p_{d}(λ_{i}) = \frac{r}{2}((−1)^{i} + 1) − 1 for 1 ≤ i ≤ d.

Theorem 3.4 A distance-regular graph Γ on n vertices, with spectrum sp Γ = {λ_{0}, λ_{1}^{m_{1}}, …, λ_{d}^{m_{d}}}, is r-antipodal if and only if

m_{i} = \frac{π_{0}}{π_{i}} (i even);  m_{i} = (r − 1)\frac{π_{0}}{π_{i}} (i odd).  (13)

P roof. It is well-known that the multiplicities of a distance-regular graph can be obtained from the distance-d polynomial p_{d} and the eigenvalues using the following formula:

m_{i} = \frac{ϕ_{0}p_{d}(λ_{0})}{ϕ_{i}p_{d}(λ_{i})} (0 ≤ i ≤ d)  (14)

where ϕ_{i} := ∏_{j=0,j≠i}^{d}(λ_{i} − λ_{j}) = (−1)^{i}π_{i} (see, for instance, Bannai and Ito [1].) But, if Γ is r-antipodal we have already seen that p_{d}(λ_{i}) = r − 1 when i is even, and p_{d}(λ_{i}) = −1 when i is odd, giving (13). Conversely, from (13) and (14) we get

p_{d}(λ_{i}) = p_{d}(λ_{0}) (i even);  p_{d}(λ_{i}) = \frac{−p_{d}(λ_{0})}{r − 1} (i odd).  (15)

To compute the value of p_{d}(λ_{0}), we first notice that

0 = tr A_{d} = tr(p_{d}(A)) = ∑_{i=0}^{d} m_{i}p_{d}(λ_{i}) = p_{d}(λ_{0}) ∑_{i=0}^{d} \frac{ϕ_{0}}{ϕ_{i}}

where we have used the value of m_{i}p_{d}(λ_{i}), 0 ≤ i ≤ d, given by (14). Hence,

σ := ∑_{i even} \frac{π_{0}}{π_{i}} = ∑_{i odd} \frac{π_{0}}{π_{i}}

and, as the multiplicities add up to n,

∑_{i=0}^{d} m_{i} = σ + (r − 1)σ = n

whence σ = n/r. Consequently, by substituting the multiplicities given by (13) into (11), we get

p_{d}(λ_{0}) = |Γ_{d}(u)| = n ( ∑_{i even} \frac{π_{0}}{π_{i}} + \frac{1}{r − 1} ∑_{i odd} \frac{π_{0}}{π_{i}} )^{−1} = \frac{n}{σ} (1 + \frac{1}{r − 1})^{−1} = r − 1.

Thus, by (15), the (0, 1)-matrix p_{d}(A) has eigenvalues r − 1 (with multiplicity σ) and −1 (with multiplicity (r − 1)σ). Consequently, it must be the adjacency matrix of the graph constituted by several (σ) copies of K_{r}. In other words, Γ is r-antipodal, as claimed. □

The case r = 2, which results in

m_{j} = \frac{π_{0}}{π_{j}} (0 ≤ j ≤ d),  (16)

was studied in [13].

Theorem 3.5 Let Γ = (V, E) be a connected regular graph on n vertices, with mesh of eigenvalues ev Γ = {λ_{0}, λ_{1}, …, λ_{d}}. Then Γ is an r-antipodal distance-regular graph if and only if the distance-d graph Γ_{d} is constituted by disjoint copies of the complete graph K_{r} with

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

P roof. We have already proved necessity as a consequence of Proposition 3.3, from which we derived (12). To prove sufficiency note that, by hypothesis, any vertex u of Γ belongs to an (d − 1)-independent set with α_{d−1} = r vertices. Thus, from Theorem 2.1, there exists a polynomial p of degree d such that pe_{u} = e_{Γ_{d}(u)} for every u ∈ V. That is,

p(A) = A_{d}.

Consequently, since Γ is clearly both extremal and diametral, Theorem 3.1 applies, and Γ is an (r-antipodal) distance-regular graph. □

Acknowledgment. Work supported in part by the Spanish Research Council (Comisión Interministerial de Ciencia y Tecnología, CICYT) under projects TIC 92-1228-E and TIC 94-0592. I am indebted to the referee for helpful comments.

References

[1] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes. Benjamin-Cummings Lecture Note Ser. 58, London (1993).

[2] N. Biggs, Algebraic Graph Theory. Cambridge University Press, Cambridge, UK, 1993.

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

[4] F. R. K. Chung, C. Delorme, and P. Solé, k-Diameter and spectral multiplicity, submitted.

[5] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs—Theory and Applications. Deutscher Verlag der Wissenschaften, Berlin, 1980; Academic Press, New York, 1980; second edition: 1982; Russian translation: Naukova Dumka, Kiev, 1984; third edition: Johann Ambrosius Barth, Heidelberg, 1995

[6] E. R. van Dam, Graphs with Few Eigenvalues. Ph.D. Thesis, Tilburg University, 1996.

[7] E. R. van Dam and W. H. Haemers, Eigenvalues and the diameter of graphs, Linear and Multilinear Algebra 39 (1995), 33–44.

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

[9] M. A. Fiol, Eigenvalue interlacing and weight parameters of graphs, submitted.

[10] M. A. Fiol and E. Garriga, The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs, submitted.

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

[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, From regular boundary graphs to antipodal distance-regular graphs, J. Graph Theory, to appear.

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

[15] M. A. Fiol, E. Garriga and J. L. A. Yebra, Boundary graphs: The limit case of a spectral property (I), submitted.

[16] E. Garriga, Contribució a la Teoria Espectral de Grafs: Problemes Mètrics i Distancia-Regularitat. Ph.D. Thesis, Universitat Politècnica de Catalunya, 1997.

[17] C. D. Godsil, Algebraic Combinatorics. Chapman and Hall, 1993.

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

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

[20] A. J. Hoffman, On the polynomial of a graph, Amer. Math. Monthly 70 (1963) 30–36.

[21] N. Kahale, Isoperimetric inequalities and eigenvalues, SIAM J. Discrete Math. 10, No. 1 (1997) 30–40.