# Properties of Graphs with an eigenvalue of -1 (adjacency matrix)?

I am wondering if there are special classes of graphs that have eigenvalue of -1 for the adjacency matrix. I know that the complete graphs, Kn, have this property, but am wondering if other graphs do as well.

-
I think this question as stated is too general. Many, many graphs have eigenvalue -1. (In fact, specify all but one row of the adjacency matrix and I can modify the last row such that the resulting directed graph has eigenvalue -1.) Can you be more specific about what you're looking for? –  Qiaochu Yuan Mar 16 '10 at 16:01
(My previous claim comes with the small caveat that, if all but the last row has been specified, the entries in the last column cannot all be equal to zero.) –  Qiaochu Yuan Mar 16 '10 at 16:56
Thanks for the reply. I am wondering if there are certain classes of graphs with this property. For example, the complete graph is a regular graph, but I do not believe all regular graphs have eigenvalue at -1. I know that bipartite graphs will have eigenvalues symmetric about the origin, but am unsure if there are any additional "special" properties such that they have an eigenvalue at -1. Maybe the question is too general. I really am just curious about graphs with this property. –  dan Mar 16 '10 at 20:18
One simple class of graphs with the property: Any graph with two adjacent vertices $x$ and $y$ whose neighborhoods are (except for $x$ and $y$ themselves) identical. This includes $K_n$, but is not the only type of example (the cycle of length $3k$ also has this property). –  Kevin P. Costello Mar 16 '10 at 23:05
If G->B is a covering map (in the topological sense), then G inherits all the eigenvalues of B (just choose an eigenfunction that is uniform on the fibers). So, for instance, any graph which covers K_n for any n has -1 as an eigenvalue. The cycle of length 3k covers the triangle, which is another way to explain Kevin's example. –  Alon Amit Mar 16 '10 at 23:53

Despite a lot of effort, there's no interesting characterization of graphs with 0 as an eigenvalue. I do not think as much attention has been paid to $-1$, but I'd be surprised if anything useful could be said. The two problems are not unrelated: for example if $G$ is regular then it has $-1$ as an eigenvalue if and only if its complement has zero as an eigenvalue. (If $G$ has $-1$ as an eigenvalue with multiplicity at least two, then its complement has 0 as an eigenvalue by interlacing.

-

Maybe you should ask which of the eigenvalues should have value -1. For instance when Patrick Fowler and I explored the middle eigenvalue $\lambda_n$ in the decreasing sequence of eigenvalues of a graph on $2n$ vertices, we observed that the value $1/\phi$ occurs quite frequently. We called such graphs golden graphs, since $\phi$ is the golden ratio.

-

Another class of graphs with $-1$ as an eigenvalue are the bipartite generalized Petersen Graphs. This includes the Desargues graph and the dodecahedron. All generalized Petersen Graphs have $1$ as an eigenvalue, so their bipartite doubles have $-1$ as an eigenvalue. The definition can be found in Bollobas's Extremal Graph Theory. You can see the generalized Petersen graphs have 1 as an eigenvalue by assigning 1 to the "outer" cycle and $-1$ to the other cycle to obtain an eigenvector with eigenvalue 1.

-

There are a lot of graphs with this property. I just introduce two classes that are very famous:

The Friendship graph $F_n$ that is $K_1\nabla nK_2$, where $\nabla$ means the join of two graphs. These graphs has $n-1$ eigenvalue $-1$.

The second class is graph $K_n$ that is removed $1,2,3$ or $4$ edges from it. So, this class contain also five different classes!!!

-

There is another interesting class (although it's probably a bit esoteric): graphs with a perfect 1-code. This is shown in Lemma 9.3.4 of Algebraic Graph Theory by Godsil & Royle.

-