Per-spectral characterizations of graphs with extremal per-nullity

A graph G is said to be determined by its permanental spectrum if any graph having the same permanental spectrum as G is isomorphic to G. In this paper, we introduce the permanental nullity of a graph, the multiplicity of the number zero in the permanental spectrum of a graph, to study graphs determined by their permanental spectra. First, we determine all graphs of order n   whose permanental nullities are n−2n−2, n−3n−3, n−4n−4 and n−5n−5, respectively. Then, we show that all graphs with the permanental nullity n−2n−2, n−3n−3, or n−5n−5, and all non-bipartite graphs with the permanental nullity n−4n−4 are determined by their permanental spectra. In particular, we prove that the complete bipartite graphs are determined by their permanental spectra.