Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
6  
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
2  
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
4  
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

5 Answers 5

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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!!!

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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