Premium
On the evaluation of the characteristic polynomial of a chemical graph
Author(s) -
Živković Tomislav P.
Publication year - 1990
Publication title -
journal of computational chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.907
H-Index - 188
eISSN - 1096-987X
pISSN - 0192-8651
DOI - 10.1002/jcc.540110207
Subject(s) - adjacency matrix , characteristic polynomial , eigenvalues and eigenvectors , mathematics , graph , adjacency list , matrix polynomial , combinatorics , polynomial , order (exchange) , discrete mathematics , mathematical analysis , physics , quantum mechanics , finance , economics
The evaluation of the characteristic polynomial of a chemical graph is considered. It is shown that the operation count of the Le Verrier–Faddeev–Frame method, which is presently considered to be the most efficient method for the calculation of the characteristic polynomial, is of the order n 4 . Here n is the order of the adjacency matrix A or equivalently, the number of vertices in the graph G . Two new algorithms are described which both have the operation count of the order n 3 . These algorithms are stable, fast, and efficient. A related problem of finding a characteristic polynomial from the known eigenvalues λ i of the adjacency matrix is also considered. An algorithm is described which requires only n ( n − 1)/2 operations for the solution of this problem.