AN ALGORITHM FOR COUNTING SPANNING-TREES IN LABELED MOLECULAR GRAPHS HOMEOMORPHIC TO CATA-CONDENSED SYSTEMS

The algorithmic method of Gutman and Mallion (1993), for calculating t he number of spanning trees in the (labeled) molecular graphs of cata- condensed systems containing rings of only one size, was subsequently generalized by John and Mallion (1996) to make it applicable to such s ystems comprising rings of more than one size; this latter algorithm i s thus generally valid for enumerating the spanning trees in the molec ular graphs of any cata-condensed system. This algorithmic philosophy is extended here in order to devise a procedure that is suitable for a n even more general class of molecular graphs-namely, those homeomorph ic to the molecular graphs of cata-condensed systems. An example of it s use is illustrated by explicitly computing the numerical value for t he complexity of a (hypothetical) pentacyclic network consisting of tw o four-membered rings, two five-membered rings, and a nine-membered ri ng, giving rise to a spanning-tree count entirely in accord with that predicted via the theorem of Gutman, Mallion, and Essam (1983)-on the face of it, an apparently very different approach, based on the ''gene ralized characteristic polynomial'' of the inner dual of the graph in question.