Computing the determinant of a signed graph

Abstract

A signed graph is a simple graph in which every edge has a positive or negative sign. In this article, we employ several algebraic techniques to compute the determinant of a signed graph in terms of the spectrum of a vertex-deleted subgraph. Particular cases, including vertex-deleted subgraphs without repeated eigenvalues or singular vertex-deleted subgraphs are considered. As applications, an algorithm for the determinant of a signed graph with pendant edges is established, the determinant of a bicyclic graph and the determinant of a chain graph are computed. In the end, the uniqueness of the polynomial reconstruction for chain graphs is proved.

Keywords

• signed graph
• characteristic polynomial
• eigenvalues
• determinant
• bicyclic graph
• chain graph
• 05c50
• 05c22