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:
That means $G'$ is the graph obtained from $K_n$ by removing "relatively" small number of edges.

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?

-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$.

  • $\begingroup$ Could you give me hint why the multiplicity of $-1$ is $k-1$? Please tell me if this is correct: Suppose that $N(u)=N(v)$ and let $f$ be the same vertor you described, then $f$ is eigenvector of $A(G)$ with eigenvector $0$. If there are $k$ vertices such that any two vertex have the same neighbour, then $0$ is an eigenvalue with multiplicity $k-1$. $\endgroup$ – M.Badaoui Apr 20 '16 at 13:56
  • 1
    $\begingroup$ @M.Badoui: Fix one vertex, call it $u$. For each vertex $v$ with the same closed neighborhood as $u$, construct an eigenvector $F_v$ as above. This gives us $k-1$ eigenvectors, each of which has only two non-zero entries. Since one of these non-zero entries is index by $u$, it's not hard to show that our $k-1$ vectors are linearly independent. $\endgroup$ – Chris Godsil Apr 20 '16 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.