Some Applications of the Proper and Adjacency Polynomials in the Theory of Graph Spectra

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: February 22, 1997; Accepted: September 15, 1997.

Abstract

Given a vertex u ∈ V of a graph Γ = (V, E), the (local) proper polynomials constitute a sequence of orthogonal polynomials, constructed from the so-called u-local spectrum of Γ. These polynomials can be thought of as a generalization, for all graphs, of the distance polynomials for the distance-regular graphs. The (local) adjacency polynomials, which are basically sums of proper polynomials, were recently used to study a new concept of distance-regularity for non-regular graphs, and also to give bounds on some distance-related parameters such as the diameter. Here we develop the subject of these polynomials and gave a survey of some known results involving them. For instance, distance-regular graphs are characterized from its spectrum and the number of vertices at “extremal distance” from each of their vertices. Afterwards, some new applications of both, the proper and adjacency polynomials, are derived, such as bounds for the radius of Γ and the weight k-excess of a vertex. Given the integers k, μ ≥ 0, let Γ_{k}^{μ}(u) denote the set of vertices which are at distance at least k from a vertex u ∈ V, and there exist exactly μ (shortest) k-paths from u to each of such vertices. As a main result, an upper bound for the cardinality of Γ_{k}^{μ}(u) is derived, showing that |Γ_{k}^{μ}(u)| decreases at least as O(μ^{−2}), and the cases in which the bound is attained are characterized. When these results are particularized to regular graphs with four distinct eigenvalues, we reobtain a result of Van Dam about 3-class association schemes, and prove some conjectures of Haemers and Van Dam, about the number of vertices at distance three from every vertex of a regular graph with four distinct eigenvalues —setting k = 2 and μ = 0— and, more generally, the number of non-adjacent vertices to every vertex u ∈ V, which have μ common neighbours with it.

AMS subject classifications. 05C50 05C38 05E30 05E35

1 Introduction

The interactions between algebra and combinatorics have proved to be a fruitful subject of study, as shown by the increasing amount of literature on the subject that has appeared in the last two decades. Some good references are the text of Bannai and Ito [2], Godsil’s recent book [24], and the very recent Handbook of Combinatorics [26]. In particular, a considerable effort has been devoted to the use of algebraic techniques in the study of graphs as, for instance, the achievement of bounds for (some of) their parameters in terms of their (adjacency or Laplacian) spectra. Classic references dealing with this topic are the books of Biggs [4], Cvetković, Doob, and Sachs [9], and the comprehensive text about distance-regular graphs of Brouwer, Cohen and Neumaier [5]. (See also the surveys of Cvetković and Doob [8] and Schwenk and Wilson [38].) In this context, some of the recent work has been specially concerned with the study of metric parameters, such as the mean distance, diameter, radius, isoperimetric number, etc. See, for instance, the papers of Alon and Milman [1], Biggs [3], Chung et.al. [6, 7], Van Dam and Haemers [11], Delorme and Solé [13], Kahale [31], Mohar [32], Quenell [36], Sarnak [39], and Garriga, Yebra, and the author [16, 19, 22]. We must also mention here Haemers’ thesis [27], an account of which can be found in his recent paper [28]. Somewhat surprisingly, in some of these works the study of the limit cases —in which the derived bounds are attained— has revealed the presence of high levels of structure in the considered graphs. See, for instance, the papers of Haemers and Van Dam, [29, 12], and Garriga, Yebra, and the author [17, 18, 20, 21], and also the recent theses of Van Dam [10], Garriga [23] and Rodríguez [37]. In their study, Garriga and the author introduced two families of orthogonal polynomials of a discrete variable, constructed from the so-called local spectrum of the graph. The members of one of these families are called the “proper polynomials,” and can be seen as a generalization, for all graphs, of the distance polynomials for the distance-regular graphs. The other family, constituted by the “adjacency polynomials,” is closely related to the first one, since its members are basically sums of consecutive proper polynomials. Both families were mainly used to study a new concept of distance-regularity for non-regular graphs, and also to give bounds on some distance-related parameters such as the diameter and the radius [16]. Here, after introducing these polynomials and recalling its main properties, we survey some of the main known results related to them. For example, a regular graph with d + 1 different eigenvalues is distance-regular if, and only if, the number of vertices at distance d from any given vertex is the value of a certain expression which only depends on the spectrum of the graph [17]. Afterwards, we further investigate some new applications of these polynomials, deriving new bounds for the radius of a graph and the “weight k-excess” of a vertex. Generalizing these results, and grouping ideas of Van Dam [10], and Garriga and the author [17, 18], we also derive bounds for the cardinalities of some special vertex subsets, and study the limit cases in which such bounds are attained. The particularization of these results to the case of regular graphs with four distinct eigenvalues proves some conjectures of Haemers and Van Dam [29, 12, 10]

In the rest of this introductory section we recall some basic concepts and results, and fix the terminology used throughout the paper. As usual, Γ = (V, E) denotes a (simple and finite) connected graph with order n := |V |. For any vertex u ∈ V, Γ(u) denotes the set of vertices adjacent to u, and δ(u) := |Γ(u)| stands for its degree. The distance between two vertices is represented by ∂(u, v). The eccentricity of a vertex u is ε(u) := max_{v∈V} ∂(u, v), the diameter of Γ is D(Γ) := max_{u∈V} ε(u), and its radius is r(Γ) := min_{u∈V} ε(u). As usual, Γ_{k}(u), 0 ≤ k ≤ ε(u), denotes the set of vertices at distance k from u, and Γ_{k}, 0 ≤ k ≤ D, is the graph on V where two vertices are adjacent whenever they are at distance k in Γ. Thus, Γ_{1}(u) = Γ(u) and Γ_{1} = Γ. The k-neighbourhood of u is then defined as N_{k}(u) := ⋃_{l=0}^{k} Γ_{l}(u) = {v : ∂(u, v) ≤ k}. A closely related parameter is the so-called k-excess of u, denoted by e_{k}(u), which is the number of vertices which are at distance greater than k from u, that is e_{k}(u) := |V \ N_{k}(u)|. Then, trivially, e_{0}(u) = n − 1 and e_{D}(u) = e_{ε(u)}(u) = 0. Furthermore, note that e_{k}(u) = 0 if and only if the eccentricity of u satisfies ε(u) ≤ k. The name “excess” is borrowed from Biggs [3], where he gave a lower bound, in terms of the eigenvalues of Γ, for the excess e_{r}(u) of (any) vertex u in a regular graph with girth g = 2r + 1 (r is sometimes called the injectivity radius of Γ, see [36].)

All the involved matrices and vectors are indexed by the vertices of Γ. Moreover, for any vertex u ∈ V, e_{u} will denote the u-th unitary vector of the canonical base of ℝ^{n}. Besides, we consider A, the adjacency matrix of Γ, as an endomorphism of ℝ^{n}. A polynomial in the vector space of real polynomials with degree at most k, p ∈ ℝ_{k}[x], will operate on ℝ^{n} by the rule pw := p(A)w, where w ∈ ℝ^{n}, and the matrix is not specified unless some confusion may arise. The adjacency (or Bose-Mesner) algebra of A, denoted by A(A), is the algebra of all the matrices which are polynomials in A. 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

S(Γ) := {λ_{0}, λ_{1}^{m_{1}}, …, λ_{d}^{m_{d}}}

where the supraindexes denote multiplicities. Because of its special role, the largest (positive and with multiplicity one) eigenvalue λ_{0} will be also denoted by λ. We will make ample use of the positive eigenvector associated to such an eigenvalue, which is denoted by ν = (ν_{1}, ν_{2}, …, ν_{n})^{⊤}, and is normalized to have smallest entry 1. Thus, ν = j when Γ is regular. We will denote by M the mesh constituted by all the distinct eigenvalues, that is M := {λ > λ_{1} > ⋯ > λ_{d}}. It is well-known that the diameter of Γ satisfies D ≤ d = |M|−1 (see, for instance, Biggs [4].) We consider the mapping ρ : P(V) → ℝ^{n} defined by ρU := ∑_{u∈U} ν_{u}e_{u} for any vertex subset U ≠ ∅, and ρ∅ := 0. This corresponds to assigning some weights to the vertices of Γ, in such a way that it becomes “regularized” since the weight degree of each vertex u turns out to be a constant:

δ_{ρ}(u) := \frac{1}{ν_{u}} ∑_{v∈Γ(u)} ν_{v} = λ.

This approach has already been used by Garriga, Yebra, and the author to derive bounds of some parameters of a graph from its spectrum —such as the diameter [19, 22], the k-excess [17], and the independence and chromatic numbers [15]— and also to study a new distance-regularity concept for non-regular graphs [20, 18]. In this context the author introduced in [15] the notion of “weight parameter” of a graph, defined as follows. For each parameter of a graph Γ, say ξ, defined as the maximum [minimum] cardinality of a set U ⊂ V satisfying a given property P, we can define the corresponding weight parameter, denoted by ξ^{⋆}, as the maximum [minimum] value of ∥ρU∥^{2} of a vertex set U satisfying P. Note that, when the graph is regular, the parameters ξ^{⋆} and ξ are the same. Otherwise, when we are dealing with non-regular graphs, the weight parameters are sometimes more convenient to work with, as it was shown in the above-mentioned papers. For instance, we will here consider the weight k-excess of a vertex u:

e_{k}^{⋆}(u) := ∥ρ(V \ N_{k}(u))∥^{2} = ∥ν∥^{2} − ∥ρN_{k}(u)∥^{2},

and we also use the notion of pseudo-distance-regularity, which is defined as follows.

Given a vertex u ∈ V of a graph Γ, with eccentricity ε(u) = ε, consider the partition V = V_{0} ∪ V_{1} ∪ ⋯ ∪ V_{ε} where V_{k} := Γ_{k}(u), 0 ≤ k ≤ ε. Then, we say that Γ is pseudo-distance-regular around vertex u whenever the numbers

c_{k}(v) := \frac{1}{ν_{v}} ∑_{w∈Γ(v)∩V_{k−1}} ν_{w}, a_{k}(v) := \frac{1}{ν_{v}} ∑_{w∈Γ(v)∩V_{k}} ν_{w}, b_{k}(v) := \frac{1}{ν_{v}} ∑_{w∈Γ(v)∩V_{k+1}} ν_{w},

defined for any v ∈ V_{k} and 0 ≤ k ≤ ε (where, by convention, c_{0}(u) = 0 and b_{ε}(v) = 0 for any v ∈ V_{ε}) do not depend on the considered vertex v ∈ V_{k}, but only on the value of k. In such a case, we denote them by c_{k}, a_{k} and b_{k} respectively. Then, the matrix

I(u) := ( \begin{matrix}0 & c_{1} & ⋯ & c_{ε−1} & c_{ε} \\ a_{0} & a_{1} & ⋯ & a_{ε−1} & a_{ε} \\ b_{0} & b_{1} & ⋯ & b_{ε−1} & 0 \end{matrix} )

is called the (pseudo-)intersection array around vertex u of Γ. It is shown in [21] that this is a generalization of the concept of distance-regularity around a vertex (which in turn is a generalization of distance-regularity) that can be found, for instance, in [5]. For example, the graph Γ = P_{3} × P_{3}, where P_{3} denotes the path graph on three vertices \{u_{1}, u_{2}, u_{3}\} and positive eigenvector (ν_{u_{1}}, ν_{u_{2}}, ν_{u_{2}})^{⊤} = (1, \sqrt{2}, 1)^{⊤}, has positive eigenvector ν with entries ν_{(u_{i},u_{j})} = ν_{u_{i}}ν_{u_{j}}, i, j ∈ {1, 2, 3}. Using this, it can be easily checked that Γ pseudo-distance-regular around the “central” vertex (u_{2}, u_{2}), and also around every “corner” vertex (u_{i}, u_{j}), i, j ∈ {1, 3}, i ≠ j (the intersection arrays around a central vertex and a corner vertex being different.) For instance, the intersection array around u = (u_{2}, u_{2}) is:

I(u) := ( \begin{matrix}0 & \sqrt{2} & 2\sqrt{2} \\ 0 & 0 & 0 \\ 2\sqrt{2} & \sqrt{2} & 0 \end{matrix} ) .

Finally, recall that a (symmetric) association scheme with d classes can be defined as a set of d graphs Γ_{i} = (V, E_{i}), 1 ≤ i ≤ d, on the same vertex set V, with adjacency matrices A_{i} satisfying ∑_{k=0}^{d} A_{k} = J, with A_{0} := I; and A_{i}A_{j} = ∑_{k=0}^{d} p_{ij}^{k}A_{k}, for some integers p_{ij}^{k}, 0 ≤ i, j, k ≤ d. Then, following Godsil [24], we say that the graph Γ_{i} is the i-th class of the scheme, and so we indistinctly use the words “graph” or “class” to mean the same thing.

2 The Proper and Adjacency Polynomials

In this section we introduce two orthogonal systems of polynomials and, after recalling their main properties, we study some of their (old and new) applications. These polynomials are constructed from a discrete scalar product whose points are eigenvalues of the graph and the corresponding weights a sort of (local) multiplicities which we introduce next.

2.1 The local spectrum

For each eigenvalue λ_{i}, 0 ≤ i ≤ d, let U_{i} be the matrix whose columns form an orthonormal basis for the eigenspace corresponding to λ_{i}, Ker(A − λ_{i}I). The (principal) idempotents of A are the matrices E_{i} := U_{i}U_{i}^{⊤} representing the orthogonal projections onto Ker(A − λ_{i}I). Thus, in particular, E_{0} = \frac{1}{∥ν∥^{2}} νν^{⊤}. Therefore, such matrices satisfy the following properties (see Godsil [24]):

(a.1) E_{i}E_{j} = \{ \begin{matrix}E_{i} & if i = j \\ 0 & otherwise; \end{matrix}

(a.2) AE_{i} = λ_{i}E_{i};

(a.3) p(A) = ∑_{i=0}^{d} p(λ_{i})E_{i}, p ∈ ℝ[x].

Given a vertex u ∈ V and an eigenvalue λ_{i}, Garriga, Yebra, and the author [21] defined the (u-)local multiplicity of λ_{i} as

m_{u}(λ_{i}) := ∥E_{i}e_{u}∥^{2} = (E_{i})_{uu} (0 ≤ i ≤ d)

so that m_{u}(λ_{i}) ≥ 0 and, in particular, m_{u}(λ_{0}) = \frac{ν_{u}^{2}}{∥ν∥^{2}} . Moreover, they showed that, when the graph is seen from a vertex, its local multiplicities play a similar role as the standard multiplicities. Thus,

(b.1) ∑_{i=0}^{d} m_{u}(λ_{i}) = ∑_{i=0}^{d} ∥E_{i}e_{u}∥^{2} = ∥e_{u}∥^{2} = 1 (u ∈ V);

(b.2) ∑_{u∈V} m_{u}(λ_{i}) = tr E_{i} = m_{i} (0 ≤ i ≤ d);

(b.3) C_{k}(u) := (A^{k})_{uu} = ∑_{i=0}^{d} m_{u}(λ_{i})λ_{i}^{k},

where C_{k}(u) is the number of closed k-walks going through vertex u. If μ_{0}(= λ) > μ_{1} > ⋯ > μ_{d_{u}} represent the eigenvalues with non-null local multiplicities, we define the (u-)local spectrum as

S_{u}(Γ) := {λ^{m_{u}(λ)}, μ_{1}^{m_{u}(μ_{1})}, …, μ_{d_{u}}^{m_{u}(μ_{du})}}.

Moreover, we introduce the (u-)local mesh as the set M_{u} := {λ > μ_{1} > ⋯ > μ_{d_{u}}}. Then it can be proved that the eccentricity of u satisfies ε(u) ≤ d_{u} = |M_{u}| − 1 (see [21].)

From the u-local spectrum we introduce in ℝ_{d_{u}}[x] the (u-)local scalar product

⟨f, g⟩_{u} := ∑_{i=0}^{d_{u}} m_{u}(μ_{i})f(μ_{i})g(μ_{i})  (1)

whose relation with the (standard) Euclidean product ⟨· , ·⟩ is

⟨fe_{u}, ge_{u}⟩ = (f(A)g(A))_{uu} = (∑_{i=0}^{d} f(λ_{i})E_{i} ∑_{j=0}^{d} g(λ_{j})E_{j})_{uu}

= ∑_{i=0}^{d} f(λ_{i})g(λ_{i})(E_{i})_{uu} = ⟨f, g⟩_{u}

where we have used properties (a.3) and (a.1). In particular, the relation between the corresponding norms is ∥fe_{u}∥ = ∥f∥_{u}. Moreover, note that, according to property (b.1), the weight function ρ_{i} := m_{u}(μ_{i}), 0 ≤ i ≤ d, of the scalar product (1) is normalized in such a way that ∑_{i=0}^{d} ρ_{i} = 1.

2.2 The proper polynomials

Let us consider an orthonormal system of polynomials {g_{k} : dgr g_{k} = k, 0 ≤ k ≤ d_{u}} with respect to the above scalar product (1). From these polynomials, and taking into account that g_{k}(λ) ≠ 0 since the roots of g_{k} are within the interval (μ_{d_{u}}, μ_{0}), we can define another orthogonal secuence by p_{k}^{u} = g_{k}(λ)g_{k}, 0 ≤ k ≤ d_{u}, which clearly satisfy the following orthogonal property

⟨p_{k}^{u}, p_{l}^{u}⟩_{u} = δ_{kl}p_{k}^{u}(λ) (0 ≤ k, l ≤ d_{u}),  (2)

so that ∥p_{k}^{u}∥_{u}^{2} = p_{k}^{u}(λ). Such a sequence, which uniqueness can be easily proved by using induction, will be called the (u-)local proper orthogonal system, and its members the (u-)local proper polynomials. As elements of an orthogonal system, such polynomials satisfy a three-term recurrence of the form

xp_{k}^{u} = b_{k−1}p_{k−1}^{u} + a_{k}p_{k}^{u} + c_{k+1}p_{k+1}^{u} (0 ≤ k ≤ d),  (3)

where a_{k}, b_{k} and c_{k} are the corresponding Fourier coeficients of xp_{k}^{u} in terms of p_{k−1}^{u}, p_{k}^{u}, and p_{k+1}^{u} respectively (b_{−1} = c_{d+1} = 0), initiated with p_{−1}^{u} = 0 and p_{0}^{u} = 1. (See, for instance, [34].) Notice that the value of p_{0}^{u} is a consequence of the fact that the weight function is normalized, since then ∥p_{0}^{u}∥^{2} = ∑_{i=0}^{d} ρ_{i} = 1 = p_{0}^{u}(λ).

Using the above property of the weight function, Garriga and the author [17, 18, 23] proved the following result giving some alternative characterizations of these polynomials.

Lemma 2.1 Given any vertex u of a graph Γ, there exists a unique orthogonal system p_{0}^{u}(= 1), p_{1}^{u}, …, p_{d_{u}}^{u}, characterized by any of the following conditions:

(a) ∥p_{k}^{u}∥_{u}^{2} = p_{k}^{u}(λ);

(b) a_{k} + b_{k} + c_{k} = λ (0 ≤ k ≤ d_{u});

(c) ∑_{k=0}^{d_{u}} p_{k}^{u} = \frac{∥ν∥^{2}}{ν_{u}^{2}π_{0}} ∏_{k=0}^{d_{u}}(x − μ_{k}), where π_{0} = ∏_{k=0}^{d_{u}}(λ − μ_{k}). □

In the same papers it was shown that the highest degree polynomial p_{d_{u}}^{u} satisfies the following properties:

(c.1) The u-local multiplicities of Γ are given by

m_{u}(μ_{i}) = \frac{ν_{u}^{2}ϕ_{0}p_{d_{u}}^{u}(λ)}{∥ν∥^{2}ϕ_{i}p_{d_{u}}^{u}(μ_{i})} (0 ≤ i ≤ d_{u})  (4)
where ϕ_{i} = ∏_{j=0(j≠i)}^{d_{u}}(μ_{i} − μ_{j});

(c.2) The value at λ of the highest degree polynomial is

p_{d_{u}}^{u}(λ) = \frac{\frac{1}{m_{u}^{2}(λ)π_{0}^{2}}}{∑{d_{u} \atop i=0} \frac{1}{m_{u}(μ_{i})π_{i}^{2}}}  (5)
where π_{i} = (−1)^{i}ϕ_{i} = |ϕ_{i}|.

Example 2.2 Let Γ = P_{3}×P_{3}, the cartesian product of two 3-path graphs with vertex sets {u_{1}, u_{2}, u_{3}}, considered in the Introduction. Then the spectrum of Γ is S(Γ) = \{2\sqrt{2}^{1}, \sqrt{2}^{2}, 0^{3}, −\sqrt{2}^{2}, −2\sqrt{2}^{1}\}, whereas the local spectrum of the central vertex u = (u_{2}, u_{2}) is S_{u}(Γ) = \{2\sqrt{2}^{\frac{1}{4}} , 0^{\frac{1}{2}} , −2\sqrt{2}^{\frac{1}{4}} \}. From this, one can compute the u-local proper polynomials and their values at λ = 2\sqrt{2}, giving:

• p_{0}^{u} = 1, 1;

• p_{1}^{u} = \frac{1}{\sqrt{2}}x, 2;

• p_{2}^{u} = \frac{1}{4}x^{2} − 1, 1;

Example 2.3 Let Γ = LP, the line graph of the Petersen graph, with spectrum S(Γ) = {4^{1}, 2^{5}, −1^{4}, −2^{5}}. Then every vertex u of Γ has local spectrum S_{u}(Γ) = \{4^{\frac{1}{15}} , 2^{\frac{1}{3}} , −1^{\frac{4}{15}} , −2^{\frac{1}{3}} \}. Hence, the u-local proper polynomials and their values at λ = 4 turn out to be:

• p_{0}^{u} = 1, 1;

• p_{1}^{u} = x, 4;

• p_{2}^{u} = x^{2} − x − 4, 8;

• p_{3}^{u} = \frac{1}{4}(x^{3} − 3x^{2} − 4x + 8), 2;

The reader who is familiar with the theory of distance-regular graphs probably has already realized that the proper polynomials can be thought of as a generalization of the so-called “distance polynomials.” Thus, in the second example, the derived polynomials satisfy

p_{k}^{u}(A) = A_{k} (0 ≤ k ≤ d_{u})

where A_{k} stands for the adjacency matrix of Γ_{k}, usually called the k-th distance matrix of Γ. In other words, for each k = 0, 1, …, d_{u}, the polynomial p_{k}^{u} is the kdistance polynomial of Γ and, consequently, Γ is distance-regular (see, for instance, [5].) In fact, generalizing this result, Garriga, Yebra, and the author [21] showed that a graph Γ is pseudo-distance-regular around a vertex u, with eccentricity ε(u) = ε, if and only if there exist the (u-)local distance polynomials p_{k}^{u}, dgr p_{k}^{u} = k, satisfying

p_{k}^{u}e_{u} = \frac{1}{ν_{u}} ρV_{k} , p_{k}^{u}(λ) = \frac{1}{ν_{u}^{2}} ∥ρV_{k}∥^{2} (0 ≤ k ≤ ε)  (6)

(the latter equality being a consequence of the former) where V_{k} = Γ_{k}(u); and that, as suggested by the notation, such polynomials coincide, in fact, with the proper polynomials.

In addition, using property (c.2) and the adjacency polynomials defined bellow, Garriga and the author [17] gave the following numeric characterization of pseudodistance-regularity. (A similar characterization for “completely regular” codes [33] can be found in [18].)

Theorem 2.4 [17] A graph Γ is pseudo-distance-regular around a vertex u, with local spectrum S_{u}(Γ) as above, if and only if

\frac{1}{ν_{u}^{2}} ∥ρV_{d_{u}}∥^{2} = p_{d_{u}}^{u}(λ) = \frac{\frac{1}{m_{u}^{2}(λ)π_{0}^{2}}}{∑{d_{u} \atop i=0} \frac{1}{m_{u}(μ_{i})π_{i}^{2}}}  (7)

where π_{i} = ∏_{j=0(j≠i)}^{d_{u}} |μ_{i} − μ_{j}|, 0 ≤ i ≤ d_{u}. □

As an example of application of the above result, let us consider again the graph Γ = P_{3} × P_{3} “seen” from the vertex u = (u_{2}, u_{2}) with ν_{u} = 2 (Example 2.2.) Then, V_{d_{u}} = V_{2} consists of the four corner vertices (u_{i}, u_{j}), i, j ∈ {1, 3}, i ≠ j, with ν_{(u_{i},u_{j})} = 1, giving \frac{1}{ν_{u}^{2}} ∥ρV_{2}∥^{2} = 1 = p_{2}^{u}(λ). Consequently, Γ is pseudo-distance regular around u, as claimed in the Introduction.

2.3 The adjacency polynomials

The consideration of the adjacency polynomials can be motivated with the following result given in the aforementioned paper.

Theorem 2.5 [17] Let u be a vertex of a graph Γ, with local mesh of eigenvalues M_{u} = {λ > μ_{1} > ⋯ > μ_{d_{u}}}. Let P be a polynomial of degree k, 0 ≤ k ≤ d_{u}, such that ∥P ∥_{u} ≤ 1. Then

P (λ) ≤ \frac{1}{ν_{u}} ∥ρN_{k}(u)∥,  (8)

and equality is attained if and only if

P e_{u} = \frac{1}{∥ρN_{k}(u)∥}ρN_{k}(u),  (9)

in which case ∥P ∥_{u} = 1. Moreover, if this is the case and k = d_{u} − 1, ε(u) = d_{u}, then Γ is pseudo-distance-regular around vertex u. □

This result leads, in a natural way, to the study of the polynomials which optimize the result in (8), so that they are the only possible candidates to satisfy (9). In other words, we are interested in finding the polynomial(s) P of degree ≤ k such that ∥P ∥_{u} ≤ 1 and P (λ) is maximum. The study of these polynomials, called the (u- )local adjacency polynomials and denoted by Q_{k}^{u}, 0 ≤ k ≤ d_{u}, was done in [17], and their basic properties are the following:

(d.1) There exists a unique local adjacency polynomial Q_{k}^{u}, with dgr Q_{k}^{u} = k, for any k = 0, 1, …, d_{u}, and ∥Q_{k}^{u}∥_{u} = 1;

(d.2) The local adjacency polynomials of degrees 0, 1, and d_{u}, and their values at λ, are the following:

• Q_{0}^{u} = 1; Q_{0}^{u}(λ) = ∥e_{u}∥ = 1;

• Q_{1}^{u} = _{\frac{1}{\sqrt{\frac{λ^{2}}{δ(u)} +1}}} (\sqrt{\frac{λ}{δ(u)}x + 1}); Q_{1}^{u}(λ) = \sqrt{\frac{λ^{2}}{δ(u)} + 1}

• Q_{d_{u}}^{u} = \frac{∥ν∥}{ν_{u}π_{0}} ∏_{i=1}^{d_{u}}(x − μ_{i}), where π_{0} = ∏_{i=1}^{d_{u}}(λ − μ_{i}); Q_{d_{u}}^{u}(λ) = \frac{1}{ν_{u}} ∥ν∥;

(d.3) In general, the local adjacency polynomials can be computed from the local proper orthogonal system {p_{k}^{u}} in the following way:

• Q_{k}^{u} = _{\frac{1}{\sqrt{q_{k}^{u}(λ)}}}q_{k}^{u} (0 ≤ k ≤ d_{u}), where q_{k}^{u} := ∑_{l=0}^{k} p_{l}^{u};

(d.4) 1 = Q_{0}^{u}(λ) < Q_{1}^{u}(λ) < ⋯ < Q_{d_{u}}^{u}(λ) = \frac{1}{ν_{u}} ∥ν∥;

(d.5) The local adjacency polynomials are orthogonal with respect to the scalar product

⟨f, g⟩_{u}^{⋆} := ∑_{i=1}^{d_{u}}(λ − μ_{i})m_{u}(μ_{i})f(μ_{i})g(μ_{i}) = λ⟨f, g⟩_{u} − ⟨xf, g⟩_{u}.

(d.6) The polynomial H_{u} := \frac{∥ν∥}{ν_{u}}Q_{d_{u}}^{u} satisfies

(H_{u}(A))_{uv} = (H_{u}(A))_{vu} = \frac{ν_{v}}{ν_{u}} (v ∈ V)

and, hence, it locally generalizes to nonregular graphs the Hoffman polynomial H of a regular graph [30] satisfying H(A) = J.

Then, using the adjacency polynomials, the basic inequality (8) reads ν_{u}Q_{k}^{u}(λ) ≤ ∥ρN_{k}(u)∥ or, in terms of both the weight k-excess e_{k}^{⋆}(u) = ∥ν∥^{2} −∥ρN_{k}(u)∥^{2} and the sum polynomials q_{k}^{u} (note that, by (d.3), Q_{k}^{u}(λ)^{2} = q_{k}^{u}(λ)),

e_{k}^{⋆}(u) ≤ E_{k} := ∥ν∥^{2} − ν_{u}^{2}q_{k}^{u}(λ)  (10)

where the bound E_{k}(≥ 0) could be called the spectral weight k-excess of vertex u. In the next subsection we show that a similar bound, computed by using only the (global) spectrum of the graph, also applies for some vertex. Moreover, since the k-excess e_{k}(u) is an integer, e_{k}(u) ≤ e_{k}^{⋆}(u), the inequality (10) gives the following corollary (see [16]).

Corollary 2.6 Let u be a vertex of a graph Γ, with eccentricity ε(u) and local adjacency polynomials Q_{k}^{u}, 0 ≤ k ≤ d_{u}. Then

Q_{k}^{u}(λ) > \frac{1}{ν_{u}} \sqrt{∥ν∥^{2} − 1} ⇒ ε(u) ≤ k.

The following simple example is also drawn from [16]:

Example 2.7 Let Γ be the graph obtained from K_{4} by deleting an edge. Then Γ has spectrum and positive eigenvector

S(Γ) = \{\frac{1}{2}(1 + \sqrt{17}), 0, −1, \frac{1}{2}(1 − \sqrt{17})\}, ν = (1, \frac{1}{2}(1 + \sqrt{17}), 1, \frac{1}{2}(1 + \sqrt{17}))^{⊤},

respectively (the 1 entries of ν correspond to the vertices of degree 2). Then, ∥ν∥^{2} = \frac{17+\sqrt{17}}{4} and, if u is a vertex of degree 3 we get, from (b.2),

Q_{1}^{u} = \frac{(\sqrt{17} + 1)x + 12}{\sqrt{198 + 6\sqrt{17}}}

giving Q_{1}^{u}(λ) = 1.6833 … Therefore, since \frac{1}{ν_{u}} \sqrt{∥ν∥^{2} − 1} = 1.6154 …, Corollary 2.6 gives e(u) = 1.

2.4 The regular case

Let Γ = (V, E) be a graph with n vertices and m edges. Then we say that Γ is (u-)locally regular if vertex u has degree δ(u) = \frac{2m}{n}. Thus, Γ is regular iff it is ulocally regular for every u ∈ V. Similarly, we say that a graph Γ with spectrum S(Γ) = {λ_{0}, λ_{1}^{m_{1}}, …, λ_{d}^{m_{d}}} is (u-)locally spectrum-regular when the u-local multiplicities of each eigenvalue satisfy

m_{u}(λ_{i}) = \frac{m_{i}}{n}  (0 ≤ i ≤ d).  (11)

(Thus, d_{u} = d.) Note that, from property (b.3) with k = 2, if Γ is u-locally spectrumregular then Γ is also u-locally regular. Associated to the values in (11) we can now consider what we call the average scalar product:

⟨f, g⟩_{Γ} := ∑_{i=0}^{d} \frac{m_{i}}{n} f(λ_{i})g(λ_{i}),  (12)

since it is the average over V of the local scalar products ⟨f, g⟩_{u}:

\frac{1}{n} ∑_{u∈V}⟨f, g⟩_{u} = \frac{1}{n} ∑_{u∈V} ∑_{i=0}^{d} m_{u}(λ_{i})f(μ_{i})g(μ_{i})

= ∑_{i=0}^{d} f(μ_{i})g(μ_{i})\frac{1}{n} ∑_{u∈V} m_{u}(λ_{i}) = ⟨f, g⟩_{Γ}  (13)

where we have used property (b.2). Therefore, since ⟨f, g⟩_{u} = (f(A)g(A))_{uu}, an alternative definition of this scalar product would be ⟨f, g⟩_{Γ} = \frac{1}{n} tr(f(A)g(A)).

Since the weight function of such a scalar product is also normalized, ∑_{i=0}^{d} \frac{m_{i}}{n} = 1, we can also consider its corresponding proper and adjacency polynomials, denoted by p_{k} and Q_{k}, 0 ≤ k ≤ d, respectively, which will be called the average (proper and adjacency) polynomials. Using them we can now give the following new result.

Theorem 2.8 Let Γ = (V, E) be a graph on n vertices, with spectrum S(Γ) = {λ, λ_{1}^{m_{1}}, …, λ_{d}^{m_{d}}}. Then, for each given k, 0 ≤ k ≤ d, there exists a vertex u ∈ V such that the average adjacency polynomial of Γ satisfies ∥Q_{k}∥_{u} ≤ 1 and

∥ρN_{k}(u)∥ ≥ ν_{u}Q_{k}(λ).  (14)

If equality is attained, then Q_{k} = Q_{k}^{u} and

ρN_{k}(u) = ∥ρN_{k}(u)∥Q_{k}e_{u}.  (15)

Moreover, if k = d−1 and ε(u) = d, then Γ is u-locally spectrum-regular and pseudodistance-regular around u.

P roof. We know that the average adjacency polynomial satisfies ∥Q_{k}∥_{Γ} = 1. Then, from (13) with f = g = Q_{k},

∑_{u∈V} ∥Q_{k}∥_{u}^{2} = n∥Q_{k}∥_{Γ}^{2} = n.

Hence, there must be some vertex, say u, for which ∥Q_{k}∥_{u} ≤ 1, and Theorem 2.5 gives the lower bound (14) for ∥ρN_{k}(u)∥. If such a bound is attained, then, by the same theorem and property (d.1), the polynomial Q_{k} must coincide with the u-local adjacency polynomial Q_{k} = Q_{k}^{u}, ∥Q_{k}∥_{u} = 1, and (15) holds. Furthermore, if k = d − 1 = ε(u) − 1, we must have d_{u} = d, since d = ε(u) ≤ d_{u} ≤ d, and hence property (d.3) gives Q_{d}^{u} = \frac{∥ν∥}{ν_{u}π_{0}} ∏_{i=1}^{d}(x − λ_{i}) = Q_{d}. Thus, applying property (d.2) we have, for k = d − 1, d,

q_{k}^{u} = \sqrt{Q_{k}^{u}(λ)}Q_{k}^{u} = \sqrt{Q_{k}(λ)}Q_{k} = q_{k},

and hence p_{d}^{u} = q_{d}^{u} − q_{d−1}^{u} = q_{d} − q_{d−1} = p_{d}. Consequently, we infer from (4) that the “weight functions” of both the local and average scalar products must coincide, m_{u}(λ_{i}) = \frac{m_{i}}{n}, 0 ≤ i ≤ d, and Γ is u-locally spectrum-regular. Finally, Theorem 2.5 assures that Γ is also pseudo-distance-regular around vertex u. □

Note that, in general, the vertex u depends on the value of k. Two straightforward consequences of the above theorem are the following.

Corollary 2.9 Let Γ be a graph as above. Then, for each given 0 ≤ k ≤ d, there exists a vertex u ∈ V with weight k-excess

e_{k}^{⋆}(u) ≤ ∥ν∥^{2} − ν_{u}^{2}Q_{k}^{2}(λ)

where Q_{k} is the average adjacency polynomial.

P roof. Use the definition of e_{k}^{⋆}(u) and (14). □

Corollary 2.10 Let Γ be a graph as above, with radius r(Γ) and average adjacency polynomial Q_{k}. Then,

Q_{k}^{2}(λ) > ∥ν∥^{2} − 1 ⇒ r(Γ) ≤ k.

P roof. Using the hypothesis and Corollary 2.9, we infer that there exist a vertex u such that such that e_{k}^{⋆}(u) ≤ ∥ν∥^{2} − ν_{u}^{2}Q_{k}^{2}(λ) ≤ ∥ν∥^{2} − Q_{k}^{2}(λ) < 1. Therefore, since e_{k}(u) ≤ e_{k}^{⋆}(u), we must have e_{k}(u) = 0 and hence r(Γ) ≤ ε(u) ≤ k. □

Note the similarity between the above result and Corollary 2.6.

3 Partially walk-regular graphs

Given an integer τ > 0, a graph Γ is said to be τ-partially walk-regular if the number C_{k}(u) = (A^{k})_{uu} of closed walks of length k, 0 ≤ k ≤ τ, through a vertex u ∈ V does not depend on u. For instance, every δ-regular graph with girth g is (g − 1)- partially walk-regular, since in this case, for any u ∈ V and 0 ≤ k ≤ g − 1, we have C_{k}(u) = Ψ(k), where Ψ(k) denote the number of closed walks of legth k which go through the root of a (internally) δ-regular tree of depth ≥ k/2 (hence, Ψ(k) = 0 if k is odd.) Notice that, since I, A, …, A^{d} is a basis for A(A), if Γ is τ-partially walkregular with τ ≥ d, then all the matrices in such a basis have constant diagonal, and hence Γ is τ-partially walk-regular for any integer τ. In this case Γ is simply called walk-regular, a concept introduced by Godsil and McKay [25]. These authors proved that walk-regular graphs are also characterized by the fact that all the subgraphs obtained by removing a vertex from Γ are cospectral, see also Godsil [24]. As it is easy to show, examples of walk-regular graphs are the vertex-transitive and/or distance-regular graphs.

Let Γ be a τ-partially walk-regular graph with τ < d, and adjacency matrix A. Consider two polynomials f, g such that dgr f +dgr g ≤ τ. Then, as (A^{l})_{uu} = ⟨x^{l}, 1⟩_{u}, 0 ≤ l ≤ τ, does not depend on u, neither does ⟨f, g⟩_{u} = (f(A)g(A))_{uu} and then

⟨f, g⟩_{u} = \frac{1}{n} tr(f(A)g(A)) = ⟨f, g⟩_{Γ}.

As a consequence, when k ≤ ⌊\frac{τ}{2}⌋, the local proper and adjacency polynomials, p_{k}^{u} and Q_{k}^{u}, are independent of the chosen vertex u and coincide with the corresponding average polynomials p_{k} and Q_{k}, respectively (in this case we simply speak about the “proper and adjacency polynomials.”) On the other hand, if τ ≥ d, then Γ is walk-regular, and the above conclusion applies for any 0 ≤ k ≤ d.

3.1 Spectrum-regular graphs

Walk-regular graphs have also shown to be equivalent to spectrum-regular graphs. See, for instance, Delorme and Tillich [14] or Garriga and the author [16]. A graph Γ = (V, E), with spectrum S(Γ) = {λ, λ_{1}^{m_{1}}, …, λ_{d}^{m_{d}}}, is called spectrum-regular when it is u-locally spectrum-regular for every u ∈ V. Then all its vertices have the same local spectrum and, in particular, d_{u} = d, for any u ∈ V. Also, ν = j and the graph must be regular.

From the above comments, notice that a graph with girth g and d ≤ g −1 is walkregular and hence spectrum-regular. In fact, if the graph is regular we can slightly relax the condition, as the following result shows.

Lemma 3.1 A δ-regular graph Γ with d distinct eigenvalues and girth g ≥ d is spectrum-regular.

P roof. From the above, Γ is τ-partially walk-regular with τ = g − 1 ≥ d − 1. Moreover, as J = H(A), where H = \frac{n}{π_{0}} ∏_{i=1}^{d}(x − λ_{i}) = q_{d} is the Hoffman polynomial [30], we have that I, A, …, A^{d−1}, J is also a basis for A(A) and therefore Γ is walkregular. Consequently, Γ is spectrum-regular and the proof is complete.

Alternatively, we can consider the linear system

∑_{i=0}^{d} m_{u}(λ_{i})λ_{i}^{k} = Ψ(k) (0 ≤ k ≤ d − 1)

with m_{u}(λ_{0}) = \frac{1}{n} and unknowns m_{u}(λ_{i}), 1 ≤ i ≤ d, which has a unique solution (independent of u ∈ V.) □

In particular, since g ≥ 3 always holds, we have that any regular graph with four distinct eigenvalues is spectrum-regular, a result already used by Van Dam in [10].

Generalizing some results of Haemers and Van Dam [29, 12] (for d = 3), and Garriga, Yebra, and the author [20] (for |Γ_{d}(u)| = 1), Garriga and the author [17] showed that the following numeric condition is sufficient to assure spectrum-regularity and, in fact, constitutes a characterization of distance-regularity (to be compared with the result of Theorem 2.4.)

Theorem 3.2 [17] Let Γ = (V, E) be a regular graph on n vertices, with spectrum S(Γ) = {λ, λ_{1}^{m_{1}}, …, λ_{d}^{m_{d}}} and average proper polynomials p_{0}, p_{1}, …, p_{d}. Then Γ is distanceregular if and only if the number of vertices at distance d from every vertex u ∈ V is

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

where π_{i} = ∏_{j=0(j≠i)}^{d} |λ_{i} − λ_{j}|. □

3.2 Bounds

The particularization of Theorem 2.8 and its corollaries to partially walk-regular (or, in particular, spectrum-regular) graphs gives the following result.

Theorem 3.3 Let Γ = (V, E) be a τ-partially walk-regular graph on n vertices, with spectrum S(Γ) = {λ, λ_{1}^{m_{1}}, …, λ_{d}^{m_{d}}}. Let Q_{k} be the adjacency polynomial of Γ (with k ≤ ⌊\frac{τ}{2}⌋ if τ < d.) Then,

(a) |N_{k}(u)| ≥ Q_{k}^{2}(λ); e_{k}(u) ≤ n − Q_{k}^{2}(λ), for every u ∈ V;

(b) |Γ_{d}(u)| = e_{d−1}(u) ≤ n − Q_{d−1}^{2}(λ) = \frac{n}{π_{0}^{2} ∑_{i=0}^{d} \frac{1}{m_{i}π_{i}^{2}}} , for every u ∈ V (τ ≥ d);

(c) Q_{k}^{2}(λ) > n − 1 ⇒ D(Γ) ≤ k. □

When Γ is spectrum-regular, the above statements were already given in [16, 17]. Moreover, when d = 3 Theorem 3.3(b) proves a conjecture of Haemers [29] (see also [12]) about the number of vertices at distance two from every vertex of a regular graph with four distinct eigenvalues.

Corollary 3.4 Let Γ = (V, E) be a δ-regular graph with four distinct eigenvalues, S(Γ) = {λ, λ_{1}^{m_{1}}, λ_{2}^{m_{2}}, λ_{3}^{m_{3}}}. Then, the number of vertices at distance two from every vertex u ∈ V is lower-bounded by

|Γ_{2}(u)| ≥ n − 1 − δ − \frac{n}{π_{0}^{2} ∑_{i=0}^{3} \frac{1}{m_{i}π_{i}^{2}}}

where π_{i} = ∏_{j=0(j≠i)}^{3} |λ_{i} − λ_{j}|.

P roof. For every vertex u ∈ V we have |Γ_{2}(u)| = n − 1 − δ − |Γ_{3}(u)|. Hence, since Γ is spectrum-regular by Lemma 3.1, the result follows from Theorem 3.3(b).

3.3 Partially distance-regular graphs

An example of partially walk-regular graphs are those graphs bearing a ‘partial distance-regularity’ around every one of their vertices, studied in [35]. More precisely, a graph Γ, with adjacency matrix A and d + 1 distinct eigenvalues, is said to be (d′-)partially distance-regular if, for any 0 ≤ k ≤ d′, there exist a polynomial p_{k} of degree k such that p_{k}(A) = A_{k}, the k-th distance matrix of Γ. In fact, any d′- partially distance-regular graph is also (2d′)-partially walk-regular and, as expected, the above polynomials p_{k} are again the proper polynomials, see [16].

By way of example, note that a graph is 1-partially distance-regular iff it is regular. At the other extreme, a (d − 1)-partially distance-regular graph is also d-partially distance-regular (since A_{d} = J − ∑_{k=0}^{d−1} A_{k} = (H − q_{d−1})(A),) which is the same as distance-regular. When Γ is a regular graph with girth g, simple reasoning shows that it is d′-partially distance-regular graph with d′ ≥ ⌊\frac{g−1}{2}⌋, see Biggs [3, 4]. In the case of odd g, say g = 2r + 1, Biggs [3] proved that the r-excess of any vertex u satisfies

e_{r}(u) ≥ ∥q_{r}∥_{∞}  (17)

where q_{r} = ∑_{k=0}^{r} p_{k} and ∥q_{r}∥_{∞} := max_{1≤i≤d}{|q_{r}(λ_{i})|}. In fact, the same reasoning used in that paper proves that (17) also applies for an r-partially distance-regular graph. As a conclusion note that, from Theorem 3.3(a) and the above comments, the k-excess of any vertex of a k-partially distance-regular graph satisfies

∥q_{k}∥_{∞} ≤ e_{k}(u) ≤ n − q_{k}(λ).

As another consequence of Theorem 2.5, we can give the following characterization of d′-partially distance-regular graphs.

Theorem 3.5 Let Γ be a regular graph, with spectrum S(Γ) = {λ, λ_{1}^{m_{1}}, …, λ_{d}^{m_{d}}}, and average proper polynomials p_{k}, 0 ≤ k ≤ d, with leading coefficients a_{k}. Then Γ is d′-partially distance-regular if and only if, for any 2 ≤ k ≤ d′, the number of vertices at distance k from every vertex is n_{k} = p_{k}(λ).

P roof. We only prove sufficiency. From the hypothesis, the average adjacency polynomials Q_{k} = \frac{1}{\sqrt{q_{k}(λ)}}q_{k} (see property (d.2)) satisfy

Q_{k}(λ) = \sqrt{q_{k}(λ)} = \sqrt{|N_{k}(u)|} = ∥ρN_{k}(u)∥

for every u ∈ V and 0 ≤ k ≤ d′ (the cases k = 0, 1 are trivial.) Then, by the converse of Theorem 2.5, it must be ∥Q_{k}∥_{u} ≥ 1. On the other hand, in the proof of Theorem 2.8 we have seen that ∑_{u∈V} ∥Q_{k}∥_{u}^{2} = n. Consequently, we must have ∥Q_{k}∥_{u} = 1 and, using again Theorem 2.5, we infer that

Q_{k}e_{u} = \frac{1}{∥ρN_{k}(u)∥}ρN_{k}(u) = \frac{1}{\sqrt{|N_{k}(u)|}}ρN_{k}(u),

or p_{k}e_{u} = ρΓ_{k}(u) for every u ∈ V and 0 ≤ k ≤ d′. But this is equivalent to p_{k}(A) = A_{k}, for any 0 ≤ k ≤ d′, and Γ is d′-partially distance-regular. □

4 Bounding Special Vertex Sets

Let Γ = (V, E) be a regular graph with four distinct eigenvalues, so that Γ is spectrumregular and D(Γ) ≤ 3. Generalizing the work of Haemers and Van Dam [12] about distance-regular graphs with diameter three to 3-class association schemes, the latter author [10] studied some bounds for the number of non-adjacent vertices to a (generic) vertex u ∈ V, that have a fixed number μ of common neighbours with u. The best bound he gave generalized that conjectured by Haemers in [29] —since for μ = 0 such a number clearly is |Γ_{3}(u)|. Van Dam showed that such a bound applied when Γ satisfied some additional conditions, and conjectured that this was always the case. Moreover he showed that the bound was attained for every vertex if and only if Γ is the (connected) graph of a 3-class association scheme. Following these work, and using again the proper and adjacency polynomials, in this section we study bounds for the more general vertex subsets Γ_{k}^{μ}(u), defined below. Also, the “extremal cases” are characterized. When the results are particularized to spectrum-regular graphs, a proof of Van Dam’s conjecture is obtained.

Let u ∈ V be a vertex with eccentricity ε(u) = ε. Given the integers k, μ such that 0 ≤ k ≤ ε and μ ≥ 0, let Γ_{k}^{μ}(u) denote the set of vertices which are at distance at least k from u ∈ V and there exist exactly μ (shortest) k-paths from u to each of such vertices. Note that Γ_{k}^{0}(u) = V \ N_{k}(u), and if μ ≠ 0, then Γ_{k}^{μ}(u) contains only vertices at distance k from u, so that we get the partition Γ_{k}(u) = ∪_{μ≥1}Γ_{k}^{μ}(u). The next theorem gives an upper bound for ∥ρΓ_{k}^{μ}(u)∥^{2}, and hence also for the cardinality of Γ_{k}^{μ}(u).

Theorem 4.1 Let u be a vertex of a graph Γ, with eccentricity ε(u) = ε, and local mesh of eigenvalues M_{u} = {λ > μ_{1} > ⋯ > μ_{d_{u}}}. Let P be a polynomial of degree k < d_{u} with leading coefficient c_{k} such that ν_{u}P (λ) = 1 + ∥ν∥^{2}c_{k}μ. Then, for any given integer μ > 0,

∥ρΓ_{k}^{μ}(u)∥^{2} ≤ \frac{∥ν∥^{2} (∥ν∥^{2}∥P ∥_{u}^{2} − ν_{u}^{2}P^{2}(λ))}{1 + ∥ν∥^{2}∥P ∥_{u}^{2} − ν_{u}^{2}P^{2}(λ)} ,  (18)

where the equality is attained if and only if n_{k}^{μ} := |Γ_{k}^{μ}(u)| = ∥ρΓ_{k}^{μ}(u)∥^{2} and either

(a) when k = ε:

P e_{u} = \frac{ν_{u}P (λ)(∥ν∥^{2} − n_{ε}^{μ}) + n_{ε}^{μ}}{∥ν∥^{2}(∥ν∥^{2} − n_{ε}^{μ})} ν − \frac{1}{∥ν∥^{2} − n_{ε}^{μ}} ρΓ_{ε}^{μ}(u) ;  (19)

(b) when k < ε:

P e_{u} = −\frac{1}{∥ν∥^{2} − n_{k}} ρV_{k} ,  (20)

where V_{k} = Γ_{k}(u) = Γ_{k}^{μ}(u) and

n_{k} := |V_{k}| = \frac{∥ν∥^{2}ν_{u}P (λ)}{ν_{u}P (λ) − 1} ,  (21)

in which case

\frac{∥P ∥_{u}^{2}}{P (λ)} = ν_{u}c_{k}μ.  (22)

P roof. First, let P be any polynomial with degree k < d_{u} and assume μ ≥ 0 (μ > 0 if k = ε.) Let U := Γ_{k}^{μ}(u). From the following spectral decompositions of ρu = ν_{u}e_{u} and ρU = ∑_{v∈U} ν_{v}e_{v}:

ρu = \frac{ν_{u}^{2}}{∥ν∥^{2}} ν + z, ρU = \frac{∥ρU∥^{2}}{∥ν∥^{2}} ν + z′

where z, z′ ∈ ν^{⊥}, we obtain P ρu = \frac{ν_{u}^{2}P (λ)}{∥ν∥^{2}}ν + P z and so

∥P z∥^{2} = ∥P ρu∥^{2} − \frac{ν_{u}^{4}P^{2}(λ)}{∥ν∥^{2}} = ν_{u}^{2} (∥P ∥_{u}^{2} − \frac{ν_{u}^{2}P^{2}(λ)}{∥ν∥^{2}});  (23)
∥z′∥^{2} = ∥ρU∥^{2} (1 − \frac{∥ρU∥^{2}}{∥ν∥^{2}} ) .  (24)

Hence,

c_{k}μν_{u}∥ρU∥^{2} ≥ c_{k}μν_{u} ∑_{v∈U} ν_{v} = ⟨P ρu, ρU⟩ = ⟨\frac{ν_{u}^{2}P (λ)}{∥ν∥^{2}}ν + P z, \frac{∥ρU∥^{2}}{∥ν∥^{2}} ν + z′⟩
= \frac{ν_{u}^{2}∥ρU∥^{2}}{∥ν∥^{2}} P (λ) + ⟨P z, z′⟩ ≥ \frac{ν_{u}^{2}∥ρU∥^{2}}{∥ν∥^{2}} P (λ) − ∥P z∥∥z′∥

= \frac{ν_{u}^{2}∥ρU∥^{2}}{∥ν∥^{2}} P (λ) − ν_{u}∥ρU∥^{2}\sqrt{(∥P ∥_{u}^{2} − \frac{ν_{u}^{2}P^{2}(λ)}{∥ν∥^{2}}) (\frac{1}{∥ρU∥^{2}} − \frac{1}{∥ν∥^{2}} )}

Simplifying and rearranging the terms, we get

\frac{∥ν∥^{2}}{∥ρU∥^{2}} ≥ \frac{(ν_{u}P (λ) − ∥ν∥^{2}c_{k}μ)^{2}}{∥ν∥^{2}∥P ∥_{u}^{2} − ν_{u}^{2}P^{2}(λ)} + 1,  (25)

where

Φ := ∥ν∥^{2}∥P ∥_{u}^{2} − ν_{u}^{2}P^{2}(λ) = ∑_{i=1}^{d_{u}} m_{u}(μ_{i})P^{2}(μ_{i}) > 0

since m_{u}(λ) = \frac{ν_{u}^{2}}{∥ν∥^{2}} and dgr P < d_{u}. (Notice that \sqrt{Φ} can be seen as the norm of P, associated to an scalar product defined on the reduced local mesh M_{u}^{⋆} := {μ_{1} > ⋯ > μ_{d_{u}}}.) Then, solving for ∥ρU∥^{2} in (25), we obtain the inequality

∥ρΓ_{k}^{μ}(u)∥^{2} ≤ \frac{∥ν∥^{2}∥P ∥_{u}^{2} − ν_{u}^{2}P^{2}(λ)}{∥ν∥^{2}c_{k}^{2}μ^{2} − 2ν_{u}P (λ)c_{k}μ + ∥P ∥_{u}^{2}} .  (26)

which, in the case μ = 0 (k < ε), particularizes to

∥ρΓ_{k}^{0}(u)∥^{2} = ∥ν∥^{2} − ∥ρN_{k}(u)∥^{2} ≤ ∥ν∥^{2} − ν_{u}^{2} \frac{P^{2}(λ)}{∥P ∥_{u}^{2}},

so that

\frac{P (λ)}{∥P ∥_{u}} ≤ \frac{1}{ν_{u}} ∥ρN_{k}(u)∥

and, when ∥P ∥_{u} ≤ 1, we get the bound (8) of Theorem 2.5. Consequently, as stated in the hypotheses of the theorem, it suffices to study the case μ > 0. Furthermore, notice that the upper bound in (26) is invariant under multiplication of P by a constant, and when ν_{u}P (λ) = ∥ν∥^{2}c_{k}μ such a bound takes the trivial value ∥ν∥^{2}. Thus, assuming ν_{u}P (λ) − ∥ν∥^{2}c_{k}μ ≠ 0, we can choose, without loss of generality, the polynomial P in such a way that P (λ) = (1 + ∥ν∥^{2}c_{k}μ)/ν_{u}. In this case, (25) becomes

\frac{∥ν∥^{2}}{∥ρU∥^{2}} ≥ \frac{1}{∥ν∥^{2}∥P ∥_{u}^{2} − ν_{u}^{2}P^{2}(λ)} + 1,  (27)

whence (18) follows.

Moreover, if such a bound is attained, then all the inequalities in the above proof must be equalities, whence we get two main consequences. First, (recall that now μ ≠ 0) we have ∥ρU∥^{2} = ∑_{v∈U} ν_{v}^{2} = ∑_{v∈U} ν_{v}, so that ν_{v} = 1 for all v ∈ U, whence ∥ρU∥^{2} = |ρU|. Second, we must have cos{P z, z′} = −1, and therefore, using (23), (24), and the spectral decomposition of ρU, we can compute P z in the following manner:

P z = −\frac{∥P z∥}{∥z′∥}z′ = −\frac{ν_{u}\sqrt{∥P ∥_{u}^{2} − \frac{ν_{u}^{2}P^{2}(λ)}{∥ν∥^{2}}}}{\sqrt{|U| (1 − \frac{|U|}{∥ν∥^{2}} )}} (ρU − \frac{|U|}{∥ν∥^{2}} ν)

= \frac{−ν_{u}}{∥ν∥^{2} − |U|} (ρU − \frac{|U|}{∥ν∥^{2}} ν)

Using the above expression in the spectral decomposition of P ρu, we get

P ρu = \frac{ν_{u}^{2}P (λ)}{∥ν∥^{2}}ν + P z = \frac{ν_{u}^{2}P (λ)}{∥ν∥^{2}}ν − \frac{ν_{u}}{∥ν∥^{2} − |U|} (ρU − \frac{|U|}{∥ν∥^{2}} ν)

so that, denoting the multiplicative constants of ν and ρU by β_{k} and γ_{k}, respectively,

P e_{u} = β_{k}ν + γ_{k}ρU = \frac{ν_{u}P (λ)(∥ν∥^{2} − |U|) + |U|}{∥ν∥^{2}(∥ν∥^{2} − |U|)}ν − \frac{1}{∥ν∥^{2} − |U|}ρU. (28)

This gives (19) when k = ε (with n_{ε}^{μ} = |U|) which, using the value of ν_{u}P (λ), can also be written as

P e_{u} = β_{ε}ν + γ_{ε}ρΓ_{ε}^{μ}(u) = \frac{1 + c_{k}μ(∥ν∥^{2} − n_{ε}^{μ})}{∥ν∥^{2} − n_{ε}^{μ}}ν − \frac{1}{∥ν∥^{2} − n_{ε}^{μ}} ρΓ_{ε}^{μ}(u).  (29)

From this last expression, we get that if v ∈ Γ_{ε}^{μ}(u), then ν_{v} = (ρΓ_{ε}^{μ}(u))_{v} = 1 and (P e_{u})_{v} = β_{ε} − γ_{ε} = c_{k}μ (as it should be.) Otherwise, if v ∉ Γ_{ε}^{μ}(u), we have (ρΓ_{ε}^{μ}(u))_{v} = 0 and hence (P e_{u})_{v} = β_{ε}ν_{v}. In particular, if v ∈ Γ_{ε}(u) \ Γ_{ε}^{μ}(u), it must be (P e_{u})_{v} = c_{k}μ_{v}, where μ_{v} ≥ 0 is the number of ε-paths from u to v. Thus,

μ_{v} = \frac{β_{ε}}{c_{k}} ν_{v}  (30)

and such a number shows to be proportional to ν_{v}.

Let us now turn our attention to the case k < ε. Then, we clearly have (P (A))_{uv} = (P e_{u})_{v} = 0 for any vertex v such that ∂(u, v) ≥ k. Hence, we must have β_{k} = 0 in (28) and, therefore, P e_{u} = γ_{k}ρU. Furthermore, (P (A))_{uv} ≠ 0 for all v ∈ Γ_{k}(u) = V_{k}, and therefore U must be the whole set V_{k}, giving (20). The value of n_{k}^{μ} = n_{k}, given in (21), is obtained from the equation β_{k} = 0. Finally, condition (22) comes from equating such a value of n_{k} to the upper bound in (18). □

From the above proof, note that (18) also applies when dgr P = d_{u}, provided that P (μ_{i}) ≠ 0 for some 1 ≤ i ≤ d_{u} (so that Φ > 0.)

As in the case of Theorem 2.5, the above theorem suggests studying the polynomials which achieve the best bound in (18). Here, too, it turns out that the proper polynomials are of valuable help, as the next result shows.

Theorem 4.2 Let u be a vertex of a graph Γ, with local spectrum S_{u}(Γ) = {λ^{m_{u}(λ)}, μ_{1}^{m_{u}(μ_{1})}, …, μ_{d_{u}}^{m_{u}(μ_{du})}}, and positive eigenvector ν, and let p_{k}^{u}, 0 ≤ k ≤ d_{u}, be the local proper polynomials. Let a_{k} denote the leading coefficient of p_{k}^{u}, and consider the sum polynomials q_{k}^{u} = ∑_{l=0}^{k} p_{l}^{u}. For any given integers μ > 0 and 0 ≤ k < d_{u}, consider the spectral weight k-excess E_{k} = ∥ν∥^{2} −ν_{u}^{2}q_{k}^{u}(λ), and define σ_{k}(μ) := ν_{u}a_{k}μ−1. Then,

∥ρΓ_{k}^{μ}(u)∥^{2} ≤ \frac{p_{k}^{u}(λ)E_{k}}{p_{k}^{u}(λ)σ_{k}(μ)^{2} + a_{k}^{2}μ^{2}E_{k}} ,  (31)

and equality is attained if and only if ∥ρΓ_{k}^{μ}(u)∥^{2} = n_{k}^{μ}, and either

(a) when k = ε:

P^{∗}e_{u} = β_{ε}^{∗}ν + γ_{ε}^{∗}ρΓ_{ε}^{μ}(u),  (32)

with the polynomial

P^{∗} := a_{ε}μE_{ε}p_{ε}^{u} + p_{ε}^{u}(λ)σ_{ε}(μ)ν_{u}q_{ε}^{u}  (33)

and constants

β_{ε}^{∗} := p_{ε}^{u}(λ)σ_{ε}(μ), γ_{ε}^{∗} := p_{ε}^{u}(λ)σ_{ε}(μ)^{2} + a_{ε}^{2}μ^{2}E_{ε};  (34)

(b) when k < ε:

p_{k}^{u}e_{u} = \frac{1}{ν_{u}} ρV_{k} ,  (35)

in which case

n_{k}^{μ} = n_{k} = ν_{u}^{2}p_{k}^{u}(λ).  (36)

P roof. Let us consider a generic polynomial P = ∑_{l=0}^{k} α_{l}p_{l}^{u}, α_{l} ∈ ℝ. Since P must have leading coefficient c_{k} = α_{k}a_{k}, we impose the condition P (λ) = (1 + α_{k}a_{k}nμ)/ν_{u}, and hence

P = ∑_{l=1}^{k} α_{l}p_{l}^{u} + \frac{1 + α_{k}a_{k}nμ}{ν_{u}} − ∑_{l=1}^{k} α_{l}p_{l}^{u}(λ);  (37)

∥P ∥_{u}^{2} = ∑_{l=1}^{k} α_{l}^{2}p_{l}^{u}(λ) + (\frac{1 + α_{k}a_{k}nμ}{ν_{u}} − ∑_{l=1}^{k} α_{l}p_{l}^{u}(λ))^{2} .  (38)

Therefore, looking at (27), our aim is to minimize the function

Φ = Φ(α_{1}, … α_{k}) = ∥ν∥^{2}∥P ∥_{u}^{2} − ν_{u}^{2}P^{2}(λ) = ∥ν∥^{2}∥P ∥_{u}^{2} − (1 + ∥ν∥^{2}α_{k}a_{k}μ)^{2}

with ∥P ∥_{u}^{2} given by (38) (remember that Φ is the square of a norm on the mesh M_{u}^{⋆}.) Then, the minimum is attained when

α_{1} = α_{2} = ⋯ = α_{k−1} = \frac{ν_{u}p_{k}^{u}(λ)(1 − ν_{u}a_{k}μ)}{Δ} ,
α_{k} = \frac{ν_{u}p_{k}^{u}(λ) − a_{k}μ(∥ν∥^{2} − ν_{u}^{2}q_{k−1}^{u}(λ))}{Δ} ,

where

Δ = ν_{u}^{2}q_{k−1}^{u}(λ)(p_{k}^{u}(λ) − a_{k}^{2}μ^{2}∥ν∥^{2}) + (ν_{u}p_{k}^{u}(λ) − a_{k}μ∥ν∥^{2})^{2}

or, using q_{k−1}^{u}(λ) = q_{k}^{u}(λ) − p_{k}^{u}(λ) and the definitions of E_{k} and σ_{k}(μ),

α_{1} = α_{2} = ⋯ = α_{k−1} = −\frac{ν_{u}p_{k}^{u}(λ)σ_{k}(μ)}{Δ} ,
α_{k} = \frac{ν_{u}p_{k}^{u}(λ) − a_{k}μE_{k}}{Δ} ,

with

Δ = (∥ν∥^{2}a_{k}^{2}μ^{2} − p_{k}^{u}(λ))E_{k} + ∥ν∥^{2}p_{k}^{u}(λ)σ_{k}(μ)^{2}.

Then, such a minimum turns out to be

Φ_{min} = \frac{p_{k}^{u}(λ)E_{k}}{Δ}

and, according to (18), the upper bound in (31) comes from ∥ν∥^{2} \frac{Φ_{min}}{1+Φ_{min}} . This bound corresponds to using in (26) the polynomial (37) with the above values of the coefficients α_{l}, 1 ≤ l ≤ k. Namely,

P = −\frac{1}{Δ} (a_{k}μE_{k}p_{k}^{u} + ν_{u}p_{k}^{u}(λ)σ_{k}(μ)q_{k}^{u}) .  (39)

When the equality is attained, we can use the values of P (λ) and n_{k}^{μ} = |Γ_{k}^{μ}(u)| to compute the multiplicative constants of ν and ρΓ_{k}^{ε}(u) in (28), which turn out to be

β_{k} = −\frac{1}{Δ}p_{k}^{u}(λ)σ_{k}(μ) and γ_{k} = −\frac{1}{Δ} (p_{k}^{u}(λ)σ_{k}(μ)^{2} + a_{k}^{2}μ^{2}E_{k})

respectively, thus giving

P^{∗}e_{u} = β_{k}^{∗}ν + γ_{k}^{∗}ρΓ_{k}^{μ}(u)  (40)

with P^{∗} = −ΔP, β_{k}^{∗} = −Δβ_{k} and γ_{k}^{∗} = −Δγ_{k}. Now, from these facts we can reason as in Theorem 4.1 to obtain the claimed results for the cases k = ε and k < ε. Thus, in the former case, (40) becomes (32) and, if v ∈ Γ_{ε}(u) \ Γ_{ε}^{μ}(u), the number μ_{v} of ε-paths from u to v is obtained from

ν_{v}β_{ε}^{∗} = ν_{v}p_{ε}^{u}(λ)σ_{ε}(μ) = c_{ε}^{∗}μ_{v},  (41)

where c_{ε}^{∗} stands here for the leading coefficient of P^{∗}, that is

c_{ε}^{∗} = a_{ε} (a_{ε}μE_{ε} + ν_{u}p_{ε}^{u}(λ)σ_{ε}(μ)) .

Finally, in the case k < ε, the only real solution obtained when we solve Eq. (22) for μ turns out to be μ = \frac{1}{a_{k}ν}, and hence σ_{k}(μ) = 0. (More simply, the same conclusions are reached from the equation β_{k}^{∗} = 0.) Substituting these values into (40) and the bound in (31) we get (35) and (36), respectively, in concordance with (6). □

Notice that, as in the case of Theorem 4.1, the bound (31) also applies when μ = 0, giving ∥ρΓ_{k}^{0}(u)∥^{2} = e_{k}^{⋆}(u) ≤ E_{k}, in concordance with (10).

If Γ is regular, the above results take a more simple form since, from ν = j, we have ∥ν∥^{2} = n and ∥ρΓ_{k}^{μ}(u)∥^{2} = n_{k}^{μ}. Moreover, when the corresponding bound (31) is attained for k = ε, the value of μ_{v} in (41) becomes a constant, say μ′, for every vertex v ∈ Γ_{ε}(u) \ Γ_{ε}^{μ}(u). Namely,

μ′ = \frac{β_{ε}^{∗}}{c_{ε}^{∗}} = \frac{p_{ε}^{u}(λ)σ_{ε}(μ)}{a_{ε}p_{ε}^{u}(λ)σ_{ε}(μ) + a_{ε}^{2}μE_{ε}} .  (42)

Consequently, we get the partition Γ_{ε}(u) = Γ_{ε}^{μ}(u) ∪ Γ_{ε}^{μ′}(u). In this case, a more compact way of giving the above relation between μ and μ′ is

p_{ε}^{u}(λ)σ_{ε}(μ)σ_{ε}(μ′) = E_{ε}a_{ε}^{2}μμ′ ,

showing the symmetry between both parameters. Notice that, in particular, it might be μ′ = 0, in which case β_{ε}^{∗} = p_{ε}^{u}(λ)σ_{ε}(μ) = 0, and we would get the same consequences as in the case k < ε.

The two following corollaries are straightforward consequences of Theorem 4.2.

Corollary 4.3 Let u be a vertex of a graph Γ, with eccentricity ε(u) and local proper polynomials p_{k}^{u}. Then, for k < d_{u},

(a) ∥ρΓ_{k}(u)∥^{2} ≤ p_{k}^{u}(λ)E_{k} ∑_{μ≥1} \frac{1}{p_{k}^{u}(λ)σ_{k}(μ)^{2} + a_{k}^{2}μ^{2}E_{k}};

(b) min_{μ≥1}{p_{k}^{u}(λ)σ_{k}(μ)^{2} + a_{k}^{2}μ^{2}E_{k}} > p_{k}^{u}(λ)E_{k} ⇒ ε(u) < k.

P roof. (a) is a direct consequence of the theorem and ∥ρΓ_{k}(u)∥^{2} = ∑_{μ≥1} ∥ρΓ_{k}^{μ}(u)∥^{2}. To prove (b) notice that, from n_{k}^{μ} ≤ ∥Γ_{k}^{μ}(u)∥^{2} and the given condition, we get

n_{k}^{μ} ≤ ⌊\frac{p_{k}^{u}(λ)E_{k}}{p_{k}^{u}(λ)σ_{k}(μ)^{2} + a_{k}^{2}μ^{2}E_{k}} ⌋ < 1

for any μ ≥ 1. Thus, n_{k} = 0 and the result follows. □

Corollary 4.4 Let u be a vertex of a graph Γ, with eccentricity ε(u) = ε, and local proper polynomial p_{k}^{u} with degree k < ε and leading coefficient a_{k}. Then, (35) holds, that is p_{k}^{u}e_{u} = \frac{1}{ν_{u}} ρV_{k}, with ∥ρV_{k}∥^{2} = |V_{k}|, if and only if the quotient 1/ν_{u}a_{k} is an integer, say μ, and the number n_{k} = |V_{k}| of vertices at distance k from u is given by (36): n_{k} = n_{k}^{μ} = ν_{u}^{2}p_{k}^{u}(λ).

P roof. Assuming that (35) holds and ∥ρV_{k}∥^{2} = |V_{k}|, we have

ν_{u}p_{k}^{u}(λ) = ⟨e_{u}, p_{k}^{u}(λ)ν⟩ = ⟨p_{k}^{u}e_{u}, ν⟩ = \frac{1}{ν_{u}} ⟨ρV_{k}, ν⟩ = \frac{1}{ν_{u}} ∥ρV_{k}∥^{2} = \frac{n_{k}}{ν_{u}}

and, for any vertex v ∈ V_{k},

(A^{k})_{uv} = ⟨A_{k}e_{u}, e_{v}⟩ = \frac{1}{a_{k}} ⟨p_{k}^{u}e_{u}, e_{v}⟩ = \frac{1}{a_{k}ν_{u}} ⟨ρV_{k}, e_{v}⟩ = \frac{1}{a_{k}ν_{u}} .

Hence, n_{k} is given by (36), and 1/a_{k}ν_{u} is an integer. Conversely, if such is the case, then the upper bound in (31) for μ = 1/ν_{v}a_{k} becomes ν_{u}^{2}p_{k}^{u}(λ), and Theorem 4.2 (k < ε) applies. □

When the considered graph is partially walk-regular, and the equality is attained for all vertices, the results of Theorem 4.2 look much better, as it is shown next.

Theorem 4.5 Let Γ = (V, E) be a τ-partially walk-regular graph on n vertices, with adjacency matrix A and spectrum S(Γ) = {λ, λ_{1}^{m_{1}}, …, λ_{d}^{m_{d}}}. Let p_{k} be the proper polynomial with degree k ≤ ⌊\frac{τ}{2}⌋ if τ < d, or k ≤ d−1 otherwise, and leading coefficient a_{k}. Let q_{k} = ∑_{l=0}^{k} p_{l}, E_{k} = n − q_{k}(λ) and, for a given integer μ, let σ_{k}(μ) = a_{k}μ − 1, and denote by A_{k}^{μ} the adjacency matrix of Γ_{k}^{μ}. Then, for any u ∈ V,

n_{k}^{μ} ≤ \frac{p_{k}(λ)E_{k}}{p_{k}(λ)σ_{k}(μ)^{2} + a_{k}^{2}μ^{2}E_{k}} ,  (43)

and equality is attained for every vertex if and only if either

(a) when k = ε:

P^{∗}(A) = β_{ε}^{∗}J + γ_{ε}^{∗}A_{ε}^{μ},  (44)

with P^{∗} = a_{ε}μE_{ε}p_{ε} + p_{ε}(λ)σ_{ε}(μ)q_{ε}, β_{ε}^{∗} = p_{ε}(λ)σ_{ε}(μ), and γ_{ε}^{∗} = p_{ε}(λ)σ_{ε}(μ)^{2} + a_{ε}^{2}μ^{2}E_{ε}; in which case A_{ε} = A_{ε}^{μ} + A_{ε}^{μ′} with

μ′ = \frac{p_{ε}(λ)σ_{ε}(μ)}{a_{ε}p_{ε}(λ)σ_{ε}(μ) + a_{ε}^{2}μE_{ε}};  (45)

(b) when k < ε:

p_{k}(A) = A_{k} , n_{k} = p_{k}(λ). □  (46)

Corollary 4.6 Let Γ = (V, E) be a τ-partially walk-regular graph as above, with diameter D(Γ). Then, for k ≤ ⌊\frac{τ}{2}⌋ if τ < d, or k ≤ d − 1 otherwise,

(a) |Γ_{k}(u)| ≤ p_{k}(λ)E_{k} ∑_{μ≥1} \frac{1}{p_{k}(λ)σ_{k}(μ)^{2} + a_{k}^{2}μ^{2}E_{k}}, for every u ∈ V;

(b) min_{μ≥1}{p_{k}(λ)σ_{k}(μ)^{2} + a_{k}^{2}μ^{2}E_{k}} > p_{k}(λ)E_{k} ⇒ D(Γ) < k. □

Corollary 4.7 Let Γ be a τ-partially walk-regular graph as above. Let k ≤ ⌊\frac{τ}{2}⌋ if τ < d, or k ≤ d − 1 otherwise. Then, p_{k}(A) = A_{k} if and only if 1/a_{k} is an integer and n_{k} = p_{k}(λ). □

Let us now consider the case k = d − 1. Then we have

E_{d−1} = n − q_{d−1}(λ) = q_{d}(λ) − q_{d−1}(λ) = p_{d}(λ)

and (43) becomes

n_{d−1}^{μ} ≤ \frac{p_{d−1}(λ)p_{d}(λ)}{p_{d−1}(λ)σ_{d−1}(μ)^{2} + a_{d−1}^{2}μ^{2}p_{d}(λ)}.  (47)

When d = 3 the above result proves a conjecture of Van Dam [10] about the number of non-adjacent vertices to any given vertex u ∈ V, which have μ common neighbours with it. (Notice that, with our notation, such a number is just n_{2}^{μ}.)

Corollary 4.8 Let Γ be a regular graph with four distinct eigenvalues, and proper polynomials p_{k} with leading coefficients a_{k}. Then, for any vertex u ∈ V, the number of vertices non-adjacent to u, which have μ common neighbours with u, is upper-bounded by

n_{2}^{μ} ≤ \frac{p_{2}(λ)p_{3}(λ)}{p_{2}(λ)(a_{2}μ − 1)^{2} + a_{2}^{2}μ^{2}p_{3}(λ)}. □  (48)

Van Dam derived his bound without using the proper polynomials, thus obtaining two involved (equivalent) expressions in terms of the eigenvalues and multiplicities, which he denoted by h(Σ, μ) and g(Σ, μ) —with Σ denoting the spectrum. (He proved that the bound applies when g(Σ, μ) is a non-negative integer, and conjectured that this condition could be dropped.) The proof of the equivalence between such expressions and our bound is a cumbersome, but straightforward, computation (just use Gram-Schmidt method from 1, x, x^{2}, x^{3} to obtain the proper polynomials.)

Example 4.9 Let us consider a regular graph Γ with spectrum S(Γ) = {4^{1}, 2^{3}, 0^{3}, −2^{5}}. Then n = 12, and its proper polynomials and their values at λ = 4 are:

• p_{0} = 1, 1;

• p_{1} = x, 4;

• p_{2} = \frac{2}{3}(x^{2} − x − 4), \frac{16}{3};

• p_{3} = \frac{1}{12}(3x^{3} − 8x^{2} − 16x + 20), \frac{5}{3};

Then, Corollary 4.8 gives

n_{2}^{μ} ≤ ⌊\frac{20}{7μ^{2} − 16μ + 12}⌋

and hence, for μ = 0, 1, 2, 3, 4, … we get the bounds 1, 6, 2, 0, 0, …, respectively. An example of a graph with such a spectrum is the one given by Godsil in [24, Chap. 5] (as an example of walk-regular graph which is neither vertex-transitive nor distanceregular.) This graph can be constructed as follows: take two copies of the 8-cycle with vertex set ℤ_{8} and chords {1, 5}, {3, 7}; joint them by identifying vertices with the same even number and, finally, add edges between vertices labelled with equal odd number. The automorphism group of this graph has two orbits, formed by even and odd vertices respectively. Then, for an even vertex the values of n_{2}^{μ} are 1, 4, 2, 0, 0, …; whereas for an odd vertex they turn out to be 0, 6, 1, 0, 0, …

In his thesis, Van Dam also proved and characterized the case when equality in (48) is attained for every vertex, as stated in the next theorem.

Theorem 4.10 [10] Let Γ be a (connected) regular graph with four distinct eigenvalues, S(Γ) = {λ, λ_{1}^{m_{1}}, λ_{2}^{m_{2}}, λ_{3}^{m_{3}}}. Then, Γ is one of the classes of a 3-class association scheme if and only if there exists an integer μ ≥ 0 such that the number n_{2}^{μ} attain the bound in (48) for every vertex u.

In our context, a short proof of this theorem can be done by using Theorem 4.5. The most difficult part in Van Dam’s proof is to show sufficiency, where interlacing techniques are used. Within our approach we have that, if equality is attained for every vertex, then either: A_{2}^{μ}, A_{2}^{μ′} ∈ A(A) by (44) when D = 2 (since J = H(A) and A_{2}^{μ′} = J −A_{2}^{μ}−A−I;) or A_{2}, A_{3} ∈ A(A) by (46) when D = 3 (A_{3} = J −A_{2}−A−I,) in which case Γ is distance-regular. Then, the theory of association schemes assures that, in both cases, Γ is indeed one of the classes of a 3-class association scheme.

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.

References

[1] N. Alon and V.D. Milman, λ_{1}, Isoperimetric inequalities for graphs and superconcentrators, J. Combin. Theory Ser. B 38 (1985) 73–88.

[2] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes. Benjamin-Cummings Lecture Note Ser. 58, Benjamin/Cummings, London, 1984.

[3] N. Biggs, Girth, valency and excess, Linear Algebra Appl. 31 (1980) 55–59.

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

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

[6] F.R.K. Chung, Diameter and eigenvalues, J. Amer. Math. Soc. 2, No. 2 (1989) 187–196.

[7] F.R.K. Chung, V. Faber and T.A. Manteuffel, An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian, SIAM J. Discrete Math. 7, No. 3 (1994) 443–457.

[8] D.M. Cvetković and M. Doob, Developments in the theory of graph spectra, Linear and Multilinear Algebra 18 (1985) 153–181.

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

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

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

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

[13] C. Delorme and P. Solé, Diameter, covering index, covering radius and eigenvalues, European J. Combin. 12 (1991) 95–108.

[14] C. Delorme and J.P. Tillich, Eigenvalues, eigenspaces and distances to subsets, Discrete Math. 165–166 (1997) 161–184.

[15] M.A. Fiol, Weight odd parameters and spectra of graphs, submitted.

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

[17] M.A. Fiol and E. Garriga, From local adjacency polynomials to locally pseudodistance-regular graphs, J. Combin. Theory Ser. B, to appear.

[18] M.A. Fiol and E. Garriga, Pseudo-distance-regularity around a set, orthogonal polynomials, and completely regular codes, submitted.

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

[20] M.A. Fiol, E. Garriga and J.L.A. Yebra, From regular boundary graphs to antipodal distance-regular graphs, submitted.

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

[22] M.A. Fiol, E. Garriga, and J.L.A. Yebra, The alternating polynomials and their relation with the spectra and conditional diameters of graphs, Discrete Math. 167–168 (1997) 297–307.

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

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

[25] C.D. Godsil and B.D. McKay, Feasibility conditions for the existence of walkregular graphs, Linear Algebra Appl. 30 (1980), 51–61.

[26] R.L. Graham, M. Grötschel, and L. Lovász, eds., Handbook of Combinatorics. Elsevier Science, Amsterdam, 1995.

[27] W.H. Haemers, Eigenvalue Techniques in Design and Graph Theory, Math. Centre Tract 121, Mathematical Centre, Amsterdam, 1980.

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

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

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

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

[32] B. Mohar, Eigenvalues, diameter and mean distance in graphs, Graphs Combin. 7 (1991) 53–64.

[33] A Neumaier, Completely regular codes, Discrete Math. 106/107 (1992) 353–360.

[34] A.F. Nikiforov, S.K. Suslov and V.B. Uvarov, Classical Orthogonal Polynomials of a Discrete Variable. Springer-Verlag, Berlin, 1991.

[35] D.L. Powers, Partially distance-regular graphs, in Graph Theory, Combinatorics, and Applications (ed. Y. Alavi, G. Chartrand, O.R. Oellermann, and A.J. Schwenk) John Wiley & Sons, New York (1991) 991–1000.

[36] G. Quenell, Spectral diameter estimates for k-regular graphs, Adv. Math. 106 (1994) 122–148.

[37] J.A. Rodríguez, Cotas de Diversos Parámetros de un Grafo a Partir de los Autovalores de su Matriz Laplaciana. Ph.D. Thesis, Universitat Politècnica de Catalunya, 1997.

[38] A.J. Schwenk and R.J. Wilson, On the eigenvalues of a graph, in Selected Topics in Graph Theory (ed. L.W. Beineke and R.J. Wilson), Academic Press, New York (1978) 307–336.

[39] P.C. Sarnak, Some Applications of Modular Forms, Cambridge Univ. Press, Cambridge, 1990.