PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.)
Vol. 39(53), pp. 63--67 (1986)
AN APPLICATION OF CIRCUIT POLYNOMIALS TO THE COUNTING OF SPANNING TREES IN GRAPHS
E. J. Farrell and J. C. GrellDepartment of Mathematics, The University of the West Indies, St. Augustine, Trinidad
Abstract: $t$ is shown that the number of spanning trees in a graph can be obtained from the circuit polynomial of an associated graph. From this, the number of spanning tress in a regular graph is shown to be obtainable from the characteristic polynomial of a node-deleted subgraph. Finally, Cayley's theorem for the number of labelled tress is derived.
Classification (MSC2000): 05C99
Full text of the article:
Electronic fulltext finalized on: 2 Nov 2001. This page was last modified: 16 Nov 2001.
© 2001 Mathematical Institute of the Serbian Academy of Science and Arts