Per-spectral characterizations of some edge-deleted subgraphs of a complete graph

Abstract

Let denote the set of all graphs obtained from by removing five or fewer edges. Cámara and Haemers proved that graphs in are uniquely determined by their adjacency spectra with the exception for graphs and . In this paper, we show that all graphs in are uniquely determined by their permanental spectra. We further extend our findings by investigating when a complete graph with a few edges removed is uniquely determined by its permanental spectrum. More precisely, we prove that if induces a star, or a matching, or a disjoint union of a matching and a path , then is uniquely determined by its permanental spectrum.

Keywords:

• permanental polynomial
• permanental spectrum
• permanental cospectral

AMS Subject Classifications:

• 05C31
• 05C50
• 15A15

Acknowledgements

The authors would like to thank the anonymous referee for carefully reading the manuscript and giving valuable suggestions.

Notes

Research supported by NSFC [11371180] and CHPCME [Z2011014].