Characteristic and matching polynomials of chemical graphs

Abstract

A new algorithm is described for the calculation of characteristic polynomials of graphs. This algorithm uses the Householder matrix tridiagonalization method in combination with the Sturm sequence to directly provide the desired polynomial coefficients. The accuracy of the procedure for moderately large chemical graphs (≈ 100 vertices) is shown to be equivalent to that of previous procedures which use integer arithmetic. A new non-recursive procedure for evaluation of the matching polynomial is also presented. This latter procedure uses a single multiple fragmentation of a polycyclic graph to obtain acyclic fragments whose characteristic polynomials define the matching polynomial.