𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Evaluation of the characteristic polynomial of a graph

✍ Scribed by Tomislav P Z̆ivković

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
387 KB
Volume
17
Category
Article
ISSN
0895-7177

No coin nor oath required. For personal study only.

✦ Synopsis

Two algorithms for the evaluation of the characteristic polynomial of a graph G are described.

Both algorithms have the operation count of the order n3, where n is the number of the vertices in the graph G. These algorithms are stable, fast, and efficient. They are one order of magnitude faster than the Le Verrier-Faddeev-Frame method, which is presently claimed to be the most efficient method for the calculation of the characteristic polynomial of a graph. A related problem of finding a characteristic polynomial from the known eigenvalues Xi of the adjacency matrix is also considered. An algorithm requiring only 0(n2) operations is described.

📜 SIMILAR VOLUMES

On the evaluation of the characteristic
On the evaluation of the characteristic polynomial of a chemical graph
✍ Tomislav P. Živković 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 583 KB

## 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 o

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

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)