Spanning Trees of Graphs and Related Topics

problems in enumerative combinatorics and graph theory.
The first important result in this respect is a classical
matrix--tree theorem that in its general form expresses, as the
determinant of a certain graph matrix, not only the number
of spanning trees of a graph but also a generating function of
all spanning trees of the graph.

We are going to discuss various results on spanning tree
enumeration. In particular we will describe certain properties
of the Laplacian polinomials and Laplacian spectrum of graphs
that play an important role in spanning tree enumeration. We
will also discuss a coding of spanning trees of so called
graph--compositions which is a generalization of the well
known Pr\"ufer coding of trees. This generalization provides a
natural way to describe the list of spanning trees of graphs of
certain type. It also allows to give purely combinatorial proves
of various results on spanning tree enumeration that have been
obtain before by using an algebraic approach. Moreover this
generalization suggests a natural notion of a
forest polynomial of a graph that is a generalization
and posseses some properties of the Laplacian polynomial of a
graph. A new coding procedure provides a certain relation between
the graph--arguments and their compositions. This
relation has interesting applications. For example it allows to
find a mechanism for generating infinitely many identities
which are generalizations of classical Abel's and Hurwitz'
identities.