Per-spectral and adjacency spectral characterizations of a complete graph removing six edges ?
Cmara 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?6 m ? 6 and every large enough n n one can obtain graphs which are not DAS by removing m m edges from a complete graph Kn K n . Let Gn G n denote the set of all graphs obtained from a complete graph Kn K n by deleting six edges. In this paper, we show that all graphs in Gn G n are uniquely determined by their permanental spectra. However, we show that for each n?7 n ? 7 or n=5 n = 5 there is just one pair of nonisomorphic cospectral graphs in Gn G n , and for n=4 n = 4 or 6 all graphs in Gn G n are DAS.
cospectral characteristic polynomial permanental polynomial permanental spectrum