co.combinatorics - The Matrix Tree Theorem for Weighted Graphs.

For signed graphs we have an interesting matrix-tree theorem. A signed graph is a graph with the additional structure of edge signs (weights) being either +1 or -1. We say that a cycle in a signed graph is balanced if the product of the edges in the cycle is +1. A signed graph is balanced if all of its cycles are balanced. Otherise, we say a signed graph is unbalanced.

We say a subgraph $H$ of a connected signed graph $G$ is an essential spanning tree of $Gamma$ if either

1) $Gamma$ is balanced and $H$ is a spanning tree of $G$, or

2) $Gamma$ is unbalanced, $H$ is a spanning subgraph and every component of $H$ is a unicyclic graph with the unique cycle having sign -1.

The matrix-tree theorem for signed graphs is stated as follows:

Let $G$ be a connected signed graph with $N$ vertices and let $b_k$ be the number of essential spanning subgraphs which contain $k$ negative cycles. Then

$$ det(L(G))=sum_{k=0}^n 4^k b_k.$$

For some references see:

T. Zaslavsky, Signed Graphs, Discrete Appl. Math, 4 (1982), 47-74.

S. Chaiken, A combinatorial proof of the all minors matrix tree theorem. SIAM J. Algebraic Discrete Methods, 3 (1982), 319-329.

Signed graphs are used in spin glass theory and network applications.

Considering mixed graphs, which are directed graphs that have some edges as undirected, we actually get the same theory. This is immediate since the matrix definitions are identical for signed graphs and mixed graphs. This seems to escape many of the people studying matrix properties of mixed graphs however. See:

R. Bapat, J. Grossman and D. Kilkarni, Generalized Matrix Tree Theorem for Mixed Graphs, Lin. and Mult. Lin. Algebra, 46 (1999), 299-312.