𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Comments on the characteristic polynomial of a graph

✍ Scribed by K. Balasubramanian

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
655 KB
Volume
12
Category
Article
ISSN
0192-8651

No coin nor oath required. For personal study only.

✦ Synopsis

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 directed graphs, signed graphs, and complex nonhennetian graphs requiring extensive modifications to the Householder algorithm through the double + random shift QR procedure requiring more computations than claimed.

Furthermore, the QR procedure does not always converge and requires random shifts. To the contrary, it is shown that the Le Verrier-Fadeev-Frame method does not require any such modifications or random shifts and takes less total CPU times when both algorithms are run using vector processors. Hence it is demonstrated that the Le Verrier-Frame algorithm is efficient and superior in its universal and direct applicability to all graphs requiring no further modifications (directed, signed, and complex).

📜 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

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)

Comment on “Characteristic polynomials o
Comment on “Characteristic polynomials of fullerene cages”
✍ P.W. Fowler 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 166 KB

Pairing of the eigenvalues of the signed adjacency matrix is a property of all graphs, not only those of fullerenes. Eigenvalues of this matrix are dependent upon the labelling of the graph and so are not structural invariants.