Properties of Graphs with an eigenvalue of -1 (adjacency matrix)? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T23:54:22Z http://mathoverflow.net/feeds/question/18389 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18389/properties-of-graphs-with-an-eigenvalue-of-1-adjacency-matrix Properties of Graphs with an eigenvalue of -1 (adjacency matrix)? dan 2010-03-16T15:51:09Z 2012-03-27T12:46:51Z <p>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.</p> http://mathoverflow.net/questions/18389/properties-of-graphs-with-an-eigenvalue-of-1-adjacency-matrix/18456#18456 Answer by Chris Godsil for Properties of Graphs with an eigenvalue of -1 (adjacency matrix)? Chris Godsil 2010-03-17T02:11:55Z 2010-03-17T02:11:55Z <p>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.</p> http://mathoverflow.net/questions/18389/properties-of-graphs-with-an-eigenvalue-of-1-adjacency-matrix/18468#18468 Answer by Tomaž Pisanski for Properties of Graphs with an eigenvalue of -1 (adjacency matrix)? Tomaž Pisanski 2010-03-17T06:59:05Z 2010-03-17T06:59:05Z <p>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 <strong>golden</strong> graphs, since $\phi$ is the golden ratio.</p> http://mathoverflow.net/questions/18389/properties-of-graphs-with-an-eigenvalue-of-1-adjacency-matrix/92370#92370 Answer by Felix Goldberg for Properties of Graphs with an eigenvalue of -1 (adjacency matrix)? Felix Goldberg 2012-03-27T12:46:51Z 2012-03-27T12:46:51Z <p>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 &amp; Royle.</p>