The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs

The Alternating and Adjacency Polynomials, and their Relation with the Spectra and Diameters of Graphs ∗ M.A. Fiol, E. Garriga Departament de Matem`atica Aplicada i Telem`atica Jordi Girona 1–3, M`odul C3, Campus Nord Universitat Polit`ecnica de Catalunya 08034-Barcelona, SPAIN February 16, 1998 Abstract Let Γ be a graph on nvertices, adjacency matrix A, and distinct eigenvalues λ>λ1> λ2>··· > λd. For every k= 0,1, . . . , d−1, the k-alternating polynomial Pk is defined to be the polynomial of degree kand norm kPkk∞= max1≤l≤d{|Pk(λl)|} = 1 that attains maximum value at λ. These polynomials, which may be thought of as the discrete version of the Chebychev ones, were recently used by the authors to bound the diameter D(Γ) of Γ in terms of its eigenvalues. Namely, it was shown that Pk(λ)> kνk2−1⇒D(Γ) ≤k, where νis the (positive) eigenvector associated to λwith minimum component 1. In this work we improve upon this result by assuming that some extra information about the structure of Γ is known. To this end, we introduce the so-called τ-adjacency polynomial Qτ. For each 0 ≤τ≤d, the polynomial Qτis defined to be the polynomial of degree τand norm kQτkA= max1≤i≤n{kQτ(A)eik} = 1 that attains maximum value at λ. Then it is shown that Pk(λ)>kνk2/Q2 τ(λ)−1⇒ D(Γ) ≤k+ 2τ. Some applications of the above results, together with new bounds for generalized diameters, are also presented. Keywords: Adjacency polynomials; Conditional diameters, Eigenvalues ∗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. Emails: [email protected], [email protected] 1 1 Introduction In this paper Γ = (V, E) denotes a (simple and finite) connected graph, with vertex set V=VΓ, |V|=n, and edge set E=EΓ. For any vertex ei∈V, Γ(ei) denotes the set of vertices adjacent to ei, and δ(ei) = |Γ(ei)|denotes its degree. Then, Γ is (δ-)regular if δ(ei) = δfor all 1 ≤i≤n. The distance between two vertices eiand ejwill be denoted by ∂(ei, ej). The eccentricity of a vertex eiis εi=ε(ei) = maxej∈V∂(ei, ej), the diameter of Γ is D=D(Γ) = maxei∈Vε(ei), and its radius is r=r(Γ) = minei∈Vε(ei). Recently, much work has been done to give upper bounds on the diameter of a graph in terms of its spectrum. Let λ0(= δ)> λ1>··· > λdbe the d+ 1 distinct eigenvalues of a δ-regular graph Γ, with order nand diameter D. Thus, Alon and Milman [1] and Mohar [28] gave results in terms of the two first eigenvalues λ0and λ1. Then, several results using the first eigenvalue λ0and either the second largest eigenvalue in absolute value, λ∗= max{λ1,−λd}, or both λ1and λdhave been given by Lubotzky, Phillips, and Sarnak [27], and Chung [4]: D≤ln(n−1) ln(λ0/λ∗)+ 1,(1) Sarnak [31], and Chung, Faber and Manteuffel [5]: D≤$cosh−1(n−1) cosh−1(λ0/λ∗)%+ 1,(2) and Van Dam and Haemers [13]: D < ln 2(n−1) ln√λ0−λd+√λ0−λ1 √λ0−λd−√λ0−λ1 + 1.(3) As expected, most of the previous results can be improved if we have further information about the structure of Γ. This is the case, for instance, when the graph is bipartite, as it was shown by Delorme and Sol´e [14] and the authors [18], or when it is vertex-transitive, see Delorme and Tillich [15]. Another example is that considered by Quenell [29], where it is assumed that the girth gof Γ is known. More precisely, this author managed to prove the following diameter estimates: D≤    cosh−1n λ0(λ0−1)`−1−1 cosh−1(λ0/λ∗)   + 2`+ 1,(4) where `=bg−1 2c(≥1) is the so-called ‘injectivity radius’ [29] or ‘parameter `’ [16] (in the latter paper this parameter was used in the context of connectivity problems.) This result improves, for ‘large enough’ graphs (more precisely, when λ∗≥2√λ0−1), the result (2) of Sarnak [31], and Chung, Faber and Manteuffel [5]. 2 The results (1), (2) and (3) admit the following unified presentation. Let Pbe a real polynomial and set kPk∞= max1≤i≤d{|P(λi)|}. Then, P(λ0)>kPk∞(n−1) ⇒D(Γ) ≤dgr P, (5) whereas the result in (4) stems from the implication P(λ0)>kPk∞n λ0(λ0−1)`−1−1⇒D(Γ) ≤dgr P+ 2`. (6) With the formulation in (5), Chung [4] considered the case P=xk, Delorme and Sol´e [14] generalized her results by taking P=xk+txk−1,t∈R+, which has the advantage of being useful to the case of bipartite biregular graphs (that is, bipartite graphs such that vertices in the same vertex class have the same degree), and Sarnak [31], Chung, Faber and Manteuffel [5], and Van Dam and Haemers [13] used Chebychev polynomials shifted to the interval [λd, λ1]. Such polynomials were also used by Quenell [29] to derive (4) from (6). Other results, using the Laplacian matrix, can be found in [5, 18, 19, 28, 11, 12, 30]. Besides, in [14, 5, 18] the case of regular digraphs was also considered. However, the formulations in (5) and (6) suggest that, to optimize the results, we must face the discrete nature of the problem, and look for the polynomials that maximize the quotient P(λ0)/kPk∞. Or, alternatively, we should try to maximize P(λ0) when the considered polynomials are normalized by kPk∞= 1. This has been done by Yebra and the authors in [18, 19], for not necessarily regular graphs, introducing the alternating polynomials Pkof degree k. We collect here some of its main properties, referring the reader to [18] for a more detailed study: •There is a unique k-alternating polynomial Pkfor 0 ≤k≤d−1; •P0(λ0) = 1 < P1(λ0)<··· < Pd−1(λ0); •Pkmaximizes Pk(x) for all x > λ1and, for k6= 0, it is strictly increasing in [λ1,∞); •Pktakes k+ 1 alternating values ±1 at {λ1, λ2, . . . , λd}, starting with Pk(λ1) = 1 and ending with Pk(λd) = (−1)k; •There are explicit formulae for P0(= 1), P1,P2, and Pd−1, while the other polynomials can be computed by solving a linear programming problem (for instance, by the simplex method.) Some particular cases of these polynomials were also considered, in the same context, by Van Dam and Haemers in [13]. In terms of the alternating polynomials, and for not necessarily regular graphs, (5) becomes Pk(λ0)>kνk2−1⇒D(Γ) ≤k, (7) 3 where νis the normalized positive eigenvector, that is the eigenvector corresponding to λ0with smallest component equal to one. In the case of regular graphs, ν=j, the all-1 vector, and this simplifies to Pk(λ0)> n −1⇒D(Γ) ≤k. (8) In this work we improve upon the above results by assuming that some extra information about the structure of Γ is known. We begin this task in the next section, where some applications of a result on the ‘(s, t)-diameter’, given in [19], are derived; and some other ‘conditional diameters’ are considered. Then, in Section 3, we introduce a new family of polynomials which are defined in terms of the adjacency matrix A, and hence they are called the adjacency polynomials of Γ. Some first applications of these polynomials are also discussed. Finally, in Section 4 we give results involving both the alternating and the adjacency polynomials, which improve and generalize the previous results. We devote the rest of this section to recall the main terminology and known results used throughout the paper. In particular we pay attention to the local spectrum of a graph, a concept introduced by the authors in [21]. Let Abe the adjacency matrix of Γ = (V, E), that has d+ 1 distinct eigenvalues λ0> λ1>··· > λd. The spectrum of Γ, which is the set of the eigenvalues of Atogether with their multiplicities ml=m(λl), 0 ≤l≤d, is denoted by S(Γ) = {λm0 0, λm1 1, . . . , λmd d}. Because of its special role, the largest eigenvalue λ0will also be denoted by λ. As a consequence of Perron-Frobenius’ theorem, λis simple and positive, with positive eigenvector ν= (ν1, ν2, . . . , νn)>. As stated above, we will suppose that νis ‘normalized’ in such a way that its minimum component equals 1. As usual, we identify Awith an endomorphism of the ‘vertex-space’ of Γ, `2(V), which, for any given indexing of the vertices, is isomorphic to Rn. Thus, for a given ordering of its vertices, we only distinguish between a vertex eiand the corresponding vector eiof the canonical base of Rnby the bold type used. The adjacency algebra of A, denoted by A(A), is the algebra of all the matrices which are polynomials in A. For a given vertex ei∈Vwe can consider its ‘spectral decomposition’ ei= d X l=0 zil =νi kνk2ν+zi(9) where zil ∈Ker(x−λl) and zi∈ν⊥. We let a polynomial poperate on Rnby the rule pw=p(A)w, and the matrix is not specified unless some confusion may arise. For instance, using (9), pei=p(A)ei=p(λ)νi kνk2ν+p(λ1)zi1+···+p(λd)zid. The (ei-)local multiplicity of an eigenvalue λl, 0 ≤l≤dwas defined in [21] as mei(λl)≡mi(λl) = kzilk2.(10) For example, the ei-local multiplicity of λis mi(λ) = ν2 i kνk2>0. Notice that the local multiplicity mi(λl) corresponds in fact to cos2βil, where βil is the angle between eiand 4 the eigenspace Ker(x−λl). The cosines cos βil, 1 ≤i≤n, 0 ≤l≤d, were formally introduced by Cvetkovi´c as the ‘angles’ of Γ (see, for instance, [9, 10].) Let λ>λi1>··· > λimbe those eigenvalues of Γ having nonnull ei-local multiplicities (note that mi(λl) = 0 iff zil =0.) Denoting them by µ0(= λ)> µ1>··· > µm, we can define the (ei-)local spectrum of Γ as Si(Γ) = {λmi(λ), µmi(µ1) 1, . . . , µmi(µm) m} and so they will be referred to as the (ei)-local eigenvalues of Γ. As was discussed in [21], when Γ is ‘seen’ from a given vertex, its local spectrum plays a similar role as the (‘global’) spectrum. In the following proposition we survey some of the results supporting this claim. Proposition 1.1 Let Γbe a graph on nvertices. Let ei∈Vbe a generic vertex with local eigenvalues µ0> µ1>··· > µm, and let pdenote a polynomial. Then, (a) (p(A))ii =Pm l=0 mi(µl)p(µl); (b) Pm l=0 µlmi(µl) = 0, and the degree of vertex eiis δ(ei) = Pm l=0 µ2 lmi(µl); (c) The ei-local multiplicities of all the eigenvalues add up to 1: Pm l=0 mi(µl) = 1 (1 ≤ i≤n); (d) The multiplicity of an eigenvalue of Γis the sum, extended to all vertices, of its local multiplicities: m(λl) = Pn i=1 mi(λl) (0 ≤l≤d); (e) The eccentricity of vertex eisatisfies εi≤m.2 In [20] Yebra and the authors introduced the following polynomial which, for nonregular graphs, plays a similar role as the well-known Hoffman polynomial [25]. H=kνk2 π0 d Y l=1 (x−λl),with π0= d Y l=1 (λ−λl).(11) Notice that H(λ) = kνk2and H(λl) = 0, 1 ≤l≤d. Moreover, it was proved that His the unique polynomial of degree ≤dsatisfying H(A)ij =νiνj, 1 ≤i, j ≤n. Notice that, when Γ is regular, ν=jgives H(A) = J, so that His the Hoffman polynomial. 2 Diameters of a graph and its eigenvalues In this section we present some results bounding the diameter of a graph in terms of its eigenvalues, and some additional information about its structure. The results improve those of Quenell [29], and they are based on a theorem concerning the so-called (s, t)- diameter, which is a generalization of the standard diameter. Other recent generalizations of such a concept are also investigated. 5 2.1 The (s, t)-diameter The distance between two subsets of vertices U1, U2⊂V, denoted by ∂(U1, U2), is defined as ∂(U1, U2) = min{∂(ei, ej) : ei∈U1, ej∈U2}.For some given integers 1 ≤s, t ≤n, the (s,t)-diameter D(s,t), used in [2, 19], measures the maximum distance between two subsets of sand tvertices, that is, D(s,t)= max V1,V2⊂V{∂(V1, V2) : |V1|=s, |V2|=t}. Thus, D(1,1) coincides with the standard diameter D. In [19] the authors proved the following result concerning the (s, t)-diameter: Theorem 2.1 Let Γ=(V, E)be a graph with eigenvalues λ>λ1>··· > λd, and let Pkdenote the k-alternating polynomial on the mesh {λ1, . . . , λd}. Let νbe the positive eigenvector associated to λ. Then, Pk(λ)>skνk2 s−1kνk2 t−1⇒D(s,t)(Γ) ≤k. 2(12) In the case of regular graphs, the above result was also implicitly proved by Van Dam and Haemers in [13] (using a generic polynomial and without mention to the conditional diameters.) For regular graphs also, and using the Chebychev polynomials Tk, Kahale [26] managed to prove that D(s,t)≤$cosh−1p(ns−1−1)(nt−1−1) cosh−1(λ0/λ∗)%+ 1.(13) Since kTkk∞= 1 in [−1,1], we have that Pk(x)≥Tk(x/λ1) for any x≥λ∗. Hence, a result like (13) for general graphs, with kνk2instead of n, can be obtained by substituting Tk(λ/λ∗) for Pk(λ) in (12). Moreover, the use of the polynomial Tk(x) ‘shifted’ to the interval [λd, λ1], that is Tk((2x−λ1−λd)/(λ1−λd)), gives the further improvement D(s,t)≤      cosh−1rkνk2 s−1kνk2 t−1 cosh−12λ0−λ1−λd λ1−λd      + 1.(14) Similar results (for general graphs) using the Laplacian matrix has been independently obtained in [19, 11, 12] (with the alternating polynomials), and in [6, 8] (with the shifted Chebychev polynomials.) In the above-mentioned paper [19], the authors showed that Theorem 2.1 has some applications to the study of other parameters, such as the (vertex-)connectivity of Γ. Following this work, we next derive two new applications bounding the k-independence number and the (standard) diameter of Γ. 6 2.2 The k-independence number For a graph Γ with diameter D, the k-independence number αk, 0 ≤k≤D−1, is defined as the maximum number of vertices which are mutually at distance greater than k. Thus, trivially α0=n, and α1≡αis the standard independence or stability number. Notice also that αkis, in fact, the independence number of the k-th power of Γ. Proposition 2.2 Let Γbe a graph as above. Then, for any 0≤k≤D−1, its kindependence number satisfies αk<2kνk2 Pk(λ)+1+ 1.(15) Proof. The proof is based on the fact that the bound in Theorem 2.1, under the conditions s+t=αkand s, t ≥1, attains its minimum at s=t. Assume first that αkis even. Then, taking s=t=αk 2, we clearly have D(s,t)(Γ) > k. Consequently, Theorem 2.1 gives Pk(λ)≤2kνk2 αk−1, and so αk≤2kνk2 Pk(λ)+1.(16) Otherwise, if αkis odd, we can take s=αk+1 2and t=αk−1 2to get P2 k(λ)≤ 2kνk2 αk+ 1 −1! 2kνk2 αk−1−1! which, solving for αk, gives αk≤−2kνk2+q(P2 k(λ)−1)2+ 4kνk4P2 k(λ) P2 k(λ)−1<2kνk2 Pk(λ)+1+ 1,(17) where the second inequality has been deduced by adding 2(2kνk2Pk(λ))(P2 k(λ)−1) to the term inside the root. 2 In fact, a more detailed study of the odd case allow us to conclude that αk<2kνk2 Pk(λ)+1+√5−2,(18) see [22]. Notice that, when 2kνk2 Pk(λ)+1 is an integer, we have (16). For instance, if Γ is a k-‘boundary graph’ as defined in [20], that is Pk(λ) = kνk2−1, the above result gives αk≤2. Hence, if D(Γ) = k+ 1 the obtained bound is tight. Another example is when we consider an r-antipodal distance-regular graph Γ (see, for instance, Biggs [3]), characterized by the fact that, given any vertex ei∈V, the set {ei}∪ΓD(ei) (with ΓD(ei) defined below) has rvertices which are mutually at distance D(= d.) In [20], the authors showed that the (d−1)-alternating polynomial of a such graph with nvertices satisfies Pd−1(λ) = 2 rn−1. Hence, (16) gives again the sharp bound αd−1≤r. 7 2.3 The diameter Given ei∈Vand any integer ρ, 0 ≤ρ≤D, let Γρ(ei) denote the set of vertices which are at distance ρfrom ei. For any integer 0 ≤τ≤D, let us define the τ-superdegree of a vertex eias δ∗ τ(ei) = |{ej:∂(ei, ej)≤τ}| =|∪τ ρ=0 Γρ(ei)|. Thus, δ∗ 0(ei) = 1, δ∗ 1(ei) = 1 + δ(ei) and δ∗ D(ei) = n. The minimum τ-superdegree is then defined as δ∗ τ= min{δ∗ τ(ei) : ei∈V}. Notice that, if Γ has minimum degree δand girth g, then δ∗ `≥1 + δ+δ(δ−1) + ···+δ(δ−1)`−1≡n(δ, `), that is the ‘Moore bound’ for a δ-regular graph with diameter `=bg−1 2c, or odd girth 2`+ 1, see Biggs [3]. The following consequence of Theorem 2.1 takes into consideration the minimum τsuperdegree. Proposition 2.3 Let Γbe a graph as above. Then, Pk(λ)>skνk2 δ∗ σ−1kνk2 δ∗ τ−1⇒D(Γ) ≤k+σ+τ. (19) Proof. Let ei, ejbe two generic vertices. Then, since | ∪σ ρ=0 Γρ(ei)| ≥ δ∗ σand | ∪τ ρ=0 Γρ(ej)| ≥ δ∗ τ, we can always consider two subsets, Sand T, of s=δ∗ σand t=δ∗ τvertices respectively, such that ∂(ei, ej)≤σ+∂(S, T) + τ≤σ+D(s,t)+τ. Hence, D(Γ) ≡D(1,1) ≤σ+D(s,t)+τ, and the result follows from Theorem 2.1. 2 In particular, if Γ has minimum degree δand girth gwe can take σ=τ=`, thus obtaining the following implication: Pk(λ)>kνk2 n(δ, `)−1⇒D(Γ) ≤k+ 2`. (20) This result improves, and generalizes for non-regular graphs, the result (6) of Quenell [29]. Moreover, it seems that the result in (20) is stronger as the value of `increases. For example, the ‘twisted odd graph’ Γ = O(12) 4, see [20], is a 4-regular graph on n= 35 vertices, with girth 5, and eigenvalues λ= 4, λ1= 3, λ2= 2, λ3= 1, λ4=−1, λ5=−2, λ6=−3. Then, the corresponding k-alternating polynomials have the following values at λ P5(4) = 34, P4(4) = 15, P3(4) = 6, P2(4) = 11 4, P1(4) = 4 3. 8 Hence, since P5(4) = n−1 (regular boundary graph [20]) we can not infer that D(Γ) ≤5. Similarly, since n(4,1) = 5, we get P3(4) = n n(4,1) −1, and (20) neither allows us to conclude that D(Γ) ≤5. However, as `= 2 and n(4,2) = 17, we have P1(4) >n n(4,2) −1, and (20) gives D(Γ) ≤5. (In fact, D(Γ) = 4.) 2.4 The (s1, . . . , sr)-diameter A natural generalization of the (s, t)-diameter is obtained when we take into consideration some, say r≥2, vertex subsets of given cardinalities. Thus, for some integers s1, s2, . . . , sr, 1≤si≤n, the (s1, s2, . . . , sr)-diameter is defined as D(s1,s2,...,sr)= max U1,...,Ur⊂V{min 1≤i<j≤r∂(Ui, Uj) : |Ui|=si,1≤i≤r}.(21) In particular, if all the subsets have the same size, say s, we simply write Dr×sinstead of D(s,s,...,s). Notice that, if s=s1+···+siand t=si+1 +···+srfor some 1 ≤i≤r−1, then D(s1,s2,...,sr)≤D(s,t), so that Theorem 2.1 gives Pk(λ)>kνk2 s−1⇒D2s×1≤k. (22) More generally, it was shown in [17], by using a different approach, that Pk(λ)>2kνk2 r−1⇒Dr×1≤k(23) for any integer r≥2. In [26], Kahale proved that if Γ is a regular graph on nvertices, and ϑ0(= λ0), ϑ1(= λ∗), ϑ2, . . . , ϑn−1represent its eigenvalues (including multiplicities) with absolute value in nonincreasing order, |ϑ0|>|ϑ1| ≥ ··· ≥ |ϑn−1|, then Dr×s≤&cosh−1n s−1 cosh−1(ϑ0/ϑr−1)'+ 1.(24) In [8], Chung, Delorme, and Sol´e prove, by using again the (normalized) Laplacian matrix (the ‘Laplace operator’ ) and the Chebychev polynomials, a result for general graphs, whose counterpart for the adjacency matrix is: D(s1,s2,...,sr)≤max 1≤i<j≤r      cosh−1rkνk2 si−1kνk2 sj−1 cosh−12θ0−θr−1−θn−1 θr−1−θn−1      + 1,(25) where θ0(= λ0)> θ1≥ ··· ≥ θn−1are the neigenvalues of A(see also Chung, Grigor’yan, and Yau [7].) The proof is based in a geometric lemma given in [6] stating that, for any r≥2 arbitrary vectors of a (r−2)-dimensional Euclidean space, at least two of them have 9 under the condition kpk2 A= k X τ=0 kaτpτk2 A= k X τ=0 a2 τkτ= 1, gives aτ= 1/pqk(λ), 0 ≤τ≤k.2 Moreover, in [21] it was shown that the polynomials qk=Pd τ=0 pτ, (0 ≤k≤d) of Proposition 3.6 form an orthogonal system with respect to the scalar product hf, gi∗= d X l=1 (λ0−λl)m(λl) nf(λl)g(λl) = λ0hf, giA−hxf, giA.(35) Hence, the same properties are shared by the k-adjacency polynomials Qkof a d0-partially walk-regular graph Γ (assuming that k≤ bd0 2cif d0< d.) The following result, to be compared with (8), is a consequence of Corollary 3.2 and the above proposition. Corollary 3.7 Let Γbe a d0-partially walk-regular graph as above. Then, qk(λ)> n −1⇒D(Γ) ≤k. 2 Example 3.8 Let Odenote the graph of the octahedron. Then the graph Γ = L2O(that is, the line graph of the line graph of O) is a vertex symmetric graph with spectrum S(Γ) = {101,63,42,26,−224}Then, its corresponding polynomials qk=pqk(λ)Qk,0≤k≤4, and their values at λ= 10 are: •q0= 1, 1; •q1=x+ 1, 11; •q2=1005 2426 x2−142 67 x−7624 1005 , 29.50. . . ; •q3=5907 65104 x3−11820 1969 x2−6100 1969 x+50640 1969 , 35.78. . . ; •q4=1 64 x4−10x3+ 20x2+ 40x−96, 36; Therefore, since q3(λ)> n −1, Corollary 3.7 gives D(Γ) ≤3, which is the exact value of the diameter. Note also that, according to previous comments, q4is, in fact, the Hoffman polynomial H. 16 3.2 Partially distance-regular graphs An example of partially walk-regular graphs are those graphs having a ‘partial distanceregularity’ around every of their vertices. More precisely, let Γ be a regular graph with adjacency matrix Aand diameter D, and let D0≤Dbe the maximum integer such that, for any 0 ≤τ≤D0there exist a polynomial vτof degree τsuch that vτ(A) is the so-called τ-distance matrix, defined by (vτ(A))ij =(1 if ∂(ei, ej) = τ, 0 otherwise. Then it is said that Γ is a D0-partially distance-regular graph. For instance, note that every regular graph is 1-partially distance-regular, since two obvious examples of τ-distance matrices are I(v0= 1) and Aitself (v1=x.) In fact, if Γ has girth g, simple reasoning shows that D0≥ b(g−1)/2c, with v0= 1, v1=x,v2=x2−δ, and vτ=xvτ−1−(δ−1)vτ−2 (3 ≤τ≤D0), see Biggs [3]. The distance polynomials vτ, 0 ≤τ≤D0, of a D0-partially distance-regular graph, are orthogonal with respect to the scalar product hf, giAdefined above since, for σ6=τ, 0 = tr (vσ(A)vτ(A)) = d X l=0 m(λl)vσ(λl)vτ(λl) = nhvσ, vτiA. Furthermore, for σ=τwe get kvτk2 A=hvτ, vτiA=1 ntr (v2 τ(A)) = 1 n n X i=1 |Γτ(ei)|, but the number of vertices at distance τfrom eidoes not depend on isince |Γτ(ei)|= hvτei,ji=hei, vτji=h1 nj+zi, vτ(λ)ji=vτ(λ). Hence kvτk2 A=vτ(λ)≡kτ, and {vτ}is the sequence of polynomials satisfying the hypotheses of Proposition 3.6. In fact any D0-partially distance-regular graph is also 2D0-partially walk-regular since, for any k=s+t≤2D0,s≤t≤D0, we have: (Ak)ii =hxkei,eii=hxsei, xteii=h s X σ=0 aσvσei, t X τ=0 bτvτeii= s X σ=0 aσbσkvσeik2 where aσand bσare the Fourier coefficients of xsand xtwith respect to the basis {vτ}, respectively (and so they do not depend on i) and, from the above, kvσeik2=kvσk2 A=kσ. Thus, a more explicit formula for (Ak)ii is: (Ak)ii = s X σ=0 hxs, vσiA kvσk2 A hxt, vσiA kvσk2 A kσ= s X σ=0 hxk, vσiA kvσk2 A =1 n s X σ=0 d X l=0 m(λl)λk l vσ(λl) kσ . 17 Corollary 3.9 Let Γbe a D0-partially distance-regular graph. Then, the k-adjacency polynomial is Qk=wk pwk(λ)(0 ≤k≤D0) where wk=Pk τ=0 vτ.2 4 The diameter of a graph and its spectrum Here we present a unified approach to the previous results, by considering both the alternating and the adjacency polynomials. Theorem 4.1 Let Γ=(V, E)be a graph with adjacency matrix A, and eigenvalues λ > λ1>··· > λd. Let νbe the positive eigenvector associated to λ. Let Pkdenote the k-alternating polynomial on the mesh {λ1, . . . , λd}. Let Qσand Qτbe the corresponding adjacency polynomials of Γ. Then, Pk(λ)>skνk2 Q2 σ(λ)−1kνk2 Q2 τ(λ)−1⇒D(Γ) ≤k+σ+τ. (36) Proof. Let Abe the adjacency matrix of Γ. Let eibe the ith coordinate vector. Then, using again decomposition (9), kQσeik2=    Qσνi kνk2ν+zi    2 =ν2 i kνk2Q2 σ(λ) + kQσzik2 Thus, we get (PkQσQτ(A))ij =hPkQσei, Qτeji =PkQσνi kνk2ν+zi, Qτνj kνk2ν+zj =Pk(λ)νiνj kνk2Qσ(λ)Qτ(λ) + hPkQσzi, Qτzji ≥Pk(λ)Qσ(λ)Qτ(λ) kνk2+hPkQσzi, Qτzji. Moreover, since kQσeik≤kQσkA= 1 and νi≥1, we have kQσzik2≤1−Q2 σ(λ) kνk2, and hence |hPkQσzi, Qτzji| ≤ kPkQσzikkQτzjk ≤ kPkk∞kQσzikkQτzjk ≤s1−Q2 σ(λ) kνk21−Q2 τ(λ) kνk2 ≤Qσ(λ)Qτ(λ) kνk2skνk2 Q2 σ(λ)−1kνk2 Q2 τ(λ)−1 18 since kPk(A)|ν⊥k=kPkk∞= 1. Therefore, (PkQσQτ(A))ij ≥Qσ(λ)Qτ(λ) kνk2 Pk(λ)−skνk2 Q2 σ(λ)−1kνk2 Q2 τ(λ)−1!>0 so that ∂(ei, ej)≤k+σ+τ, and hence D(Γ) ≤k+σ+τas claimed. 2 In particular, for σ=τ, we get Pk(λ)>kνk2 Q2 τ(λ)−1⇒D(Γ) ≤k+ 2τ. (37) As, for any graph, the 1-adjacency polynomial is given by (34), we have Q2 1(λ) = ∆+λ2 ∆, and hence: Corollary 4.2 Let Γbe a graph as above. Then, Pk(λ)>kνk2 1+(λ2/∆) −1⇒D(Γ) ≤k+ 2.2(38) In particular, taking k= 0 (P0= 1), we obtain the following condition for Γ to have diameter at most two: λ > s∆kνk2 2−1⇒D(Γ) ≤2 (39) which, for δ-regular graphs, reads λ=δ≥ bn/2c⇒D(Γ) ≤2 (trivial.) Another consequence of Theorem 4.1, corresponding to Corollary 3.2(b), is obtained when we take k=τ= 0 (P0=Q0= 1): Corollary 4.3 Let Γbe a graph as above. Then, Qσ(λ)>qkνk2−1⇒D(Γ) ≤σ. 2(40) The similarity between the results (7) and (40) deserves a comparative study. With this aim, note first that the value of Pk(λ) is obtained using only the eigenvalues of the graph. Thus, intuitively speaking, the successive steps A→S(Γ) → {λ>λ1>··· > λd} → Pk(λ) progressively weaken the precision that a result about some property of Γ, deduced from some condition on Pk(λ), can have. Consequently, it seems that the corresponding condition on the value Qk(λ), obtained from the whole spectrum of Γ, should lead to a stronger result. The following proposition shows that, at least for regular graphs, this is the case for (7) and (40). 19 Proposition 4.4 Let Γbe a regular graph on nvertices, with eigenvalues λ>λ1>··· > λd. Then, for any 1≤k≤d, Pk(λ)> n −1⇒Q2 k(λ)> n −1. Proof. Let eibe a vertex such that kPkeik=kPkkA= max1≤j≤n{kPkejk}. Since kPkeik2=P2 k(λ) n+kPkzik2≤P2 k(λ) n+ 1 −1 n, the vector √n qP2 k(λ) + n−1 Pkei has norm ≤1. Hence, from the choice of eiand the definition of Qk, Qk(λ)≥√nPk(λ) qP2 k(λ) + n−1 and so, using the hypothesis, Q2 k(λ)≥nP2 k(λ) P2 k(λ) + n−1=n−n2−n P2 k(λ) + n−1> n −1.2 To show that the converse of the above result does not hold, we can consider again the graph Γ = L2Oin the example of Section 3. Indeed, we already saw that such a graph has Q2 3(λ) = q3(10) = 35.78 . . . > n −1 = 35, whereas its 3-alternating polynomial is P3=3 32 x3−5 8x2+1 8x+5 2, which gives P3(10) = 35 (L2Ois a boundary graph.) Going back to the consequences of Theorem 4.1, we can use Corollary 3.9 to derive a result for D0-partially walk-regular graphs. Corollary 4.5 Let Γbe a D0-partially distance-regular graph on nvertices. Then, for any 0≤σ, τ ≤D0, Pk(λ)>sn qσ(λ)−1 n qτ(λ)−1⇒D(Γ) ≤k+σ+τ. 2(41) In particular, if Γ has girth gand σ=τ=`, we have q`(λ) = n(δ, `) and the above corollary gives (20). 20 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] C. Balbuena, A. Carmona, J. F`abrega, and M.A. Fiol, On the connectivity and the conditional diameter of graphs and digraphs, Networks 28 (1996) 97–105. [3] N. Biggs, Algebraic Graph Theory (Cambridge University Press, Cambridge, 1993). [4] F.R.K. Chung, Diameter and eigenvalues, J. Am. Math. Soc. 2 (1989) 187-196. [5] 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 (1994) 443–457. [6] F.R.K. Chung, A. Grigor’yan, and S.-T. Yau, Upper bounds for eigenvalues of the discrete and continuous Laplace operators, Advances in Math. 117 (1996) 165–178. [7] F.R.K. Chung, A. Grigor’yan, and S.-T. Yau, Eigenvalues and diameters for manifolds and graphs, submitted. [8] F.R.K. Chung, C. Delorme, and P. Sol´e, k-Diameter and spectral multiplicity, submitted. [9] D. Cvetkovi´c and M. Doob, Developments in the theory of graph spectra, Linear and Multilinear Algebra 18 (1985) 153–181. [10] D. Cvetkovi´c, P. Rowlinson, and S. Simi´c, Eigenspaces of Graphs (Cambridge University Press, Cambridge, 1997). [11] E.R. van Dam, Graphs with few eigenvalues, Ph.D. Thesis, Tilburg University, LE Tilburg (1996). [12] E.R. van Dam, Bounds on special subsets in graphs, eigenvalues and association schemes, J. Algebraic Combin., to appear. [13] E.R. van Dam and W.H. Haemers, Eigenvalues and the diameter of graphs, Linear and Multilinear Algebra 39 (1995) 33–44. [14] C. Delorme and P. Sol´e, Diameter, covering index, covering radius and eigenvalues, European J. Combin. 12 (1991) 95–108. [15] C. Delorme and J.P. Tillich, Eigenvalues, eigenspaces and distances to subsets, Discrete Math. 165–166 (1997) 161–184. [16] J. F`abrega and M.A. Fiol, Maximally connected digraphs, J. Graph Theory 13 (1989) 657–668. 21 [17] M.A. Fiol, An eigenvalue characterization of antipodal distance-regular graphs, Electron. J. Combin. 4 (1997), no. 1, #R30. [18] M.A. Fiol, E. Garriga, and J.L.A. Yebra, On a class of polynomials and its relation with the spectra and diameter of graphs, J. Combin. Theory Ser B. 67 (1996) 48–61. [19] 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. [20] M.A. Fiol, E. Garriga, and J.L.A. Yebra, Boundary graphs: The limit case of a spectral property (II), Discrete Math. 182 (1998) 101–111. [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] E. Garriga, Contribuci´o a la teoria espectral de grafs: Problemes m`etrics i distanciaregularitat, Ph.D. Thesis, Universitat Polit`ecnica de Catalunya, Barcelona (1997). [23] C.D. Godsil, Algebraic Combinatorics (Chapman and Hall, New York, 1993). [24] C.D. Godsil and B.D. McKay, Feasibility conditions for the existence of walk-regular graphs, Linear Algebra Appl. 30 (1980) 51–61. [25] A.J. Hoffman, On the polynomial of a graph, Amer. Math. Monthly 70 (1963) 30–36. [26] N. Kahale, Isoperimetric inequalities and eigenvalues, SIAM J. Discrete Math. 10 (1997) 30–40. [27] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan Graphs, Combinatorica 8 (1988) 261–277. [28] B. Mohar, Eigenvalues, diameter and mean distance in graphs, Graphs Combin. 7 (1991) 53-64. [29] G. Quenell, Spectral diameter estimates for k-regular graphs, Adv. Math. 106 (1994) 122–148. [30] J.A. Rodr´ıguez, Cotas de diversos par´ametros de un grafo a partir de los autovalores de su matriz laplaciana, Ph.D. Thesis, Universitat Polit`ecnica de Catalunya, Barcelona (1997). [31] P.C. Sarnak, Some Applications of Modular Forms (Cambridge Univ. Press, Cambridge, 1990). 22