Welcome to MathOverflow

Question

1

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.

flag	asked Mar 16 2010 at 15:51 dan 217●10

5

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

1

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

2

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

Chris Godsil · Answer 1 · 2010-03-17 02:11:55Z UTC

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.

Tomaž Pisanski · Answer 2 · 2010-03-17 06:59:05Z UTC

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.

Felix Goldberg · Answer 3 · 2012-03-27 12:46:51Z UTC

0

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.

answered Mar 27 2012 at 12:46

Felix Goldberg
2,363●4●12

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.