Spectral characterization of the complete graph removing a cycle

Abstract

A graph is determined by its spectrum if there is not another graph with the same spectrum. Cámara and Haemers proved that the graph Kn∖Ck, obtained from the complete graph Kn with n vertices by deleting all edges of a cycle Ck with k vertices, is determined by its spectrum for k∈{3,4,5}, but not for k=6. In this paper, we show that k=6 is the unique exception for the spectral determination of Kn∖Ck.