Croatica Chemica Acta, Vol. 77 No. 1-2, 2004.
Original scientific paper
A Theorem for Counting Spanning Trees in General Chemical Graphs and Its Particular Application to Toroidal Fullerenes
Edward C. Kirby
; Resource Use Institute, 14, Lower Oakfield, Pitlochry, Perthshire, PH16 5DS, Scotland, UK
Douglas J. Klein
; Texas A&M University at Galveston, Galveston, Texas 7753-1675, USA
Roger B. Mallion
; The King's School, Canterbury, Kent, CT1 2ES, England, UK
Paul Pollak
; The King's School, Canterbury, Kent, CT1 2ES, England, UK
Horst Sachs
; Institut für Mathematik, Technische Universität Ilmenau, Postfach 10 05 65, D-98684 Ilmenau, Germany
Abstract
A theorem is stated that enables the number of spanning trees in any finite connected graph to be calculated from two determinants that are easily obtainable from its cycles → edges incidence-matrix. The 1983 theorem of Gutman, Mallion and Essam (GME), applicable only to planar graphs, arises as a special case of what we are calling the Cycle Theorem (CT). The determinants encountered in CT are the same size as those arising in GME when planar graphs are under consideration, but CT is applicable to non-planar graphs as well. CT thus extends the conceptual and computational advantages of GME to graphs of any genus. This is especially of value as toroidal polyhexes and other carbon-atom species embedded on the torus, as well as on other non-planar surfaces, are presently of increasing interest. The Cycle Theorem is applied to certain classic, and other, graphs – planar and non-planar – including a typical toroidal polyhex.
Keywords
spanning trees; non-planar graphs; molecular complexity; toroidal fullerenes; torusenes; polyhexes
Hrčak ID:
102674
URI
Publication date:
31.5.2004.
Visits: 2.145 *