An edge version of the matrix-tree theorem and the wiener index

Abstract

Let T be a tree on n vertices. The Laplacian matrix is L(T)=D(T)−A(T), where D(T) is the diagonal matrix of vertex degrees and A(T) is the adjacency matrix. A special case of the Matrix-Tree Theorem is that the adjugate of L(T) is the n-by-n matrix of l's. The (n−l)-square "edge version" of L(T)is K(T). The main result is a graph-theoretic interpretation of the entries of the adjugate of K(T). As an application, it is shown that the Wiener Index from chemistry is the trace of this adjugate.