An eigenvalue characterization of antipodal distance-regular graphs
Abstract
Let $\Gamma$ be a regular (connected) graph with $n$ vertices and $d+1$ distinct eigenvalues. As a main result, it is shown that $\Gamma$ is an $r$-antipodal distance-regular graph if and only if the distance graph $\Gamma_d$ is constituted by disjoint coies of the complete graph $K_r$, with $r$ satisfying an expression in terms of $n$ and the distinct eigenvalues.
Full text
An Eigenvalue Characterization of Antipodal Distance-Regular Graphs 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: July 19, 1997; Accepted: November 14, 1997. Abstract Let Γ be a regular (connected) graph with nvertices and d+ 1 distinct eigenvalues. As a main result, it is shown that Γ is an r-antipodal distanceregular graph if and only if the distance graph Γdis constituted by disjoint copies of the complete graph Kr, with rsatisfying an expression in terms of n and the distinct eigenvalues. AMS subject classifications. 05C50 05E30 1 Introduction The core of spectral graph theory is to describe the properties of a graph by its spectrum and find conditions that cospectral graphs may not share. For instance, consider the following question: Can we see from the spectrum of a graph with diameter D, say, whether it is distance-regular? Since a long time it was known that the answer to this question is ‘yes’ when D≤2 and ‘not’ if D≥4. Then, on the basis of these results, it had been conjectured (cf. Cvetkovi´c, Doob, and H. Sachs [5] ) that the answer is also ‘yes’ for D= 3, but recently Haemers [19] disproved the conjecture constructing some counterexamples. So, in general the spectrum is not sufficient to assure distance-regularity and, if we want to go further, we must require the graph to satisfy some additional conditions. In this direction, Van Dam and Haemers [8] showed that, in the case D= 3, such a condition could be the number ndof vertices
the electronic journal of combinatorics 4 (1997), #R30 2 at “extremal distance” D=d(where d+ 1 is the number of distinct eigenvalues) from each vertex. Independently, Garriga, Yebra and the author [13] settled the case nd= 1 (for any value of D), that is the case of 2-antipodal distance-regular graphs. Finally, Garriga and the author [11] solved the general case, characterizing distance-regular graphs as those regular graphs whose number of vertices at distance dfrom each vertex is what it should be (a number that depends only on the spectrum of the graph.) An striking peculiarity of the case nd= 1 (2-antipodal graphs) is that, in fact, we do not need to look at the whole spectrum, but only at the distinct eigenvalues (its multiplicities can be deduced from them.) The main contribution of this paper is to show that this is also true for r-antipodal distance-regular graphs. As a main result it is shown that an antipodal regular graph is distance-regular if, and only if, its ‘fibres’ (that is, the sets of antipodal vertices) have all cardinality r, a number depending on the order and the eigenvalues of the graph. This result is obtained via an spectral bound for the k-independence number, or (standard) independence number of the k-th power of the graph, and the study of the limit case in which such a bound is attained. Let us now fix the terminology and notation used throughout the paper. Thus, Γ=(V,E) denotes a connected (simple and finite) graph with order n:= |V|and adjacency matrix A=A(Γ). The distance between two vertices u, v ∈Vis represented by dist(u, v). The eccentricity of a vertex uis ecc(u):=max v∈Vdist(u, v), and the diameter ofΓisD:= maxu∈Vecc(u). As usual, Γk(u), 0 ≤k≤ecc(u), denotes the set of vertices at distance kfrom u, and Γ1(u) is simply written as Γ(u). The distance-kgraph Γk,0≤k≤D, is the (possibly non-connected) graph on Vwhere two vertices are adjacent whenever they are at distance kin Γ. Thus, in particular, Γ0 is the trivial graph on nvertices, and Γ1= Γ. The adjacency matrix of Γk, denoted by Ak, is usually referred as the distance-kmatrix of Γ. A graph Γ of diameter D is called antipodal if, for any given vertex u∈V, the set {u}∪Γ D (u) consists of vertices which are mutually at distance D. In other words, there exists a partition of the vertex set into classes (called the fibres of Γ) with the property that two distinct vertices are in the same class iff they are at distance D(see, for instance, Godsil [17] .) If all the fibres have the same cardinality, say r,wesaythatΓisanr-antipodal graph. We index all the involved matrices and vectors by the vertices of Γ. Moreover, for any vertex u∈V, we denote by euthe u-th unitary vector of the canonical basis of Rn. Thus, the characteristic vector of a vertex set U⊂Vis just eU:= Pu∈Ueu. As usual, the adjacency matrix Aof Γ is seen as an endomorphism of Rn. We let a polynomial p∈Rk[x] operate on Rnby the rule pw:= p(A)w, where w∈Rn, and
the electronic journal of combinatorics 4 (1997), #R30 3 the matrix is not specified unless some confusion may arise. 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: sp Γ := {λm0 0,λ m 1 1,...,λ m d d} where the superscripts denote multiplicities. Recall that the largest positive eigenvalue λ0(with multiplicity one if Γ is connected) has an eigenvector ν=(ν 1 ,ν 2,...,ν n) >, which can be taken with all its entries positive, and we will consider it normalized in such a way that its smallest entry is 1. Thus, ν=jwhen Γ is regular. In some of our results we do not use the whole spectrum, but only the mesh (set) constituted by all the distinct eigenvalues, that is ev Γ := {λ0,λ 1,...,λ d} in decreasing order: λ0>λ 1>··· >λ d . (We follow here the notation of Godsil [17] .) Associated to such a mesh, we make ample use of the moment-like positive numbers πi, which are defined as πi= d Y j=0,j6=i |λi−λj|(0 ≤i≤d).(1) As it is well-known, if Γ is connected, its diameter is at most d=|ev Γ|−1 (see, for instance, Biggs [2] .) Then, we say that Γ is extremal when it has “spectrally maximum” diameter D=d. We also say that Γ is diametral when all its vertices have eccentricity equal to the diameter. In order to obtain bounds on the diameter of a graph in terms of its eigenvalues, Garriga, Yebra and the author [12] used the so-called alternating polynomial Pk, 0≤k≤d−1, which is the (unique) polynomial satisfying Pk(λ0) = max p∈Rk[x]{p(λ0): kpk ∞≤1} where kpk∞= max1≤i≤d|p(λi)|. When k=d−1, we simply speak about the alternating polynomial,P:= Pd−1.In[12] it was proved that the k-alternating polynomial is characterized by taking k+ 1 alternating values ±1 at ev Γ, with Pk(λ1)=1 and Pk(λd)=(−1)k. In particular, for k=d−1, this characterization gives P(λi)=(−1)i+1,1≤i≤d, which together with Lagrange interpolation yields P(λ0)= d X i=1 π0 πi P(λ0)= d X i=1 π0 πi .(2)
the electronic journal of combinatorics 4 (1997), #R30 4 Some particular cases of these polynomials were also considered by Van Dam and Haemers in [7] . We finally recall that the Kronecker product of two matrices A=(a ij) and B, denoted by A⊗B, is obtained by replacing each entry aij with the matrix aijB, for all iand j. Then, if uand vare eigenvectors of Aand B, with corresponding eigenvalues λand µ, respectively, then u⊗v(seeing uand vas matrices) is an eigenvector of A⊗B, with eigenvalue λµ. 2 The k-independence number Let Γ = (V,E) be a graph with diameter D. A vertex set U⊂Vis said to be kindependent, for some integer k≥0, if their vertices are mutually at distance greater than k. By convention, U={u}will be supposed to be k-independent for every k. The k-independence number αkof Γ is then defined as the cardinality of a maximum k-independent set. Thus, trivially, α0=nand αk=1ifk≥D. Moreover, α1≡α is the standard independence or stability number. Notice also that αkis, in fact, the independence number of the k-thpowerofΓ. In[10] , Garriga and the author showed that, when 0 ≤k≤d−1, the k-independence number of a regular graph satisfies the following spectral upperbound αk<2n Pk(λ0)+1+1. where Pkis the k-alternating polynomial of Γ. This was derived as a consequence of a result on the (s, t)-diameter, which is the maximum distance between two subsets of sant tvertices. Here we begin with a result which slightly improves this bound and, more important, tell us what happens when the bound is attained. Although both bounds are very similar, the method used here is quite different from that used in [10] . Roughly speaking, we must now use a more precise technique, which, rather than the distance between two subsets, should take into account all the distances between vertices of a unique subset. As noted by the referee, the improved bound can also be derived by using ‘eigenvalue interlacing’ (see Haemers’ survey [18] on this versatile technique.) More details about this approach can be found in [9] . Theorem 2.1 Let Γbe a connected regular graph with nvertices, mesh of eigenvalues ev Γ = {λ0,λ 1,...,λ d}, and k-alternating polynomial Pk. Then, for any 0≤k≤ d−1, its k-independence number satisfies αk≤2n Pk(λ0)+1.(3)
the electronic journal of combinatorics 4 (1997), #R30 5 If equality holds for some (maximum) k-independent set U, then there exists a polynomial p∈Rd[x](independent of U) such that peu=eU\{u}peu=eU\{u}.(4) for every vertex u∈U. P roof. Let U={u0,u 1,...,u r−1}be a maximum k-independent set, where r=|U|=αk. From the k-alternating polynomial Pkof Γ, we consider the polynomial Qk:= r 2Pk+r 2−1. Then, since Pk(λ0)≥1 and −1≤Pk(λi)≤1 for i6= 0, the matrix Qk(A) has eigenvalues Qk(λ0)≥r−1 and Qk(λi) satisfying −1≤Qk(λi)≤r−1 for 1≤i≤d. Now consider the matrix B:= A(Kr)⊗Qk(A). For instance, for r=3 we have B= OQk(A)Qk(A) Qk(A)OQk(A) Qk(A)Qk(A)O . The complete graph Krhas eigenvalues r−1 and −1 (with multiplicity r−1), with corresponding orthogonal eigenvectors j∈Rrand φi=(1,ωi,ω2i,...,ω(r−1)i)>, 1≤i≤r−1, where ωis a primitive r-th root of 1, say ω:= ej2π r. Consequently, each eigenvector uof Qk(A) with eigenvalue Qk(λ), λ∈ev Γ, gives rise to the eigenvalues (r−1)Qk(λ) and −Qk(λ) (with multiplicity r−1), with corresponding orthogonal eigenvectors u0:= j⊗uand ui:= φi⊗u,1≤i≤r−1. Thus, when λ6=λ0, we have −1≤Qk(λ)≤r−1 and hence the corresponding eigenvalues of B are within the interval [−(r−1),(r−1)2]. Moreover, Bhas maximum eigenvalue (r−1)Qk(λ0)≥(r−1)2. Now take the vector fU:= (e> u0|e> u1|···|e > u r−1) >∈R rn, and consider its spectral decomposition: fU= r−1 X i=0 hfU,jii kjik2ji+zU=1 nj0+zU(5) where zU∈hj 0 ,j 1 ,...,jr−1i ⊥, and we have used that hfU,j0i=r,kjik2=rn, and hfU,jii=Pr−1 j=0 ωij = 0, for any 1 ≤i≤r−1. From (5), we get kzUk2=kfUk2−1 n2kj0k2=r1−1 n. Since there is no path of length ≤kbetween any pair of vertices of U,(Q k (A))uiuj= 0 for any i6=j. Thus, 0=hBfU,fUi=*(r−1)Qk(λ0) nj0+BzU,1 nj0+zU+
the electronic journal of combinatorics 4 (1997), #R30 6 =r(r−1)Qk(λ0) n+hBzU,zUi ≥r(r−1)Qk(λ0) n−(r−1)kzUk2=r(r−1) n(Qk(λ0)−n+1). Therefore, we get Qk(λ0)=α k 2P k (λ 0 )+α k 2−1≤n−1 and (3) follows. From the above, notice that equality holds iff BzU=−(r−1)zU.(6) By (5), we infer that, if eui=1 nj+zi,zi∈j⊥, represents the spectral decomposition of euiin Rn∼ =Ld j=0 Ker(A−λjI), 0 ≤i≤r−1, then zU=(z > 0|z > 1|···|z> r−1) >. Hence, (6) gives the rvectorial equations: r−1 X i=0,i6=j Qkzi=−(r−1)zj(0 ≤j≤r−1) which are equivalent to Qkzi=(r−2)zi− r−1 X j=0,j6=i Qkzi=(r−2)zi− r−1 X j=0,j6=i zj(0 ≤i≤r−1).(7) Let Hbe the Hoffman polynomial defined by its values at ev Γ, namely H(λ0)=n, H(λ i )=0,1≤i≤d, and satisfying H(A)=J(see Hoffman [20] .) Now we claim that the searched polynomial is p=H−Qk+(r−2), whose value at λ0is p(λ0)=n−(n−1)+(r−2) = r−1. Indeed, using (7), we get peui=p1 nj+zi=r−1 nj−Qkzi+(r−2)zi =r−1 nj+ r−1 X j=0,j6=i zj= r−1 X j=0,j6=i euj=eU\{ui}(0 ≤i≤r−1), which concludes the proof of the theorem. 2 For general k, the given bound (3) is sharp. For instance, in [14] it was shown that the alternating polynomial P(k=d−1) of an r-antipodal distance-regular graph on nvertices satisfies P(λ)=2 r n−1, whence we get αd−1≤r. In the next section we prove again, for completeness, such a result on Pby using Theorem 2.1, but first we will pay attention to some other straightforward consequences of the theorem.
the electronic journal of combinatorics 4 (1997), #R30 7 Using the language of Coding Theory, notice that (3) yields a bound for the size of any code Cin Γ with minimum distance δ(that is the minimum distance between two distinct ‘code words’ —vertices of Γ.) Namely, |C|≤ 2n P δ−1 (λ 0 )+1. In the spirit of [21] , where a spectral upper bound is given on the minimum distance between tsubsets of same size, we can consider the t-diameter Dtdefined by Dt:= max U⊂V,|U|=t{min u,v∈Udist(u, v)}, as it was done in [16] ,[4] . The standard diameter is then D=D2. From our theorem we have the following result. Corollary 2.2 Let Γbe a regular graph on nvertices, and with t-diameter Dt. Then, Pk(λ0)>2n tPk(λ0)>2n t−1⇒Dt≤k. (8) P roof. From the hypothesis and Theorem 2.1we get αk<t, which implies the result. 2 By using the positive eigenvector νof the Introduction, similar results can be obtained for non-regular graphs. So, from the vector fU=Pr−1 i=0 1 νui eui, instead of (3)wenowget α k≤2kνk 2 P k (λ 0 )+1 (9) whence Pk(λ0)>2kνk2 tPk(λ0)>2kνk2 t−1⇒Dt≤k. (10) Spectral bounds on the t-diameter, in terms of the i-th largest eigenvalue (in absolute value) of the adjacency and Laplacian matrices can be found in Kahale [21] and Chung, Delorme, and Sol´e [4] , respectively. 3 Antipodal Distance-Regular Graphs In this section we study two spectral characterizations of antipodal distance-regular graphs. The fist one establishes that the distance-regular graphs which are antipodal
the electronic journal of combinatorics 4 (1997), #R30 8 are characterized by their eigenvalue multiplicities. The second characterization was already commented in the Introduction, and states that we can see from the spectrum of a regular graph, and the cardinalities of the “extremal fibres” (the sets of antipodal vertices at extremal distance) whether the graph is an antipodal distance-regular graph. Let us begin by recalling some definitions and known results which are on the basis of our work. 3.1 Distance-regular graphs A (connected) graph Γ with diameter Dis distance-regular if, for any two vertices u and v∈Γk(u), 0 ≤k≤D, the numbers ak(u)=|Γ k (u)∩Γ(v)|,bk(u)=|Γ k+1(u)∩ Γ(v)|, and ck(u)=|Γ k−1 (u)∩Γ(v)|do not depend on uand v, but only on k. Some basic references dealing with this topic are Bannai and Ito [1] , Biggs [2] , and Brouwer, Cohen and Neumaier [3] . A well-known characterization of such graphs is the following: a graph Γ, with adjacency matrix Aand diameter D, is distanceregular if and only if, for any 0 ≤k≤D, its distance-kmatrix Akis a polynomial of degree kin A. Recently, Garriga, Yebra, and the author [14] showed that, if Γ is extremal and diametral, the condition on ADsuffices, as stated in the following theorem. Theorem 3.1 A graph Γwith adjacency matrix Aand diameter Dis distanceregular if and only if Γis extremal, diametral, and its distance-Dmatrix ADis a polynomial of degree Din A.2 From this result, and generalizing some results of Haemers and Van Dam [19] ,[6] ,[8] ] (the case d= 3) , and Garriga, Yebra and the author [13] (the case |Γd(u)|= 1), the following spectral characterization was also obtained in [11] : Theorem 3.2 A regular graph Γon nvertices, with spectrum sp Γ = {λ0,λ m 1 1,···,λ m d d}, is distance-regular if and only if |Γd(u)|=n π2 0Pd i=0 1 miπ2 i (11) for every vertex uof Γ.2 Notice that the cases d=1,2 are trivial, in the sense that every (connected) regular graph Γ with two or three different eigenvalues is distance-regular. More precisely, Γ = Knif d+ 1 = 2, and Γ is strongly regular when d+ 1 = 3. See, for instance, Godsil [17] .
the electronic journal of combinatorics 4 (1997), #R30 9 3.2 Antipodal graphs Let us now turn our attention to the antipodal graphs. In this context, another consequence of Theorem 2.1is the following result, already proved in [15] using a different approach (see also [16] .) Proposition 3.3 Let Γbe an extremal r-antipodal regular graph, with nvertices and diameter D, and let ADbe the adjacency matrix of ΓD.IfA Dbelongs to the algebra generated by A, then AD=J−R(A), where R:= r 2P−r 2+1 and Pis the alternating polynomial of Γ. P roof. The first part of the proof goes as in [15] : We know that sp ΓD= {(r−1)σ,−1n−σ}, where σ=n/r stands for the number of fibres. By the hypothesis, there exists a polynomial p∈Rd[x] such that p(A)=A D , so that p(λ0)=r−1 and p(λi)∈{r−1,−1}for 1 ≤i≤d. Since Γ is regular, the polynomial R:= H−p∈ Rd[x] satisfies R(A)=J−A Dand hence R(λ0)=n−r+1, R(λ i )∈{1,1−r} for 1 ≤i≤d. Moreover, since each entry of R(A) corresponding to a diametral pair of vertices is zero, it must be R∈Rd−1[x]. Let P:= 2 rR+1−2 r. Then, P(λ0)=2n r−1, and P(λi)=±1 for i6= 0. The second part of the proof consists in proving that Pis indeed the alternating polynomial Pd−1of Γ. But, from the above, r=αd−1=2n/(P(λ0) + 1), so that, using (3)wegetP(λ 0 )≥P d−1 (λ 0 ) and hence P=Pd−1.2 An interesting example of graphs satisfying the above hypotheses are the rantipodal distance-regular graphs. Indeed, they are extremal, D=d, and its ‘distancedpolynomial’ pdsatisfies Ad=pd(A). Thus, from pd=H−r 2P+r 2−1, we infer that their alternating polynomial satisfies P(λ0)=2n r−1 and hence r=2n P(λ0)+1 =2n d X i=0 π0 πi!−1 ,(12) where we have used (2). As mentioned above, this property of antipodal distanceregular graphs was already proved in [15] . At the end of the section, we will see that this condition is also sufficient to assure that an r-antipodal (regular) graph is distance-regular. Next, we use the above results to give a characterization of those distance-regular graphs which are antipodal, in terms of their eigenvalue multiplicities. With this aim, note first that, from the above expression of pd, we have pd(λi)=r 2((−1)i+1)−1 for 1 ≤i≤d.