FROM REGULAR BOUNDARY GRAPHS TO ANTIPODAL DISTANCE-REGULAR GRAPHS

Let Gamma be a regular graph with n vertices, diameter D, and d + 1 di fferent eigenvalues lambda > lambda(1) > > lambda(d). In a previous pa per, the authors showed that if P(lambda) > n - 1, then D less than or equal to d - 1, where P is the polynomial of degree d-1 which takes a lternating values +/-1 at lambda(1), ..., lambda(d). The graphs satisf ying P(X) = n - 1, called boundary graphs, have shown to deserve some attention because of their rich structure. This paper is devoted to th e study of this case and, as a main result, it is shown that those ext remal (D = d) boundary graphs where each vertex have maximum eccentric ity are, in fact, 2-antipodal distance-regular graphs. The study is ca rried out by using a new sequence of orthogonal polynomials, whose spe cial properties are shown to be induced by their intrinsic symmetry. ( C) 1998 John Wiley & Sons, Inc.