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

✍ Scribed by M.A. Fiol; E. Garriga; J.L.A. Yebra

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 602 KB
• Volume: 67
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1996.0033

✦ Synopsis

Let * 1 >* 2 > } } } >* d be points on the real line. For every k=1, 2, ..., d, the k-alternating polynomial P k is the polynomial of degree k and norm

Because of this optimality property, these polynomials may be thought of as the discrete version of the Chebychev polynomials T k and, for particular values of the given points, P k coincides in fact with the ``shifted'' T k . In general, however, those polynomials seem to bear a much more involved structure than Chebychev ones. Some basic properties of the P k are 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.

1996 Academic Press, Inc. given indexing of the vertices, is isomorphic to R n . Thus, we will make no difference between the vertex v i # V and the ith unit vector e i # R n .

Recently, some results relating the diameter of a regular graph and its second eigenvalue (in absolute value) have been given by Chung [3],

article no. 0033 48 0095-8956Â96 18.00