## DIMACS TR: 2000-03

## Tree and Forest Volumes of Graphs

### Authors: Alexander Kelmans, Igor Pak and Alexander Postnikov

**
ABSTRACT
**

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.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-03.ps.gz

DIMACS Home Page