Per-Spectral Characterizations Of Some Bipartite Graphs

A graph is said to be characterized by its permanental spectrum if there is no other non-isomorphic graph with the same permanental spectrum. In this paper, we investigate when a complete bipartite graph K_p,p with some edges deleted is determined by its permanental spectrum. We first prove that a graph obtained from K_p,p by deleting all edges of a star K_1,l, provided l < p, is determined by its permanental spectrum. Furthermore, we show that all graphs with a perfect matching obtained from K_p,p by removing five or fewer edges are determined by their permanental spectra.