MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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 2010 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 2010 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 2010 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 2010 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 2010 at 23:53

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.

-

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.

-

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.

-