A COMBINATORIAL LAPLACIAN WITH VERTEX WEIGHTS

One of the classical results in graph theory is the matrix-tree theore m which asserts that the determinant of a cofactor of the combinatoria l Laplacian is equal to the number of spanning trees in a graph (see [ 1, 17, 11, 15]). The usual notion of the combinatorial Laplacian for a graph involves edge weights. Namely, a Laplacian L for G is a matrix with rows and columns indexed by the vertex set V of G, and the (u, v) -entry of L, for u, v in G, u not equal v, is associated with the edge -weight of the edge (u, v). It is not so obvious to consider Laplacian s with vertex weights (except for using some symmetric combinations of the vertex weights to define edge-weights). In this nets, we consider a vertex weighted Laplacian which is motivated by a problem arising i n the study of algebro-geometric aspects of the Bethe Ansatz [18]. The usual Laplacian can be regarded as a special case with all vertex-wei ghts equal. We will generalize the matrix-tree theorem to matrix-tree theorems of counting ''rooted'' directed spanning trees. In addition, the characteristic polynomial of the vertex-weighted Laplacian has coe fficients with similar interpretations. We also consider subgraphs wit h non-trial boundary. The will shown that the Laplacian with Dirichlet boundary condition has its determinant equal to the number of rooted spanning forests. The usual matrix-tree theorem is a special case with the boundary consisting of one single vertex. (C) 1996 Academic Press , Inc.