Spectral characterization of the complete graph removing a path of small length

Abstract

A graph $G$ is said to be \emph{determined by its spectrum} if any graph having the same spectrum as $G$ is isomorphic to $G$. Let $K_n\setminus P_{\ell }$ be the graph obtained from $K_n$ by removing edges of $P_{\ell }$, where $P_{\ell }$ is a path of length $\ell -1$ which is a subgraph of a complete graph $K_n$. Cámara and Haemers~\cite{MC} conjectured that $K_n\backslash P_{\ell }$ is determined by its adjacency spectrum for every $2\le \ell \le n$. In this paper we show that the conjecture is true for $7\le \ell \le 9$.