Some applications of the proper and adjacency polynomials in the theory of graph spectra

Some Applications of the Proper and Adjacency Polynomials in the Theory of Graph Spectra M.A. Fiol Departament de Matem`atica Aplicada i Telem`atica, Universitat Polit`ecnica de Catalunya,Jordi Girona, 1–3 , M`odul C3, Campus Nord 08034 Barcelona,Spain; email: [email protected] Submitted: February 22, 1997; Accepted: September 15, 1997. Abstract Given a vertex u∈Vof 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 uto 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 the electronic journal of combinatorics 4 (1997), #R21 2 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´c, Doob, and Sachs [9] , and the comprehensive text about distance-regular graphs of Brouwer, Cohen and Neumaier [5] . (See also the surveys of Cvetkovi´c 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. [7] ,[6] , Van Dam and Haemers [11] , Delorme and Sol´e [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, [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 dfrom 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] . the electronic journal of combinatorics 4 (1997), #R21 3 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 uis ε(u):=max v∈V∂(u, v), the diameter ofΓisD(Γ) := maxu∈Vε(u), and its radius is r(Γ) := minu∈Vε(u). As usual, Γk(u), 0 ≤k≤ε(u), denotes the set of vertices at distance kfrom u, and Γk,0≤k≤D, is the graph on Vwhere two vertices are adjacent whenever they are at distance kin Γ. Thus, Γ1(u)=Γ(u) and Γ1= Γ. The k-neighbourhood of uis then defined as Nk(u):=Sk l=0 Γl(u)={v:∂(u, v)≤k}.A closely related parameter is the so-called k-excess of u, denoted by ek(u), which is the number of vertices which are at distance greater than kfrom u, that is ek(u):= |V\N k (u)|. Then, trivially, e0(u)=n−1 and eD(u)=e ε(u) (u) = 0. Furthermore, note that ek(u) = 0 if and only if the eccentricity of usatisfies ε(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 er(u) of (any) vertex uin a regular graph with girth g=2r+1(ris 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,euwill denote the u-th unitary vector of the canonical base of Rn. Besides, we consider A, the adjacency matrix of Γ, as an endomorphism of Rn.A polynomial in the vector space of real polynomials with degree at most k,p∈Rk[x], will operate on Rnby the rule pw:= p(A)w, where w∈Rn, 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, Jdenotes the n×nmatrix with all entries equal to 1, and similarly j∈Rnis the all-1 vector. The spectrum of Γ is the set of eigenvalues of Atogether with their multiplicities S(Γ) := {λ0,λ m 1 1,...,λ m d d} where the supraindexes denote multiplicities. Because of its special role, the largest (positive and with multiplicity one) eigenvalue λ0will 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, ν=jwhen Γ is regular. We will denote by Mthe 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)→Rndefined by ρU:= Pu∈Uνueufor any vertex subset U6=∅, 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 uturns out to be a constant: δρ(u):= 1 ν uX 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] the electronic journal of combinatorics 4 (1997), #R21 4 ,[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 [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⊂Vsatisfying a given property P, we can define the corresponding weight parameter, denoted by ξ?, as the maximum [minimum] value of kρUk2of a vertex set Usatisfying 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):=kρ(V\N k (u))k2=kνk2−kρN k(u)k2 , and we also use the notion of pseudo-distance-regularity, which is defined as follows. Given a vertex u∈Vof a graph Γ, with eccentricity ε(u)=ε, consider the partition V=V0∪V1∪···∪V εwhere Vk:= Γk(u), 0 ≤k≤ε. Then, we say that Γ is pseudo-distance-regular around vertex uwhenever the numbers ck(v):= 1 ν vX w∈Γ(v)∩Vk−1 νw,a k (v):= 1 ν vX w∈Γ(v)∩Vk νw,b k (v):= 1 ν vX w∈Γ(v)∩Vk+1 νw, defined for any v∈Vkand 0 ≤k≤ε(where, by convention, c0(u)=0andb ε (v)=0 for any v∈Vε) do not depend on the considered vertex v∈Vk, but only on the value of k. In such a case, we denote them by ck,akand bkrespectively. Then, the matrix I(u):=   0c 1··· c ε−1c ε a 0a 1··· a ε−1a ε b 0b 1··· b ε−10   is called the (pseudo-)intersection array around vertex uof Γ. 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 Γ = P3×P3, where P3denotes the path graph on three vertices {u1,u 2,u 3}and positive eigenvector (νu1,ν u 2,ν u 2) >=(1, √ 2,1)>, has positive eigenvector νwith entries ν(ui,uj)=νuiνuj,i, j ∈{1,2,3}. Using this, it can be easily checked that Γ pseudo-distance-regular around the “central” vertex (u2,u 2), and also around every “corner” vertex (ui,u j), i, j ∈{1,3},i6=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):=   0√ 22 √ 2 000 2 √ 2 √ 20    . Finally, recall that a (symmetric) association scheme with dclasses can be defined as a set of dgraphs Γi=(V,Ei), 1 ≤i≤d, on the same vertex set V, with adjacency the electronic journal of combinatorics 4 (1997), #R21 5 matrices Aisatisfying Pd k=0 Ak=J, with A0:= I; and AiAj=Pd k=0 pk ijAk, for some integers pk ij,0≤i, j, k ≤d. Then, following Godsil [24] , we say that the graph Γiis 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 Uibe the matrix whose columns form an orthonormal basis for the eigenspace corresponding to λi, Ker(A−λiI). The (principal) idempotents of Aare the matrices Ei:= UiU> irepresenting the orthogonal projections onto Ker(A−λiI). Thus, in particular, E0=1 kνk2νν>. Therefore, such matrices satisfy the following properties (see Godsil [24] ): (a.1) EiEj=(Eiif i=j 0otherwise; (a.2) AEi=λiEi; (a.3) p(A)=Pd i=0 p(λi)Ei,p∈R[x]. Given a vertex u∈Vand an eigenvalue λi, Garriga, Yebra, and the author [21] defined the (u-)local multiplicity of λias mu(λi):=kE i e u k 2=(E i ) uu (0 ≤i≤d) so that mu(λi)≥0 and, in particular, mu(λ0)= ν 2 u kνk 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) d X i=0 mu(λi)= d X i=0 kEieuk2=keuk2=1 (u∈V); (b.2) X u∈V mu(λi)=trE i=m i(0 ≤i≤d); (b.3) Ck(u):=(A k ) uu = d X i=0 mu(λi)λk i, the electronic journal of combinatorics 4 (1997), #R21 6 where Ck(u) is the number of closed k-walks going through vertex u.Ifµ 0 (= λ)> µ1>···>µ d urepresent the eigenvalues with non-null local multiplicities, we define the (u-)local spectrum as Su(Γ) := {λmu(λ),µ m u(µ 1) 1,...,µ m u(µ d u) d u}. Moreover, we introduce the (u-)local mesh as the set Mu:= {λ>µ 1>···>µ d u }. Then it can be proved that the eccentricity of usatisfies ε(u)≤du=|Mu|−1 (see [21] .) From the u-local spectrum we introduce in Rdu[x] the (u-)local scalar product hf,giu:= du X i=0 mu(µi)f(µi)g(µi) (1) whose relation with the (standard) Euclidean product h·,·i is hfeu,ge ui=(f(A)g(A))uu =  d X i=0 f(λi)Ei d X j=0 g(λj)Ej uu = d X i=0 f(λi)g(λi)(Ei)uu =hf,giu where we have used properties (a.3) and (a.1). In particular, the relation between the corresponding norms is kfeuk=kfku. Moreover, note that, according to property (b.1), the weight function ρi:= mu(µi), 0 ≤i≤d, of the scalar product (1)is normalized in such a way that Pd i=0 ρi=1. 2.2 The proper polynomials Let us consider an orthonormal system of polynomials {gk: dgr gk=k,0≤k≤du} with respect to the above scalar product (1). From these polynomials, and taking into account that gk(λ)6= 0 since the roots of gkare within the interval (µdu,µ 0), we can define another orthogonal secuence by pu k=gk(λ)gk,0≤k≤d u , which clearly satisfy the following orthogonal property hpu k,p u liu=δ klpu k(λ)(0≤k,l ≤du),(2) so that kpu kk2 u=pu k(λ). 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 xpu k=bk−1pu k−1+akpu k+ck+1pk+1xpu k=bk−1pu k−1+akpu k+ck+1pu k+1 (0 ≤k≤d),(3) where ak,bkand ckare the corresponding Fourier coeficients of xpu kin terms of pu k−1, pu k, and pu k+1 respectively (b−1=cd+1 = 0), initiated with pu −1= 0 and pu 0= 1. (See, the electronic journal of combinatorics 4 (1997), #R21 7 for instance, [34] .) Notice that the value of pu 0is a consequence of the fact that the weight function is normalized, since then kpu 0k2=Pd i=0 ρi=1=p u 0(λ). 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 uof a graph Γ, there exists a unique orthogonal system pu 0(= 1),p u 1,...,p u d u, characterized by any of the following conditions: (a) kpu kk2 u=pu k(λ); (b) ak+bk+ck=λ(0 ≤k≤du); (c) Pdu k=0 pu k=kνk2 ν2 uπ0Qdu k=0(x−µk), where π0=Qdu k=0(λ−µk).2 In the same papers it was shown that the highest degree polynomial pu dusatisfies the following properties: (c.1) The u-local multiplicities of Γ are given by mu(µi)= ν 2 u φ 0 p u d u(λ) kνk 2 φ i p u d u(µ i )(0 ≤i≤du) (4) where φi=Qdu j=0(j6=i)(µi−µj); (c.2) The value at λof the highest degree polynomial is pu du(λ)= 1 m 2 u (λ)π 2 0 Pd u i=0 1 mu(µi)π2 i (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 {u1,u 2,u 3}, considered in the Introduction. Then the spectrum of Γis S(Γ) = {2√21,√22,03,−√22,−2√21}, whereas the local spectrum of the central vertex u= (u2,u 2)is Su(Γ) = {2√2 1 4,01 2,−2√2 1 4}. From this, one can compute the u-local proper polynomials and their values at λ=2 √ 2, giving: •pu 0=1,1; •p u 1 = 1 √ 2 x,2; •p u 2 = 1 4 x 2 −1,1; the electronic journal of combinatorics 4 (1997), #R21 8 Example 2.3 Let Γ=LP, the line graph of the Petersen graph, with spectrum S(Γ) = {41,25,−14,−25}. Then every vertex uof Γhas local spectrum Su(Γ) = {41 15 ,21 3,−14 15 ,−21 3}. Hence, the u-local proper polynomials and their values at λ=4 turn out to be: •pu 0=1,1; •p u 1 =x,4; •p u 2 =x 2 −x−4,8; •p u 3 = 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 pu k(A)=A k(0 ≤k≤du) where Akstands 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 pu kis the k-distance polynomial of Γ and, consequently (see, for instance, [5] ) , Γ is distanceregular. 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 pu k, dgr pu k=k, satisfying pu keu=1 νu pu keu=1 νu ρVk,p u k (λ)= 1 ν 2 ukρV k k 2(0 ≤k≤ε) (6) (the latter equality being a consequence of the former) where Vk=Γ 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 Su(Γ) as above, if and only if 1 ν2 ukρVduk2=pu du(λ)= 1 m 2 u (λ)π 2 0 Pd u i=0 1 mu(µi)π2 i (7) where πi=Qdu j=0(j6=i)|µi−µj|,0≤i≤du.2 the electronic journal of combinatorics 4 (1997), #R21 9 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, Vdu=V2consists of the four corner vertices (ui,u j), i, j ∈{1,3},i6=j, with ν(ui,uj)= 1, giving 1 ν2 ukρV2k2=1=p u 2(λ). 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 ube a vertex of a graph Γ, with local mesh of eigenvalues Mu={λ>µ 1> ···>µ d u }.LetPbe a polynomial of degree k,0≤k≤du, such that kPku≤1. Then P(λ)≤1 νu P(λ)≤1 νukρNk(u)k,(8) and equality is attained if and only if Peu=1 kρNk(u)kPeu=1 kρNk(u)kρNk(u),(9) in which case kPku=1. Moreover, if this is the case and k=du−1,ε(u)=d u , then Γis pseudo-distance-regular around vertex u.2 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) Pof degree ≤ksuch that kPku≤1 and P(λ) is maximum. The study of these polynomials, called the (u- )local adjacency polynomials and denoted by Qu k,0≤k≤d u , was done in [17] , and their basic properties are the following: (d.1) There exists a unique local adjacency polynomial Qu k, with dgr Qu k=k, for any k=0,1,...,d u, and kQu kku=1; (d.2) The local adjacency polynomials of degrees 0, 1, and du, and their values at λ, are the following: •Qu 0=1; Q u 0(λ)=ke u k=1; •Q u 1=1 qλ 2 δ(u)+1 qλ δ(u)x+1 ;Q u 1(λ)=qλ 2 δ(u)+1 •Q u d u=kνk ν u π 0Qd u i=1(x−µi), where π0=Qdu i=1(λ−µi); Qu du(λ)= 1 ν ukνk; (d.3) In general, the local adjacency polynomials can be computed from the local proper orthogonal system {pu k}in the following way: the electronic journal of combinatorics 4 (1997), #R21 16 2.8we have seen that Pu∈VkQkk2 u=n. Consequently, we must have kQkku= 1 and, using again Theorem 2.5, we infer that Qkeu=1 kρNk(u)kρNk(u)= 1 q|N k (u)|ρN k (u), or pkeu=ρΓk(u) for every u∈Vand 0 ≤k≤d0. But this is equivalent to pk(A)=A k , for any 0 ≤k≤d0,andΓisd 0 -partially distance-regular. 2 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∈Vbe 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 kfrom u∈Vand there exist exactly µ(shortest) k-paths from uto each of such vertices. Note that Γ0 k(u)=V\N k (u), and if µ6= 0, then Γµ k(u) contains only vertices at distance kfrom u, so that we get the partition Γk(u)=∪ µ≥1 Γ µ k (u). The next theorem gives an upper bound for kρΓµ k(u)k2, and hence also for the cardinality of Γµ k(u). Theorem 4.1 Let ube a vertex of a graph Γ, with eccentricity ε(u)=ε, and local mesh of eigenvalues Mu={λ>µ 1>···>µ d u }.LetPbe a polynomial of degree k<d uwith leading coefficient cksuch that νuP(λ)=1+kνk 2 c k µ. Then, for any given integer µ>0, kρΓ µ k(u)k 2≤kνk 2(kνk 2 kPk 2 u−ν 2 u P2 (λ)) 1+kνk2 kPk2 u−ν 2 u P2 (λ),(18) where the equality is attained if and only if nµ k:= |Γµ k(u)|=kρΓµ k(u)k2and either (a) when k=ε: Peu=νuP(λ)(kνk2−nµ ε)+n µ ε kνk2 (kνk2−n µ ε)ν−1 kνk2−n µ ε ρΓ µ ε(u) ; (19) the electronic journal of combinatorics 4 (1997), #R21 17 (b) when k<ε: Pe u=−1 kνk 2−n k Pe u=−1 kνk 2−n k ρV k,(20) where Vk=Γ k (u)=Γ µ k(u)and nk:= |Vk|=kνk2νuP(λ) νuP(λ)−1,(21) in which case kPk2 u P(λ)=νuckµ. (22) Proof. First, let Pbe any polynomial with degree k<d uand assume µ≥0 (µ>0ifk=ε.) Let U:= Γµ k(u). From the following spectral decompositions of ρu=νueuand ρU=Pv∈Uνvev: ρu=ν2 u kνk2ν+z,ρU=kρUk2 kνk2ν+z0 where z,z0∈ν⊥, we obtain Pρu=ν2 uP(λ) kνk2ν+Pzand so kPzk2=kPρuk2−ν4 uP2(λ) kνk2=ν2 u kPk2 u−ν2 uP2(λ) kνk2!; (23) kz0k2=kρUk2 1−kρUk2 kνk2!.(24) Hence, ckµνukρUk2≥ckµνuX v∈U νv=hPρu, ρUi=*ν2 uP(λ) kνk2ν+Pz,kρUk2 kνk2ν+z0+ =ν2 ukρUk2 kνk2P(λ)+hPz,z 0i≥ν 2 u kρUk 2 kνk 2P(λ)−kPzkkz0k =ν2 ukρUk2 kνk2P(λ)−νukρUk2v u u t kPk2 u−ν2 uP2(λ) kνk2! 1 kρUk2−1 kνk2! Simplifying and rearranging the terms, we get kνk2 kρUk2≥(νuP(λ)−kνk2 c kµ) 2 kνk2 kPk2 u−ν 2 u P2 (λ)+1,(25) where Φ:=kνk 2 kPk 2 u−ν 2 u P2 (λ)= d u X i=1 mu(µi)P2(µi)>0 the electronic journal of combinatorics 4 (1997), #R21 18 since mu(λ)= ν 2 u kνk 2and dgr P<d u . (Notice that √Φ 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 kρUk2in (25), we obtain the inequality kρΓµ k(u)k2≤kνk2kPk2 u−ν2 uP2(λ) kνk2c2 kµ2−2νuP(λ)ckµ+kPk2 u .(26) which, in the case µ=0(k<ε), particularizes to kρΓ0 k(u)k2=kνk2−kρN k(u)k2≤kνk 2−ν 2 u P2 (λ) kPk 2 u , so that P(λ) kPku≤1 νukρNk(u)k and, when kPku≤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 Pby a constant, and when νuP(λ)=kνk 2 c k µsuch a bound takes the trivial value kνk2. Thus, assuming νuP(λ)−kνk 2 c k µ6= 0, we can choose, without loss of generality, the polynomial Pin such a way that P(λ)=(1+kνk 2 c k µ)/νu. In this case, (25) becomes kνk2 kρUk2≥1 kνk2kPk2 u−ν2 uP2(λ)+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 µ6=0)wehavekρUk 2=Pv∈Uν 2 v=Pv∈Uν v , so that νv= 1 for all v∈U, whence kρUk2=|ρU|. Second, we must have cos{Pz,z0}=−1, and therefore, using (23), (24), and the spectral decomposition of ρU, we can compute Pzin the following manner: Pz=−kPzk kz0kz0=− νurkPk2 u−ν2 uP2(λ) kνk2 r|U|1−|U| kνk2 ρU−|U| kνk2ν! =−νu kνk2−|U| ρU−|U| kνk2ν ! Using the above expression in the spectral decomposition of Pρu,weget Pρu=ν 2 u P(λ) kνk 2ν+Pz=ν 2 u P(λ) kνk 2ν−ν u kνk 2−|U| ρU−|U| kνk2ν ! so that, denoting the multiplicative constants of νand ρUby βkand γk, respectively, Peu=βkν+γkρU=νuP(λ)(kνk2−|U|)+|U| kνk2 (kνk2−|U|)ν−1 kνk2−|U|ρU. (28) the electronic journal of combinatorics 4 (1997), #R21 19 This gives (19) when k=ε(with nµ ε=|U|) which, using the value of νuP(λ), can also be written as Peu=βεPeu=βεν+γερΓµ ε(u)=1+c kµ(kνk2−n µ ε) kνk2−n µ ε ν−1 kνk2−n µ ε ρΓ µ ε(u).(29) From this last expression, we get that if v∈Γµ ε(u), then νv=(ρΓ µ ε (u))v=1 and (Peu)v=βε−γε=ckµ(as it should be.) Otherwise, if v/∈Γ µ ε (u), we have (ρΓµ ε(u))v= 0 and hence (Peu)v=βενv. In particular, if v∈Γε(u)\Γµ ε(u), it must be (Peu)v=ckµv, where µv≥0 is the number of ε-paths from uto v. Thus, µv=βε ck ν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 = (Peu)v= 0 for any vertex vsuch that ∂(u, v)≥k. Hence, we must have βk=0in (28) and, therefore, Peu=γkρU. Furthermore, (P(A))uv 6= 0 for all v∈Γk(u)=V k , and therefore Umust be the whole set Vk, giving (20). The value of nµ k=nk, given in (21), is obtained from the equation βk= 0. Finally, condition (22) comes from equating such a value of nkto the upper bound in (18). 2 From the above proof, note that (18) also applies when dgr P=du, provided that P(µi)6= 0 for some 1 ≤i≤du(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 ube a vertex of a graph Γ, with local spectrum Su(Γ) = {λmu(λ),µ m u(µ 1) 1,...,µ m u(µ d u) d u}, and positive eigenvector ν, and let pu k,0≤k≤du,be the local proper polynomials. Let akdenote the leading coefficient of pu k, and consider the sum polynomials qu k=Pk l=0 pu l. For any given integers µ>0and 0≤k<d u , consider the spectral weight k-excess Ek=kνk2−ν2 uqu k(λ), and define σk(µ):=ν u a k µ−1. Then, kρΓµ k(u)k2≤pu k(λ)Ek pu k(λ)σk(µ)2+a2 kµ2Ek ,(31) and equality is attained if and only if kρΓµ k(u)k2=nµ k, and either (a) when k=ε: P∗eu=β∗ εν+γ∗ ερΓµ ε(u),(32) with the polynomial P∗:= aεµEεpu ε+pu ε(λ)σε(µ)νuqu ε(33) and constants β∗ ε:= pu ε(λ)σε(µ),γ ∗ ε := pu ε(λ)σε(µ)2+a2 εµ2Eε; (34) the electronic journal of combinatorics 4 (1997), #R21 20 (b) when k<ε: p u k e u=1 ν u p u k e u=1 ν u ρV k,(35) in which case nµ k=nk=ν2 upu k(λ).(36) Proof. Let us consider a generic polynomial P=Pk l=0 αlpu l,αl∈R. Since Pmust have leading coefficient ck=αkak, we impose the condition P(λ)=(1+ α k a k nµ)/νu, and hence P= k X l=1 αlpu l+1+α ka knµ νu− k X l=1 αlpu l(λ); (37) kPk2 u= k X l=1 α2 lpu l(λ)+ 1+α ka knµ νu− k X l=1 αlpu l(λ)!2 .(38) Therefore, looking at (27), our aim is to minimize the function Φ=Φ(α 1 ,...α k)=kνk 2 kPk 2 u−ν 2 u P2 (λ)=kνk 2 kPk 2 u−(1 + kνk2αkakµ)2 with kPk2 ugiven 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=ν up u k(λ)(1 −νuakµ) ∆, αk=νupu k(λ)−akµ(kνk2−ν2 uqu k−1(λ)) ∆, where ∆=ν 2 u q u k−1 (λ)(pu k(λ)−a2 kµ2kνk2)+(ν u p u k(λ)−a kµkνk2 ) 2 or, using qu k−1(λ)=q u k(λ)−p u k (λ) and the definitions of Ekand σk(µ), α1=α2=···=α k−1=−ν up u k(λ)σ k(µ) ∆, α k=ν up u k(λ)−a kµEk ∆, with ∆=(kνk 2 a 2 k µ 2−p u k (λ))Ek+kνk2pu k(λ)σk(µ)2. Then, such a minimum turns out to be Φmin =pu k(λ)Ek ∆ and, according to (18), the upper bound in (31) comes from kνk2Φ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=−1 ∆(akµEkpu k+νupu k(λ)σk(µ)qu k).(39) the electronic journal of combinatorics 4 (1997), #R21 21 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=−1 ∆pu k(λ)σk(µ) and γk=−1 ∆pu k(λ)σk(µ)2+a2 kµ2Ek respectively, thus giving P∗eu=β∗ kν+γ∗ kρΓµ k(u) (40) with P∗=−∆P,β∗ k=−∆βkand γ∗ k=−∆γk. Now, from these facts we can reason as in Theorem 4.1to 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 µvof ε-paths from uto vis obtained from νvβ∗ ε=νvpu ε(λ)σε(µ)=c ∗ ε µ v ,(41) where c∗ εstands here for the leading coefficient of P∗, that is c∗ ε=aε(aεµEε+νupu ε(λ)σε(µ)) . Finally, in the case k<ε, the only real solution obtained when we solve Eq. (22) for µturns out to be µ=1 akν, 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). 2 Notice that, as in the case of Theorem 4.1, the bound (31) also applies when µ= 0, giving kρΓ0 k(u)k2=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 kνk2=nand kρΓµ k(u)k2=nµ k. Moreover, when the corresponding bound (31) is attained for k=ε, the value of µvin (41) becomes a constant, say µ0, for every vertex v∈Γε(u)\Γµ ε(u). Namely, µ0=β∗ ε c∗ ε =pu ε(λ)σε(µ) aεpu ε(λ)σε(µ)+a 2 εµEε .(42) Consequently, we get the partition Γε(u)=Γ µ ε (u)∪Γ µ 0 ε(u). In this case, a more compact way of giving the above relation between µand µ0is pu ε(λ)σε(µ)σε(µ0)=E ε a 2 ε µµ0, showing the symmetry between both parameters. Notice that, in particular, it might be µ0= 0, in which case β∗ ε=pu ε(λ)σε(µ) = 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 ube a vertex of a graph Γ, with eccentricity ε(u)and local proper polynomials pu k. Then, for k<d u , the electronic journal of combinatorics 4 (1997), #R21 22 (a) kρΓk(u)k2≤pu k(λ)EkX µ≥1 1 pu k(λ)σk(µ)2+a2 kµ2Ek ; (b) min µ≥1{pu k(λ)σk(µ)2+a2 kµ2Ek}>p u k (λ)E k⇒ε(u)<k. Proof. (a) is a direct consequence of the theorem and kρΓk(u)k2=Pµ≥1kρΓµ k(u)k2. To prove (b) notice that, from nµ k≤kΓ µ k(u)k 2and the given condition, we get nµ k≤$pu k(λ)Ek pu k(λ)σk(µ)2+a2 kµ2Ek%<1 for any µ≥1. Thus, nk= 0 and the result follows. 2 Corollary 4.4 Let ube a vertex of a graph Γ, with eccentricity ε(u)=ε, and local proper polynomial pu kwith degree k<εand leading coefficient ak. Then, (35) holds, that is pu keu=1 νuρVk, with kρVkk2=|Vk|, if and only if the quotient 1/νuakis an integer, say µ, and the number nk=|Vk|of vertices at distance kfrom uis given by (36): nk=nµ k=ν2 upu k(λ). Proof. Assuming that (35) holds and kρVkk2=|Vk|,wehave ν u p u k (λ)=he u ,p u k(λ)νi=hp u ke u,νi=1 ν uhρV k,νi=1 ν ukρV kk2=n k ν u and, for any vertex v∈Vk, (Ak)uv =hAkeu,evi=1 akhpu keu,evi=1 akνuhρVk,evi=1 akνu . Hence, nkis given by (36), and 1/akνuis an integer. Conversely, if such is the case, then the upper bound in (31) for µ=1/νvakbecomes ν2 upu k(λ), and Theorem 4.2 (k<ε) applies. 2 When the considered graph is partially walk-regular, and the equality is attained for all vertices, the results of Theorem 4.2look much better, as it is shown next. Theorem 4.5 Let Γ=(V,E)be a τ-partially walk-regular graph on nvertices, with adjacency matrix Aand spectrum S(Γ) = {λ, λm1 1,...,λ m d d}.Letp kbe the proper polynomial with degree k≤bτ 2cif τ<d,ork≤d−1otherwise, and leading coefficient ak.Letq k= P k l=0 pl,Ek=n−qk(λ)and, for a given integer µ, let σk(µ)=a k µ−1, and denote by Aµ kthe adjacency matrix of Γµ k. Then, for any u∈V, nµ k≤pk(λ)Ek pk(λ)σk(µ)2+a2 kµ2Ek ,(43) and equality is attained for every vertex if and only if either the electronic journal of combinatorics 4 (1997), #R21 23 (a) when k=ε: P∗(A)=β ∗ εJ+γ ∗ εA µ ε,(44) with P∗=aεµEεpε+pε(λ)σε(µ)qε,β∗ ε=pε(λ)σε(µ), and γ∗ ε=pε(λ)σε(µ)2+ a2 εµ2Eε; in which case Aε=Aµ ε+Aµ0 εwith µ0=pε(λ)σε(µ) aεpε(λ)σε(µ)+a 2 εµEε ; (45) (b) when k<ε: p k (A)=A k,n k =p k (λ).2(46) Corollary 4.6 Let Γ=(V,E)be a τ-partially walk-regular graph as above, with diameter D(Γ). Then, for k≤bτ 2cif τ<d,ork≤d−1otherwise, (a) |Γk(u)|≤p k (λ)E kX µ≥1 1 p k (λ)σ k (µ) 2+a 2 k µ 2 E k , for every u∈V; (b) min µ≥1{pk(λ)σk(µ)2+a2 kµ2Ek}>p k (λ)E k⇒D(Γ) <k.2 Corollary 4.7 Let Γbe a τ-partially walk-regular graph as above. Let k≤b τ 2 cif τ<d,ork≤d−1otherwise. Then, pk(A)=A kif and only if 1/akis an integer and nk=pk(λ).2 Let us now consider the case k=d−1. Then we have Ed−1=n−qd−1(λ)=q d (λ)−q d−1 (λ)=p d (λ) and (43) becomes nµ d−1≤pd−1(λ)pd(λ) pd−1(λ)σd−1(µ)2+a2 d−1µ2pd(λ).(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 pkwith leading coefficients ak. Then, for any vertex u∈V, the number of vertices non-adjacent to u, which have µcommon neighbours with u, is upper-bounded by n2nµ 2≤p2(λ)p3(λ) p2(λ)(a2µ−1)2+a2 2µ2p3(λ).2(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 3to obtain the proper polynomials.) the electronic journal of combinatorics 4 (1997), #R21 24 Example 4.9 Let us consider a regular graph Γwith spectrum S(Γ) = {41,23,03,−25}. Then n=12, and its proper polynomials and their values at λ=4are: •p0=1,1; •p 1 =x,4; •p 2 = 2 3 (x 2 −x−4),16 3; •p3=1 12 (3x3−8x2−16x+ 20),5 3; Then, Corollary 4.8gives nµ 2≤$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 Z8and 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µ 2are 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(Γ) = {λ, λm1 1,λ m 2 2,λ m 3 3}. Then, Γis one of the classes of a 3-class association scheme if and only if there exists an integer µ≥0such that the number nµ 2attain 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µ0 2∈A(A)by(44) when D= 2 (since J=H(A) and Aµ0 2=J−Aµ 2−A−I;) or A2,A3∈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´on Interministerial de Ciencia y Tecnolog´ıa, CICYT) under projects TIC 92-1228-E and TIC 94-0592. the electronic journal of combinatorics 4 (1997), #R21 25 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´c and M. Doob, Developments in the theory of graph spectra, Linear and Multilinear Algebra 18 (1985) 153–181. [9] D.M. Cvetkovi´c, 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´e, 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.