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 number of both positive and negative spanning trees of G in terms of the principal minors of $L^{\pm }$ generalizing the 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.

Keywords:

• Incidence matrix
• Signed graph
• Net Laplacian matrix
• Matrix tree theorem

Acknowledgements

The author is indebted to Keivan Hassani Monfared for the idea of introducing the imaginary number $\mathrm{i}$ in incidence matrices of signed graphs. The author would like to thank Zoran Stanić and Thomas Zaslavsky for their comments on some of the results in this article. The author would also like to thank the anonymous reviewer and the handling editor Kevin Vander Meulen for their valuable comments.

Disclosure statement

No potential conflict of interest was reported by the author.

Correction Statement

This article has been corrected with minor changes. These changes do not impact the academic content of the article.