Permanents and Determinants of Graphs: A Cycle Polynomial Approach

Abstract

Various connections have been established between the permanent and the determinant of the adjacency matrix of a graph. Connections are also made between these scalars and the number of perfect matchings in a graph. We establish conditions for graphs to have determinant 0 or $\pm 1$. Necessary conditions and sufficient conditions are obtained for graphs to have permanent equal to 0 or to 1.