On a Class of Polynomials and Its Relation with the Spectra and Diameters of Graphs

Letλ1>λ2>…>λdbe points on the real line. For everyk=1, 2, …, d, thek-alternatingpolynomialPkis the polynomial of degreekand norm ‖Pk‖∞=max1⩽l⩽d{|Pk(λl)|}⩽1 that attains maximum absolute value at any pointλ∉[λd, λ1]. Because of this optimality property, these polynomials may be thought of as the discrete version of the Chebychev polynomialsTkand, for particular values of the given points,Pkcoincides in fact with the “shifted”Tk. In general, however, those polynomials seem to bear a much more involved structure than Chebychev ones. Some basic properties of thePkare studied, and it is shown how to compute them in general. The results are then applied to the study of the relationship between the (standard or Laplacian) spectrum of a (not necessarily regular) graph or bipartite graph and its diameter, improving previous results.