𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the evaluation of the characteristic polynomial of a chemical graph

✍ Scribed by Tomislav P. Živković

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
583 KB
Volume
11
Category
Article
ISSN
0192-8651

No coin nor oath required. For personal study only.

✦ Synopsis

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 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.

📜 SIMILAR VOLUMES

Comments on the characteristic polynomia
Comments on the characteristic polynomial of a graph
✍ K. Balasubramanian 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 655 KB

Several unique advantages of the Le Verrier-Fadeev-Frame method for the characteristic polynomials of graphs over the method proposed by Zivkovic recently based on the Givens-Householder method are described. It is shown that the Givens-Householder method proposed by Zivkovic, by itself fails for di

Computer generation of the characteristi
Computer generation of the characteristic polynomials of chemical graphs
✍ K. Balasubramanian 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 497 KB

A computer program based on the Frame method for the characteristic polynomials of graphs is developed. This program makes use of an efficient polynomial algorithm of Frame for generating the coefficients in the characteristic polynomials of graphs. This program requires as input only the set of ver

A solution to Gutman's problem on the ch
A solution to Gutman's problem on the characteristic polynomial of a bipartite graph
✍ Xueliang Li; Heping Zhang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 209 KB

In this short paper, we present a solution to Gutman's problem on the characteristic polynomial of a bipartite graph (Research Problem 134, Discrete Math. 88 (1991)). In [2] I. Gutman proposed a research problem which is stated as follows. The matchings polynomial of a graph G is defined by cl(G,x)

Parallel algorithm for the computation o
Parallel algorithm for the computation of characteristic polynomials of chemical graphs
✍ P. Venuvanalingam; P. Thangavel 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

A parallel algorithm is developed for the f i t time based on Frame's method to compute the characteristic polynomials of chemical graphs. This algorithm can handle all types of graphs: ordinary, weighted, directed, and signed. Our algorithm takes only linear time in the CRCW PRAM model with O(n9) p

The Wiener polynomial of a graph
The Wiener polynomial of a graph
✍ Bruce E. Sagan; Yeong-Nan Yeh; Ping Zhang 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 674 KB

The Wiener index is a graphical invariant that has found extensive application in chemistry. We define a generating function, which we call the Wiener polynomial, whose derivative is a q-analog of the Wiener index. We study some of the elementary properties of this polynomial and compute it for some