Per-spectral and adjacency spectral characterizations of a complete graph removing six edges

Cámara and Haemers (2014) investigated when a complete graph with some edges deleted is determined by its adjacency spectrum (DAS for short). They claimed: for any m≥6m≥6 and every large enough nn one can obtain graphs which are not DAS by removing mm edges from a complete graph KnKn. Let GnGn denote the set of all graphs obtained from a complete graph KnKn by deleting six edges. In this paper, we show that all graphs in GnGn are uniquely determined by their permanental spectra. However, we show that for each n≥7n≥7 or n=5n=5 there is just one pair of nonisomorphic cospectral graphs in GnGn, and for n=4n=4 or 6 all graphs in GnGn are DAS.