From Regular Boundary Graphs to Antipodal Distance-Regular Graphs* M. A. Fiol, E. Garriga, and J. L. A. Yebra DEPARTAMENT DE MATEMA?TICA APLICADA I TELEMA?TICA UNIVERSITAT POLITE?CNICA DE CATALUNYA E-mails: f iol@mat.upc.es, garriga@mat.upc.es, yebra@mat.upc.es Received April 10, 1995; revised October 16, 1997 Abstract: Let ? be a regular graph with n vertices, diameter D, and d + 1 different eigenvalues ? > ?1 > и и и > ?d . In a previous paper, the authors showed that if P (?) > n ? 1, then D ? d ? 1, where P is the polynomial of degree d?1 which takes alternating values ▒1 at ?1 , . . . , ?d . The graphs satisfying P (?) = n ? 1, called boundary graphs, have shown to deserve some attention because of their rich structure. This paper is devoted to the study of this case and, as a main result, it is shown that those extremal (D = d) boundary graphs where each vertex have maximum eccentricity are, in fact, 2-antipodal distanceregular graphs. The study is carried out by using a new sequence of orthogonal polynomials, whose special properties are shown to be induced by their intrinsic c 1998 John Wiley & Sons, Inc. J Graph Theory 27: 123?140, 1998 symmetry. Keywords: antinodal distance-regular graphs, boundary graphs, eigenvalues, orthogonal polynomials 1. INTRODUCTION A general problem which has deserved much attention among graph theorists is to *Work supported in part by the Spanish Research Council (Comisio?n Interministerial de Ciencia y Tecnologia, CICYT) under projects TIC 92-1228-E and TIC 94-0592. c 1998 John Wiley & Sons, Inc. CCC 0364-9024/98/030123-18 124 JOURNAL OF GRAPH THEORY know how the properties of a graph depend on its (adjacency matrix) spectrum. In this context, some results relating the diameter of a regular graph and its second eigenvalue (in absolute value) have been recently given by Chung [4], Delorme and Sole? [6] and Mohar [11]. As it was pointed out in [7], the results in [4, 6] admit the following unified presentation. Let ? > ?1 > и и и > ?d be the distinct eigenvalues of a regular graph ? of order n and diameter D(?). It is well known that D(?) ? d. Let p ? Rk [x], the vector space of real polynomials of degree at most k ? d ? 1. Then, p(?) > kpk? (n ? 1) ? D(?) ? dgr p ? k (1) where kpk? = max1?l?d {|p(?l )|}. Similar results concerning the spectrum of the Laplacian matrix were also given for (not necessarily regular) graphs by Chung, Faber and Manteuffel [5] using Tchebychef polynomials. Following these works, the authors [7] optimized previous results by introducing a new class of polynomials, called the k -alternating polynomials because of their special behavior on the mesh M = {?1 , . . . , ?d }. More precisely they showed that, for a regular graph on n vertices, (2) Pk (?) > n ? 1 ? D(?) ? k where Pk ? Rk [x] denotes the k -alternating polynomial defined by the condition: Pk (?) = sup {p(?) : kpk? ? 1}. p?Rk [x] In [7] it was shown that the k -alternating polynomial Pk is unique and its degree is exactly k . Moreover, Pd?1 ? P , called the alternating polynomial for short, is characterized by P (?l ) = (?1)l+1 , l = 1, . . . , d, and hence an easy computation gives: P (?) = d X ?0 i=1 ?i , d Y where ?i = |?i ? ?l |, i = 0, 1, . . . , d. (3) l=0(l=i) / See [7] for more details. The above results suggest the issue of analyzing the graphs which are on the boundary of the region in which the condition on the lefthand side of (2) holds. Namely, those regular graphs satisfying Pk (?) = n ? 1, which we call k -boundary graphs. In the?apparently more tractable?case k = d ? 1, we simply speak of boundary graphs. Notice that, from their definition and (3), boundary graphs are characterized by P (?) + 1 = d X ?0 l=0 ?l = n. (4) The study of such graphs was initiated by the authors in [8, 9], where some of their basic properties were discussed. Also, some constructions of such graphs ANTIPODAL DISTANCE-REGULAR GRAPHS 125 were presented. In particular, it was shown that there are boundary graphs with diameter D ? d ? 1, but there are also graphs with spectrally maximum diameter D = d, which we call below extremal. Then, it was proved that all 2-antipodal distance-regular graphs are extremal boundary graphs. Unfortunately, the converse result does not hold. Thus, the Hoffman graph [10], which is cospectral with the (2antipodal distance-regular) graph Q4 ?the 4-cube?is an example of an extremal boundary graph which is not distance-regular. In fact, since the characterization (4) of boundary graphs only takes into account the (distinct) eigenvalues and the order of the graph, all cospectral graphs of a boundary graph are also boundary graphs. Like Q4 , the Hoffman graph has diameter 4 and is therefore extremal. However, unlike the 4-cube, not all the vertices of the Hoffman graph have eccentricity equal to the diameter. A natural question is then to ask whether every extremal boundary graph having all vertices with maximum eccentricity is a 2-antipodal distance-regular graph. The main contribution of this paper is to give an affirmative answer to such a question. Our study is mainly based on a new class of orthogonal polynomials, which are the topic of Section 2. Their special properties, inherited from their intrinsic symmetry, suggest that their interest might go beyond our applications, which begin in Section 3 for general boundary graphs. In the same section we show that there are some parallelism between our study and part of the theory on distance-regular graphs. The close relationship between extremal boundary graphs and 2-antipodal distance-regular graphs is explored in Section 4. The rest of this section is devoted to establish the main terminology, and to recall some additional known results used throughout the paper. Thus, ? = (V, E) denotes a simple, connected graph, of order |V | = n, and regular of degree ?. For a given ordering of its vertices, we only distinguish between a vertex ei and the corresponding vector ei of the canonical base of Rn by the bold type used. Besides, we consider A, the adjacency matrix of ?, as an endomorphism of Rn . As usual, J denotes the nОn matrix with all entries equal to 1, and similarly j ? Rn is the all-1 vector. The eigenvalues of the graph are denoted by ?0 > ?1 > и и и > ?d (we will assume that ? is not the complete graph, so that d ? 2) but, because of its special role, the largest eigenvalue ?0 is also denoted by ?. The spectrum of the graph, which is the set of eigenvalues together with their multiplicities mi = m(?i ), is md m1 0 denoted by Spec ? = {?m 0 , ?1 , . . . , ?d }. The distance between two vertices is denoted by ?(ei , ej ) and the diameter is represented by D(?). A vertex ei is said to be diametral whenever there exists a vertex ej such that ?(ei , ej ) = D(?), and then {ei , ej } will be referred to as a diametral pair of vertices. In this case, any shortest path between ei and ej is called a diametral path of ?. The graph is called diametral when all its vertices are diametral. It is well known that D(?) ? d and when D(?) = d we say that ? is an extremal graph. As usual, ?l (e) denotes the set of vertices at distance l from e and ?l is the graph on V where two vertices are adjacent whenever they are at distance l in ?. A generic polynomial p operates on Rn by the rule pw = p(A)w, and the matrix is not specified unless some confusion may arise. Let Z + and Z ? denote the monic polynomials having as roots the eigenvalues ?l , 1 ? l ? d, with odd 126 JOURNAL OF GRAPH THEORY and even subindex l, respectively. Then, we will make ample use of the following spectral decompositions of the canonical vector ei . ei = 1 1 1 ? j + zi = j + z i1 + и и и + z id = j + z + i + zi n n n (5) ? + ? where z i ? j ? , z il ? Ker (x ? ?l ), z + i ? Ker Z and z i ? Ker Z . Since for a boundary graph the inequality in the righthand side of (2) (with k = d ? 1) does not hold, the matrix P (A) may have entries equal to zero. That is, it may happen that hP e, e?i = 0 for some pair of vertices e, e?. We say in this case that each one is a conjugate vertex and, when they are different, that they form a pair of conjugate vertices. Thus, every diametral pair of an extremal graph is a conjugate pair. If hP e, ei = 0 we say that e is a selfconjugate vertex. In some cases, condition (4) characterizing boundary graphs is strong enough to determine the entries of the matrix P (A), from where some of the main properties of such graphs follow. Indeed, since the alternating polynomial satisfies P (?l ) = (?1)l+1 , 1 ? l ? d, we have kP z i k2 = kz i k2 = 1 ? k n1 jk2 = 1 ? n1 , and this decomposition allows us to give a generic expression for the ij entry of the matrix P (A), as follows: (P (A))ij = hP ei , ej i = P (?) 1 j + P zi, j + zj n n n?1 + kP z i k kz j k cos ?ij n n?1 = (1 + cos ?ij ) n = (6) where ?ij represents the angle formed by P z i and z j . As a straightforward consequence of (6), note that all the entries of P (A) satisfy 0 ? (P (A))ij < 2(1 ? n1 ). Furthermore, (7) (P (A))ij = 0 ? P z i = ?z j + ? ? l ? z+ i = ?z j , z i = z j ? z il = (?1) z jl , ( ? (1 ? l ? d) (8) ei = n1 j + z i1 + z i2 + z i3 + и и и + z id ej = n1 j ? z i1 + z i2 ? z i3 + и и и + (?1)d z id (9) since, in j ? , P z = z iff z ? Ker Z + , and P z = ?z iff z ? Ker Z ? . Notice that, by (9), the spectral decompositions of the conjugate vertices ei , ej have the same components, except for their signs which are alternatively equal or distinct. As we will see, the polynomials studied in the next section show a similar behavior at the points of the mesh and, we could say that, in a sense, each one has also a ??conjugate.?? For instance, consider the pair (P, I) formed by the alternating and the identity polynomials respectively. Then, using (9) we get P ei + Iej = 1 (P j + j) = j. n (10) ANTIPODAL DISTANCE-REGULAR GRAPHS 127 That is, if P ei has a zero component, all its other components are 1, and hence each vertex can only belong to a pair of conjugate vertices. Let V ? denote the set of conjugate vertices and let ?? be its induced subgraph in V ? . Let ? : V ? ? V ? be the mapping defined by ?e = (J ? P (A))e. From the above, ? is well defined and it is an involutive permutation of V ? . Then, in [8] the following result was proved. Proposition 1.1. In a boundary graph ? the mapping ? is an automorphism of ?? . Moreover, in ?, ?(?ei , ?ej ) = ?(ei , ej ), ?ei , ej ? V ? . 2. A CLASS OF ORTHOGONAL POLYNOMIALS Let M = {x1 > и и и > xm } be a mesh of m real points. For i = 1, . . . , m, set Mi = {1, . . . , m} \ {i} and ?i (M) = Y ?i (M) = (?1)i+1 ?i = |?i (M)|. (xi ? xl ), l?Mi Using the fact that each polynomial of degree ? m ? 1 can be identified by its values on M, we introduce in Rm?1 [x] a scalar product by m X hp, qi = i=1 1 p(xi )q(xi ), ?i (M) and a linear mapping T by (T p)(xi ) = (?1)i+1 p(xi ), i = 1, . . . , m. Clearly, T is an involutive automorphism of Rm?1 [x], and for this scalar product we have: P (?1)i+ 1 (a) T is symmetric, hT p, qi = m i=1 ?i (M) p(xi )q(xi ) = hp, T qi; (b) T is an isometry, hT p, T qi = hT 2 p, qi = hp, qi. In particular, kT pk = kpk. In order to establish the main results of this section we first need the following. Lemma 2.1. m X i=1 xki = ?i (M) 0 for k = 0, 1, . . . , m ? 2 1 for k = m ? 1. Proof. Since for polynomials of degree ? m ? 1 interpolation trough m points Q is exact, using Lagrange interpolation with Ri = j?Mi (x ? xj ) we have p= m X p(xi ) i=1 Ri (xi ) Ri = m X p(xi ) i=1 and for p = xk the result follows. ?i (M) Ri = m X p(xi ) i=1 ?i (M) ! xm?1 + и и и 128 JOURNAL OF GRAPH THEORY P 1 i+1 xr xs = Noticing that hT xr , xs i = m i=1 ?i (M) (?1) i i restate the above lemma in the following way: r s hT x , x i = Pm s xr+ i i=1 ?i (M) , we may 0 for r + s = 0, 1, . . . , m ? 2 1 for r + s = m ? 1. (11) We next use T to characterize some systems of orthogonal polynomials for the scalar product above. Proposition 2.2. Let pk , k = 0, . . . , m ? 1, be polynomials with dgr pk = k. Then, the following statements are equivalent: (i) {pk , k = 0, . . . , m ? 1} is an orthogonal system; (ii) T pk is proportional to pm?1?k , k = 0, 1, . . . , m ? 1. Proof. Since dgr pk = k , (11) implies hT pk , pl i = 0 for k + l < m ? 1. Let {pk , k = 0, . . . , m ? 1} be an orthogonal system. Then, T pk = m?1 X l=0 ckl pl = m?1 X ckl pl , l=m?1?k since for l < m ? 1 ? k we have ckl kpl k2 = hT pk , pl i = 0. For k = 0 we already obtain that T p0 is proportional to pm?1 . Using induction, let us assume that T p0 = ?0 pm?1 , . . . , T pk?1 = ?k?1 pm?k . Consider now l > m?1?k . Since T is involutive and m?1?l < k , we obtain pm?1?l = T 2 (pm?1?l ) = ?m?1?l T pl , so that 1 ckl kpl k2 = hT pk , pl i = hpk , T pl i = hpk , pm?1?l i = 0. ?m?1?l Therefore, ckl = 0 for l > m ? 1 ? k and T pk is proportional to pm?1?k . Reciprocally, assume now that T pk = ?k pm?1?k , for k = 0, 1, . . . , m ? 1. For 0 ? j < i ? m ? 1 we have m ? 1 ? i + j < m ? 1, so that hpi , pj i = hT pi , T pj i = ?i hpm?1?i , T pj i = 0. From this proposition we obtain, for k = 0, 1, . . . , m ? 1, kpk k2 = hT pk , T pk i = ?k2 kpm?1?k k2 , kpk k2 = hT pk , ?k pm?1?k i = ?k hT (?k xk + и и и), ?m?1?k xm?1?k + и и иi = ?k ?k ?m?1?k , (12) (13) where ?k is the leading coefficient of pk , 0 ? k ? m ? 1. Proposition 2.3. For any given x0 > x1 and any constant n there exists a unique system of orthogonal polynomials on the mesh M, w0 , w1 , . . . , wm?1 , with dgr wk = k, such that, for k = 0, 1, . . . , m ? 1, ANTIPODAL DISTANCE-REGULAR GRAPHS 129 (a) T wk = wm?1?k ; (b) wk (x0 ) + wm?1?k (x0 ) = n. Proof. The Gram-Schmidt procedure assures the existence of a unique system of orthonormal polynomials q0 , q1 , . . . , qm?1 , such that dgr qk = k and the leading coefficient of each qk is positive. From the theory of orthogonal polynomials we know that all their roots are real and belong to the interval (xm , x1 ). It follows that qk (x0 ) > 0 for all k . From (12) and (13) we obtain T qk = qm?1?k . Setting wk = ?k qk we have T wk = ?k T qk = ?k qm?1?k = ?k ?m?1?k wm?1?k . Now (a) is equivalent to ?k = ?m?1?k and (b) becomes n = ?k qk (x0 ) + ?m?1?k qm?1?k (x0 ) = (qk (x0 ) + qm?1?k (x0 ))?k , which determines ?k for k = 0, 1, . . . , m ? 1. In particular, (a) gives kwk k2 = ?k ?m?1?k , , k = 0, 1, . . . , m ? 1, (14) where ?k is the leading coefficient of wk . Denoting by PM the polynomial of degree m ? 1 such that PM (xi ) = (?1)i+1 , i = 1, . . . , m, we have: wm?1 (xi ) = T w0 (xi ) = (?1)i+1 ?0 , so that wm?1 = ?0 PM . Moreover, ?0 + ?0 PM (x0 ) = n, and n n w0 = (15) , wm?1 = PM . 1 + PM (x0 ) 1 + PM (x0 ) Notice that when M, x0 , n are such that PM (x0 ) = n ? 1, equation (15) becomes w0 = 1 and wm?1 = PM . We will consider this case in the context of graphs in the next section. Consider now two meshes M? = {?1 > и и и > ?d }, M = {?0 (= ?) > ?1 > и и и > ?d }. For the mesh M? (resp. M) we define the involutive automorphism T ? (resp. T ) and consider the scalar product h , i? (resp. h , i) and the norm k и k? (resp. k и k.) We also write ?i? = ?i (M? ) and ?i = ?i (M). For a fixed constant n let w0 , w1 , . . . , wd?1 be the orthogonal system of Proposition 2.3 for the mesh M? with x0 = ?, that is T ? wk = wd?1?k , wk (?) + wd?1?k (?) = n for k = 0, 1, . . . , d ? 1. We next introduce the polynomials in Rd [x]: vk = wk ? wk?1 , by defining w?1 = 0, wd = and w?1 (?) + wd (?) = n. n ?0 Qd i=1 (x k = 0, 1, . . . , d, ? ?i ), so that we still have: T ? w?1 = wd 130 JOURNAL OF GRAPH THEORY Proposition 2.4. The polynomials v0 , v1 , . . . , vd form an orthogonal system for the mesh M. Moreover, kvk k2 = ?k ?d?k , k = 0, 1, . . . , d, where ?k denotes the leading coefficient of vk . Proof. For k = 0, . . . , d, we have (T vk )(?i ) = (?1)i (wk (?i ) ? wk?1 (?i )) = (?1)i (T ? wd?1?k (?i ) ? T ? wd?k (?i )) = wd?k (?i ) ? wd?k?1 (?i ) = vd?k (?i ), i = 1, . . . , d; (T vk )(?) = vk (?) = wk (?) ? wk?1 (?) = n ? wd?1?k (?) ? n + wd?k (?) = vd?k (?), so that T vk = vd?k , for k = 0, 1, . . . , d and the result follows from Proposition 2.2. The value of kvk k2 comes from (14). Lemma 2.5. The scalar products in the two meshes M? and M are related by: hf, gi? = ?hf, gi ? hxf, gi. Proof. hf, gi? = hxf, gi. Proposition 2.6. relation: Pd 1 l=1 ? ? f (?l )g(?l ) l = Pd l=0 ???l ?l f (?l )g(?l ) = ?hf, gi ? The polynomials v0 , v1 , . . . , vd satisfy the following recurrence xv0 = v?1 + a0 v0 + c1 v1 xvi = bi?1 vi?1 + ai vi + ci+1 vi+1 (i = 1, . . . , d ? 1) xvd = bd?1 vd?1 + ad vd + vd+1 (16) where v?1 = 0, vd+1 = ?n0 (x ? ?0 )(x ? ?1 ) и и и (x ? ?d ) and, setting ??1 = 0 the coefficients are given by ?i?1 ?d?i?1 ci = , bi = , ai = ? ? bi ? ci , (i = 0, . . . , d). ?i ?d?i Proof. From the recursive relation satisfied by orthogonal polynomials, and equaling the leading coefficients, we have xvi = hxvi , vi?1 i hxvi , vi i ?i vi?1 + vi + vi+1 . 2 2 kvi?1 k kvi k ?i+1 Then, from (14) we get kvi k2? = kwi k2? + kwi?1 k2? = ?i ?d?1?i + ?i?1 ?d?i . By Proposition 2.4 and Lemma 2.5 we have bi = hxvi+1 , vi i 1 kwi k2? ?d?i?1 = ? hv , v i = = i+1 i ? 2 kvi k ?i ?d?i ?i ?d?i ?d?i ANTIPODAL DISTANCE-REGULAR GRAPHS 131 ai = hxvi , vi i 1 ?d?i?1 ?i?1 = (?kvi k2 ? kvi k2? ) = ? ? ? = ? ? bi ? ci 2 kvi k ?i ?d?i ?d?i ai Notice that Proposition 2.6 can also be stated as a matrix equation in the following way: ?? ? a0 c1 ?b a c ? 0 1 2 ? b1 a2 и ? ? b2 и и ? ? ? и и ? ? и и и ? v0 v1 v2 и и ?? ?? ?? ?? ?? ?? ?? ?? ?? cd ? ? vd?1 bd?1 ad vd ? v0 v1 v2 и и ? ? ? ? ? ? ? ? ? ? ? = x? ? ? ? ? ? ? ? ? vd?1 ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? vd 0 0 0 и и 0 ? ? ? ? ? ? ? . (17) ? ? ? ? vd+1 Then, the (d + 1) О (d + 1) tridiagonal matrix of coefficients, denoted by B , has as simple eigenvalues the roots of vd+1 , that is ?0 (= ?) > ?1 > и и и > ?d , with associated eigenvectors v(?i ) = (v0 (?i ), . . . , vd (?i ))T . Propositions 2.3 and 2.4 lead to an inductive procedure for constructing the polynomials v0 , v1 , . . . , vd on a given mesh M = {?0 (= ?) > ?1 > и и и > ?d }. If Mk ? {?k > и и и > ?d } for k = 0, . . . , d?1, let Vk = {v0 , . . . , vd?k }Mk (Proposition 2.4) and Wk = {w0 , . . . , wd?k?1 }Mk (Proposition 2.3) be the corresponding orthogonal sequences associated to Mk . Consider now the steps of the following diagram: ? ? Vk ?k Wk ?k Vk?1 Then, we construct V0 = {v0 , . . . , vd }M by applying ?0 ??0 ?и и и??d?1 ??d?1 ??d to Wd = {w0 }Md . 3. ORTHOGONAL POLYNOMIALS IN BOUNDARY AND DISTANCE-REGULAR GRAPHS Let G be a graph on n vertices, with distinct eigenvalues ? = ?0 > ?1 > и и и > ?d . Consider the systems of orthogonal polynomials w0 , w1 , . . . , wd?1 and v0 , v1 , . . . , vd of the preceding section, corresponding to the meshes M? = {?1 > и и и > ?d } and M = {?(= ?0 ) > ?1 > и и и > ?d }, respectively, for such a n. Notice that, since M consist of the eigenvalues of G, we have: Lemma 3.1. (a) wd is the Hoffman polynomial [10] of ?, that is, wd (A) = J; (b) w0 = 1 and wd?1 = P (alternating polynomial of ?) if and only if ? is a boundary graph. Proof. (a) is a well known result for a regular connected graph. Furthermore, (b) follows from (15) by taking PM = P . 132 JOURNAL OF GRAPH THEORY Now, define the numbers ki , i = 0, 1, . . . , kd recursively by ki = initialized with k0 = v0 (?) = 1. Then, ki = bi?1 ci ki?1 , bi?1 bi?1 и и и b0 ?d?i ?i ?0 ki?1 = = = kvi k2 . ci ci и и и c1 ?d ?0 n (18) Let us now turn our attention to distance-regular graphs. As it is well known, a graph ?, with adjacency matrix A and eigenvalues ? > ?1 > и и и > ?d , is a distance-regular graph if and only if its adjacency algebra (that is, the algebra generated by its adjacency matrix) contains the adjacency matrix of ?k , for any 1 ? k ? d, and this matrix is a polynomial of degree k in A, see Biggs [2] and Brouwer et al. [3]. In other words, there exists a sequence of polynomials {vk , 0 ? k ? d} such that dgr vk = k and (vk (A))ij = 1, if ?(ei , ej ) = k 0, otherwise, (19) which are usually called the (k -)distance polynomials. These polynomials satisfy the recurrence relation (16), where the coefficients ai , bi , ci are now the entries of the so-called intersection array of ?. Besides, the matrix B associated to the recurrence relation (17) is now the collapsed adjacency matrix of ?. See [2, 3] for more details. A known, but seldom explicited, result states that the distance polynomials constitute an orthogonal basis of Rd [x] with the scalar product hf, gi = d X m(?l ) l=0 n f (?l )g(?l ). (20) An easy proof of such result goes as follows. By (19), all entries of the main diagonal of vi (A)vj (A), i = / j , are equal to zero, and hence Tr(vi (A)vj (A)) = 0. On the other hand, since each vi (A) is a polynomial in A so is vi (A)vj (A), and therefore 0 = Tr(vi (A)vj (A)) = d X m(?l )vi (?l )vj (?l ) = nhvi , vj i. l=0 Furthermore, for i = j we get kvi k2 = hvi , vi i = 1 1 X Tr(vi (A)vi (A)) = |?i (v)| = ki . n n v?V (?) The reader has already probably noted the similarities between the recurrence relation (16) satisfied by the polynomials vi of both boundary graphs and distanceregular graphs. This will lead to a unified formula for both type of graphs, which is the main result of this section. Before proceeding with our study, however, we must recall some basic facts on orthogonal polynomials of a discrete variable. For more details see, for instance, [12]. Let {pi } be a sequence of polynomials satisfying the ANTIPODAL DISTANCE-REGULAR GRAPHS 133 following recurrence, initiated with p?1 = 0, p0 = 1: xpi = bi?1 pi?1 + ai pi + ci+1 pi+1 where bi?1 , ai , ci+1 are real numbers such that ci+1 = / 0 and bi?1 ci+1 > 0, 1 ? i ? d. Then, the following orthogonality property holds: d X pi (xl )pj (xl )?l = ?ij ki , (0 ? i, j < d + 1) (21) l=0 where the points xl are the (real and different) roots of pd+1 , k0 is any given positive number, ki = bi?1 ci ki?1 , 1 ? i ? d, and d X 1 p2i (xl ) ?d = p0 (xl )pd (xl ) = ?l i=0 ki ?d+1 kd d+1 (22) with ?i the leading coefficient of pi . Moreover, these polynomials satisfy also the so-called dual orthogonality property: d X i=0 pi (xl )pi (xm ) 1 1 = ?lm , ki ?l (0 ? l, m < d + 1). (23) The polynomials p?l ? Rd [x] defined on the mesh M = {x0 , . . . , xd } by p?l (xi ) = pi (xl ) are called the dual polynomials of the {pi }. Let us see some consequences of these results for boundary graphs and distanceregular graphs. Theorem 3.2. Let ? be a distance-regular graph or a boundary graph on n vertices, with eigenvalues ?0 = ? > ?1 > и и и > ?d , and let vd be the polynomial of degree d of the corresponding sequence of orthogonal polynomials. Then, d X 1 vi2 (?l ) хl vd (?l ) , = kvl? k2 = =n ?l ki х0 vd (?) i=0 where хl = х0 (?l ), х(x) = vd+1 (x) = Qd l=0 (x (24) ? ?l ). Proof. We have seen that, in both cases, the polynomials vi satisfy a recurrence relation of the type xvi = bi?1 vi?1 + ai vi + ci+1 vi+1 (25) with v?1 = 0, v0 = 1, and c1 , . . . , cd , a0 , . . . , ad , b0 , . . . , bd?1 being constants satisfying ai = ? ? bi ? ci (cd+1 = / 0 and b?1 can be conveniently chosen). We have also seen that they satisfy an orthogonal property: d X l=0 vi (?l )vj (?l )?l = ?ij ki (26) 134 JOURNAL OF GRAPH THEORY n with k0 = 1 and ki = bi?1 ci ki?1 , 1 ? i ? d. Then, by applying (22) with ?d = х0 (the leading coefficient of the Hoffman polynomial) and vd+1 (x) = х(x), we get kvi? k2 = d X vi2 (?l ) i=0 ki =n хl vd (?l ) . х0 kd (27) Hence, it suffices to show that kd = kvd k2 = vd (?). By induction, k?1 = 0 = v?1 (?) (by convention), and k0 = 1 = v0 (?). Let us then assume that the result holds for ki?1 and ki . Evaluating (25) at ? and solving for vi+1 (?), we obtain vi+1 (?) = (? ? ai )ki ? bi?1 ki?1 bi = ki = ki+1 , ci+1 ci+1 where we have used that bi?1 ki?1 = ci ki and ai = ? ? bi ? ci . In particular, we can obtain the following known result for the multiplicities of a distance-regular graph (see Bannai and Ito [1]): Corollary 3.3. Let ? be a distance-regular graph with eigenvalues ?0 = k > ?1 > и и и > ?d , and let vd the d-distance polynomial. Then, m(?l ) = х0 vd (?) хl vd (?l ) (0 ? l ? d) (28) l) Proof. From (20), we have ?l = m(? n . Then the result follows from (24). By (28) note that, since х0 vd (?) = х0 kd > 0, we must also have хl vd (?l ) > 0. n = kvi? k2 , that is, Moreover, we also have m(? i) m(?i ) = n hu(?i ), v(?i )i (0 ? i ? d) (29) which corresponds to the formula given by Biggs [2, Th.21.4] for the multiplicities of the eigenvalues of ?. In this formula, v(?i ) = (v0 (?i ), . . . , vd (?i ))T and u(?i ) = ( k10 v0 (?i ), . . . , k1d vd (?i )) are respectively the right and left eigenvalues of B , corresponding to the eigenvalue ?i , and with first component 1. For any i = / j, the vectors v(?i ) and u(?j ) are orthogonal. With respect to the consequences of Theorem 3.2 for boundary graphs, we have the following result. Corollary 3.4. ?d . Then, Let ? be a boundary graph with eigenvalues ?0 > ?1 > и и и > d X vi2 (?l ) i=0 ki = n?l . ?0 (30) Proof. Now, vd is the polynomial of Rd [x] defined by vd (?l ) = (?1)l , 0 ? l ? d (the Hoffman polynomial minus the alternating polynomial), so that ?d = ANTIPODAL DISTANCE-REGULAR GRAPHS 135 Pd 0 = ?n0 . Then, applying (24) with vd+1 (?l )vd (?l ) = хl (?1)l = ?l , and = 1, the result follows. Alternatively, the comparison between (18) and (26) gives ?l = ??l0n , so that (30) is just ?1l . We have already seen that, in the case of distance-regular graphs, the value of ki corresponds to the number of vertices |?i (v)| for any v . But, clearly, such a value is also the sum of the entries of every row or column of vi (A). The following result shows that this last property is also shared by boundary graphs. 1 l=0 ?l kd = k0 Lemma 3.5. Let A be the adjacency matrix of a distance-regular graph or a boundary graph, and let {vi , 0 ? i ? d} be the corresponding sequence of orthogonal polynomials. Then, the sum of the entries of each row or column of vi (A) is ki . Proof. Using previous results, we have: hvi ei , ji = hei , vi ji = hei , vi (?)ji = vi (?) = ki . 4. EXTREMAL BOUNDARY GRAPHS AND DISTANCE-REGULAR GRAPHS We devote this last section to study the relationship between extremal boundary graphs and distance-regular graphs. First, we recall that a graph ? is antipodal when the relation ei ? ej iff ei = ej or ?(ei , ej ) = D(?) is an equivalence relation. In particular, ? is 2-antipodal when all equivalence classes have 2 elements. Alternatively, ? is 2-antipodal when every connected component of ?D(?) is K2 . In [8], as a consequence of a more general result about r-antipodal graphs, it was proved the following result: Lemma 4.1. graphs. All 2-antipodal distance-regular graphs are extremal boundary This section is mainly devoted to examine the additional conditions under which the reciprocal statement holds. We begin by studying the structure of the graph as ??seen from a diametral vertex.?? Notice that, to say that e is a diametral vertex of an extremal boundary graph ? is equivalent to saying that ?d (e) consists of just one vertex (e?). We will use again the results on orthogonal polynomials of Section 2. Lemma 4.2. Let ? be a boundary graph with a pair of conjugate vertices e, e?. Then, for k = ?1, 0, . . . , d, wk e + wd?1?k e? = j. Proof. For k = ?1 and k = d the result is straightforward. Then, let us consider the remaining cases k = 0, 1, . . . , d?1. By using the spectral decompositions 136 JOURNAL OF GRAPH THEORY of e and e?: e= d X 1 zl, j+ n l=1 e? = d X 1 (?1)l z l , j+ n l=1 with z l ? Ker (A ? ?l I), we get wk e + wd?1?k e? = d X wk (?) wd?1?k (?) j+ j wk (?l )z l + n n l=1 + d X (?1)l (T ? wk )(?l )z l l=1 1 = (wk (?) + wd?1?k (?))j n + d X (wk (?l ) + (?1)l (?1)l+1 wk (?l ))z l = j l=1 as claimed. Notice that, for k = 0, Lemma 4.2 corresponds to (10) in Section 2. Let ? be a boundary graph with a pair of conjugate vertices e, e?. From Lemma 4.2 we have, for any vertex v ? V (?), hwk e, vi + hwd?1?k e?, vi = 1. (31) We are now ready to present the main result of this section. Theorem 4.3. An extremal boundary graph ? is distance-regular 2-antipodal around any diametral vertex e, and the corresponding local intersection array is independent of such a vertex. Proof. Let k = 0, 1, . . . , d and v ? ?k (e). Then, hwk e, vi = ?k hAk e, vi, and hwd?1?k e?, vi = 0 since ?(v, e?) ? d ? k . From (31) we obtain, hAk e, vi = 1 ?k (32) for any v ? ?k (e). Now, let k = ?1, 0, . . . , d ? 1 and v ? ?k+1 (e). Then, hwk e, vi = 0, and hwd?1?k e?, vi = ?d?1?k hAd?1?k e?, vi, because ?(v, e?) ? d ? k ? 1. Applying again (31) we have hAd?1?k e?, vi = 1 ?d?1?k (33) for any v ? ?k+1 (e). For a given vertex v ? ?k (e), 0 ? k ? d, let ak (v), bk (v), and ck (v) denote the number of vertices adjacent to v and belonging to ?k (e), ?k+1 (e), and ?k?1 (e) respectively. Then, for any k , we clearly have ak (v) + bk (v) + ck (v) = ?, where ANTIPODAL DISTANCE-REGULAR GRAPHS 137 a0 (v) = ad (v) = 0, b0 (v) = cd (v) = ? and, by convention, c0 (v) = 0 and bd (v) = 0. Denoting by u1 , . . . , uck (v) the vertices of ?k?1 (e) which are adjacent to v , equation (32) yields: ck (v) X 1 ck (v) k = hA e, vi = hAk?1 e, ul i = . ?k ?k?1 l=1 (34) Similarly, if w1 , . . . , wbk (v) represent the vertices in ?k+1 (e) which are adjacent to v , equation (33) leads to 1 ?d?k = hA d?k e?, vi = bk (v) X hAd?k?1 e?, wl i = l=1 bk (v) . ?d?1?k (35) As a consequence of (34) and (35) notice, in particular, that the numbers bk = bk (v) and ck = ck (v) do not depend on the considered vertex v ? ?k (e). Moreover, bk = ?d?1?k , ?d?k ck = ?k?1 , ?k ak = ? ? bk ? ck , (36) are also independent of the chosen diametral vertex e. From Theorem 4.3 and Corollary 4.1 we reach the following characterization of those extremal boundary graphs all of whose vertices are diametral. Theorem 4.4. A graph ? is distance-regular 2-antipodal if and only if it is a diametral extremal boundary graph. By (29) and (30), an immediate consequence of this characterization is: Proposition 4.5. The multiplicities of the eigenvalues of a distance-regular 2antipodal graph (diametral extremal boundary graph) are given by m(?i ) = ?0 ?i (i = 0, 1, . . . , d). Reasoning as in (32) we get that, for any diametral vertex e of an extremal boundary graph, hwi e, vi = 1 if and only if ?(v, e) ? i. Hence, the polynomials vi = wi ? wi?1 satisfy the following result. Corollary 4.6. Let e be a diametral vertex of an extremal boundary graph. Then, for any 1 ? j ? n, the vector vi e has j th component equal to 1 if ?(e, ej ) = i, and 0 otherwise. So, we could say that vi , 0 ? i ? d, is the ??locally?? i-distance polynomial of the graph. We end the section by giving some more results on (general) extremal boundary graphs. To begin with, note that, given a diametral vertex e of ?, the numbers 138 JOURNAL OF GRAPH THEORY ki defined by k0 = 1 and bi?1 ki?1 = ci ki (i = 1, . . . , d) correspond now to ki = |?i (e)|. Then, we have bi?1 ki?1 + ai ki + ci+1 ki+1 = ?ki and the tridiagonal matrix B of Section 2 has the eigenvector (k0 , k1 , . . . , kd )T with corresponding eigenvalue ?. Since k0 = v0 (?) = 1, we have ki = vi (?) (i = 0, 1, . . . , d), as we already know. Hence, (18) yields the following result: Proposition 4.7. Then, Let e be a diametral vertex of an extremal boundary graph. |?i (e)| = vi (?) = ?0 kvi k2 . n From previous results, the local intersection array of an extremal boundary graph (and hence the intersection array of a distance-regular 2-antipodal graph) is determined by its eigenvalues. Indeed, from the equalities (T ? wk )(?i ) = wd?1?k (?i ) (1 ? i ? d), wk (?) + wd?1?k (?) = n, we get a linear system of equations with the coefficients of wk and wd?1?k as unknowns. Then, Cramer's rule yields: ?d?1?k = (?1)k+1 Hk (?1 , . . . , ?d ) n Hk (?, ?1 , . . . , ?d ) (0 ? k ? d ? 2) where Hk (x1 , . . . , xm ) stands for the determinant of order m 1 1 1 .. . 1 x1 x2 x3 .. . xm x21 x22 x23 .. . x2m и и и xk1 1 x1 x21 k и и и x2 ?1 ?x2 ?x22 k и и и x3 1 x3 x23 .. .. .. .. . . . . и и и xkm (?1)m+ 1 (?1)m+ 1 xm (?1)m+ 1 x2m ?k xm?2 1 m?2 ?k ?x2 ?k xm?2 3 .. . иии ?k и и и (?1)m+ 1 xm?2 m иии иии иии By (34) and (35) we get bk = cd?k , and an explicit formula for such coefficients, as stated in the next Corollary. Corollary 4.8. The entries of the local intersection array of an extremal boundary graph ? are univocally determined by their eigenvalues, ? > ?1 > и и и > ?d , through the formulas: bk = cd?k = ? Hk (?1 , . . . , ?d )Hk?1 (?, ?1 , . . . , ?d ) Hk (?, ?1 , . . . , ?d )Hk?1 (?1 , . . . , ?d ) b0 = cd = ?, bd?1 = c1 = 1, (1 ? k ? d ? 2) ak = ? ? bk ? ck . Keeping in mind our description of an extremal boundary graph as a local distance-regular 2-antipodal graph, we come back to the subgraph ?? induced by the conjugate vertices. Then, ANTIPODAL DISTANCE-REGULAR GRAPHS 139 Proposition 4.9. Let ? be an extremal boundary graph with 1 + ?1 + и и и + ?d < 0. Then, either every vertex of each connected component of ?? is diametral, or neither is. Proof. Let e be a diametral vertex of ?, and let ei be a conjugate vertex adjacent to e. Let e? and e?i be their respective conjugate vertices which are also adjacent vertices by Proposition 1.1. Therefore, ?(ei , e?i ) ? d ? 2. Moreover, in [8] it was shown that the first two terms of the alternating polynomial of an extremal boundary graph (d ? 2) are: P =? n d?1 [x ? (1 + ?1 + и и и + ?d )xd?2 + и и и]. ?0 Hence, we have hP ei , e?i i = ? n (hAd?1 ei , e?i i ? (1 + ?1 + и и и + ?d )hAd?2 ei , e?i i) = 0 ?0 so that ?(ei , e?i ) = d and ei is also diametral. There are boundary graphs with self-conjugate vertices, but the examples of extremal boundary graphs known by the authors [8] have no such vertices. In the way of studying their possible existence, it could be worth considering the following facts: (1) If d is odd such vertices cannot exist. Indeed, By Proposition 1.1 and the property of being locally distance-regular, a self-conjugate vertex e would be on a diametral path, and at the same distance of its end vertices, but this only can happen if d is even. (2) Assuming that d is even, say d = 2d0 , Lemma 4.2 with k = d0 and for a self-conjugate vertex e yields: wd0 e + wd0 ?1 e = j . Therefore, the graph has radius d0 , the self-conjugate vertices are in the center of the graph, and ?d0 (e) contains all the pairs of diametral vertices. References [1] [2] [3] [4] [5] E. Bannai and T. Ito, Algebraic combinatorics I: Association schemes, Benjamin-Cummings Lecture Note Ser. 58, London (1993). N. Biggs, Algebraic graph theory, Cambridge University Press, Cambridge (1993). A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance regular graphs, Springer-Verlag (1989). F. R. K. Chung, Diameter and eigenvalues, J. Amer. Math. Soc. 2 (2) (1989), 187?196. F. R. K. Chung, V. Faber, and T. H. Manteuffel, An upper bound on the diameter of a graph from eigenvalues associated with its laplacian. SIAM J. Disc. Math. 7 (3) (1994), 443?457. 140 JOURNAL OF GRAPH THEORY [6] [7] [8] [9] [10] [11] [12] C. Delorme and P. Sole?, Diameter, covering index, covering radius and eigenvalues. European J. Combin. 12 (1991), 95?108. 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. M. A. Fiol, E. Garriga, and J. L. A. Yebra, Boundary graphs: The limit case of a spectral property (I), submitted, 1995. M. A. Fiol, E. Garriga, and J. L. A. Yebra, Boundary graphs: The limit case of a spectral property (II). Discrete Math., to appear. A. J. Hoffman, On the polinomial of a graph. Amer. Math. Monthly 70 (1963), 30?36. B. Mohar, Eigenvalues, diameter and mean distance in graphs. Graphs Combin. 7 (1991), 53?64. A. F. Nikiforov, S. K. Suslov, and V. B. Uvarov, Classical orthogonal polynomials of a discrete variable, Springer-Verlag, Berlin (1991).

1/--страниц