Matrix tree theorem for the net Laplacian matrix of a signed graph

Abstract

For a simple signed graph $G$ with the adjacency matrix $A$ and net degree matrix $D^{\pm }$, the net Laplacian matrix is $L^{\pm }=D^{\pm }-A$. We introduce a new oriented incidence matrix $N^{\pm }$ which can keep track of the sign as well as the orientation of each edge of $G$. Also $L^{\pm }=N^{\pm }(N^{\pm }{)}^T$. Using this decomposition, we find the numbers of positive and negative spanning trees of $G$ in terms of the principal minors of $L^{\pm }$ generalizing Matrix Tree Theorem for an unsigned graph. We present similar results for the signless net Laplacian matrix $Q^{\pm }=D^{\pm }+A$ along with a combinatorial formula for its determinant.

arXiv comment16 pages, accepted in Linear and Multilinear Algebra