Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes Original Research Article

The number of spanning trees in a molecular graph (its ‘complexity’) has been of recent interest and, in this paper, various methods are applied to calculate the complexities of graphs that represent the fullerenes — as exemplified by the molecules C60 and C70, and the notional structures C60 (known as ‘handballene’) and C120 (‘Archimedene’). These graphs are large, regular and highly symmetrical and the methods chosen address the computational difficulties and advantages presented by these features. The methods discussed are of general applicability when the graph under study has at least one of these properties. One of the methods needs only ‘pencil-and-paper’ working when applied to the two C60 structures, C70 and the dual of C120. For C120, the evaluation of the (real) determinant of the (complex) matrices that arise was carried out on a personal computer.