On the evaluation of the characteristic polynomial of a chemical graph
- 1 March 1990
- journal article
- research article
- Published by Wiley in Journal of Computational Chemistry
- Vol. 11 (2) , 217-222
- https://doi.org/10.1002/jcc.540110207
Abstract
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 n4. 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 n3. 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.Keywords
This publication has 40 references indexed in Scilit:
- The characteristic polynomial of a chemical graphJournal of Mathematical Chemistry, 1988
- Computer generation of spectra of graphs: Applications to C60 clusters and other systemsJournal of Computational Chemistry, 1988
- Computer generation of characteristic polynomials of edge‐weighted graphs, heterographs, and directed graphsJournal of Computational Chemistry, 1988
- Facile calculations of the characteristic polynomial and π-energy levels of molecules using chemical graph theoryJournal of Chemical Education, 1987
- Applications of combinatorics and graph theory to spectroscopy and quantum chemistryChemical Reviews, 1985
- Computer generation of the characteristic polynomials of chemical graphsJournal of Computational Chemistry, 1984
- Spectra of chemical treesInternational Journal of Quantum Chemistry, 1982
- The aromaticity of annulenoannulenesJournal of the American Chemical Society, 1978
- Aromaticity and conjugationJournal of the American Chemical Society, 1977
- Drum Shapes and Isospectral GraphsJournal of Mathematical Physics, 1966