ABSTRACT
There are a number of polynomials that one can associate with a graph. Among the graph-theoretical (graphic) polynomials the most im portant appears to be the characteristic polynomial
There are, in the main, three reasons why graphic polynomials are of interest for (chemical) graph theorists:^
1. Graphic polynomials appear as generating functions of combinatorial graph invariants
2. Graphic polynomials can be used to introduce algebraic concepts into graph theory
3. The study of graphic polynomials is an interesting and relevant research area per se
the characteristic polynomial of its adjacency matrix,
P(G;x) = det |xl - A| ( 1) where A and I are, respectively, the adjacency matrix of a graph G with N vertices and the N x N unit matrix. A graph eigenvalue is a zero of the characteristic polynomial
P(G;Xi) = 0 (2) for i = 1,2, . . . ,N. The complete set of graph eigenvalues {xj,X2, . . . x^} forms the spectrum of the graph. The eigenvalues are all real and the interval in which they lie is bounded. According to the Frobenius th e o re m ,th e limits of the graph spectrum are determined by the maximum valency of a vertex D„,ax in a graph:
-D „ (3) Among connected graphs, equality is achieved on the right-hand side if, and only if, all vertices in the graph have the same valency, while equality is achieved on the left-hand side if, and only if, the graph is also bipartite; in either case, these extreme eigenvalues are nondegenerate.
