The tree volume of a weighted graph $G$ is the ``sum'' of the tree volumes of all spanning trees of $G$, and the tree volume of a weighted tree $T$ is the product of the edge weights of $T$ times the ``product'' of the letters of the Pr\"{u}fer code of $T$ where the vertices of $G$ are viewed as independent indeterminants that can be multiplied and commute. The forest volume of $G$ is the tree volume of the graph $G^c$ obtained from $G$ by adding a new vertex $c$ and connecting every vertex of $G$ with $c$ by an arc of weight 1. We show that the forest volume is a natural generalization of the Laplacian polynomial of graphs and that it also can be expressed as the characteristic polynomial of a certain matrix similar to the Laplacian matrix. It turns out that the forest volumes of graphs possesses many important properties of the Laplacian polynomials, for example, the reciprocity theorem holds also for the forest volumes. We describe two constructions of graph compositions, and show that the forest volume of a composition can be easily found if the ``structure'' of the composition and the forest volumes of the graph--bricks are known. As an illustration of the results on the forest volume of graph--compositions we give a combinatorial interpretation and proof of Hurwitz's identity.
Keywords: graph, tree, forest spanning tree, Laplacian matrix and polynomial, tree and forest volume.
DIMACS Home Page