Let Gamma be a graph on n vertices, adjacency matrix A, and distinct eigenvalues lambda > lambda(1) > lambda(2) > ... > lambda(d). For every k = 0, 1,..., d - 1, the k-alternating polynomial P-k is defined to be the polynomial of degree k and norm parallel to P(k)parallel to(infinity), = max(1 less than or equal to/less than or equal to d) {P-k(lambda(1))} = 1 that attains maximum value at lambda. 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(Gamma) of Gamma in terms of its eigenvalues. Namely, it was shown that P-k(lambda) > parallel to nu parallel to(2) - 1 double right arrow D(Gamma)less than or equal to k, where nu is the (positive) eigenvector associated to lambda with minimum component 1. In this work we improve upon this result by assuming that some extra information about the structure of Gamma is known. To this end, we introduce the so-called tau-adjacency polynomial Q(tau). For each 0 less than or equal to tau less than or equal to d, the polynomial Q(tau) is defined to be the polynomial of degree tau and norm parallel to Q(tau)parallel to(A) = max(1 less than or equal to i less than or equal to n) {parallel to Q tau(A)e(i)parallel to} = 1 that attains maximum value at lambda. Then it is shown that P-k(lambda) > parallel to nu parallel to(2)/Q(tau)(2)(lambda) - 1 double right arrow D(Gamma) less than or equal to k + 2 tau. Some applications of the above results, together with new bounds for generalized diameters, are also presented. (C) 1998 Elsevier Science B.V. All rights reserved. [References: 31]
展开▼
