Spectral characterization of the complete graph removing a path: Completing the proof of Cámara–Haemers Conjecture

Abstract A graph G is A − D S if every A -cospectral graph of G is isomorphic to G . Denote by K n ∖ P k the graph obtained from the complete graph K n with n vertices by deleting all edges of a path P k with k vertices. In 2014, Camara and Haemers conjectured that K n ∖ P k is A − D S for every 2 ≤ k ≤ n . The conjecture has been confirmed for k = n (Doob and Haemers, 2002), 2 ≤ k ≤ 6 (Camara and Haemers, 2014), 7 ≤ k ≤ 9 (Mao et al., 2019) and k ≥ 20 (Liu et al., 2020). In this paper, we completely settle the conjecture by proving the remaining cases.