Preliminaries:
Let $K_n$ be the complete graph on $n$ vertices. $|E(K_n)|=\frac{n(n-1)}{2}$.
It's well known that the eigenvalues of $K_n$ are $n-1$ with multiplicity 1, and -1 with multiplicity $n-1$.
Let $E'=\{e_1,\ldots,e_l\}\subset E(K_n)$, where $l\leq \frac{n}{2}$
Let $G'$ be the graph obtain from $K_n$ in the following way:
-$V(G')=V(K_n)$
-$E(G')=E(K_n)-\{E'\}$
That means $G'$ is the graph obtained from $K_n$ by removing "relatively" small number of edges.
Question?
Is it possible to commute the spectrum of $G'$ if $E'$ satisfies certain conditions? for example one of the following:
-$E'$ is perfect matching of $K_n$
-$|E'|\leq 4$.
Is there any work in this direction?
Ideas:
-Since -1 is eigenvalue of $K_n$ with very high multiplicity (that is $n-1$), then I guess that by removing small number of edges from $K_n$, -1 will still be eigenvalue with high multiplicity
-Interlacing theorem could help in commutating the eigenvalues of $G'$.
Any idea will be useful!
Let $N(x)$ denote the neighbourhood of the vertex $x$ in the graph $G$ and suppose that $u$ and $v$ are distinct vertices of $G$ such that \[ {u} \cup N(u) = {v} \cup N(v). \] (We say that $u$ and $v$ have same closed neighbourhoods.) Let $f$ the vector indexed by $E(G)$ such that $f_u=1$ and $f_v=-1$ and $f_x=0$ if $x\ne u,v$. You may check that $f$ is an eigenvector of $A(G)$ with eigenvalue $-1$. If there are $k$ vertices such that any two have same closed neighbourhood, you may show that $-1$ is an eigenvalue with multiplicity at least $k-1$.