✦ LIBER ✦

Computational algorithms for matching polynomials of graphs from the characteristic polynomials of edge-weighted graphs

✍ Scribed by Haruo Hosoya; K. Balasubramanian

Publisher: John Wiley and Sons
Year: 1989
Tongue: English
Weight: 736 KB
Volume: 10
Category: Article
ISSN: 0192-8651
DOI: 10.1002/jcc.540100511

No coin nor oath required. For personal study only.

✦ Synopsis

Computational algorithms are described which provide for constructing the set of associated edgeweighted directed graphs such that the average of the characteristic polynomials of the edge-weighted graphs gives the matching polynomial of the parent graph. The weights were chosen to be unities or purely imaginary numbers so that the adjacency matrix is hermitian. The computer code developed earlier by one of the authors (K. B.) is generalized for complex hermitian matrices. Applications to bridged and spirographs, some lattices and all polycyclic graphs containing up to four cycles are considered.

📜 SIMILAR VOLUMES

Computer generation of characteristic po

Computer generation of characteristic polynomials of edge-weighted graphs, heterographs, and directed graphs

✍ K. Balasubramanian 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 624 KB

The computer code developed previously (K. Balasubramanian, J . Computational Chern., 5,387 (1984)) for the characteristic polynomials of ordinary (nonweighted) graphs is extended in this investigation to edge-weighted graphs, heterographs (vertex-weighted), graphs with loops, directed graphs, and s

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

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

Operator technique for obtaining the rec

Operator technique for obtaining the recursion formulas of characteristic and matching polynomials as applied to polyhex graphs

✍ Haruo Hosoya; Noriko Ohkami 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 581 KB

A simple and efficient method, called an operator technique, for obtaining the recurrence relation of a given counting polynomial, e.g., characteristic Pc; (x) or matching M c (x) polynomial, for periodic networks is proposed. By using this technique the recurrence relations of the Pc (x) and M(; (x

An Accurate and Efficient Algorithm for

An Accurate and Efficient Algorithm for the Computation of the Characteristic Polynomial of a General Square Matrix

✍ S. Rombouts; K. Heyde 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 99 KB

An algorithm is presented for the efficient and accurate computation of the coefficients of the characteristic polynomial of a general square matrix. The algorithm is especially suited for the evaluation of canonical traces in determinant quantum Monte-Carlo methods.