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.
$\begingroup$
$\endgroup$
5
-
6$\begingroup$ 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? $\endgroup$– Qiaochu YuanCommented Mar 16, 2010 at 16:01
-
$\begingroup$ (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.) $\endgroup$– Qiaochu YuanCommented Mar 16, 2010 at 16:56
-
$\begingroup$ 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. $\endgroup$– danCommented Mar 16, 2010 at 20:18
-
2$\begingroup$ 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). $\endgroup$– Kevin P. CostelloCommented Mar 16, 2010 at 23:05
-
4$\begingroup$ 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. $\endgroup$– Alon AmitCommented Mar 16, 2010 at 23:53
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
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.
answered Mar 17, 2010 at 2:11
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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!!!
$\begingroup$
$\endgroup$
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