×

An application of circuit polynomials to the counting of spanning trees in graphs. (English) Zbl 0599.05019

In the paper the number of spanning trees in a graph is brought into connection with so-called ”circuit polynomial” [introduced by the first author in Discrete Math. 25, 121-133 (1979; Zbl 0401.05057)] of an associated graph. In the case of regular graphs this shows how to obtain the number of spanning trees from the characteristic polynomial of a node-deleted subgraph.
Reviewer: P.Kirschenhofer

MSC:

05C05 Trees

Citations:

Zbl 0401.05057
PDFBibTeX XMLCite
Full Text: EuDML