I have a regular and arc transitive graph which I think that either 1 or -1 is an eigenvalues of adjacency matrix of this graph. How can I prove it? Is there any classification of graphs which have 1 or -1 as an eigenvalue? Is there any paper related to this problem?
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ The simplest way to show that some number is an eigenvalue is to produce the eigenvector. The second-simplest, if you have the adjacency matrix, is to stuff it into something like sage and compute the factored characteristic polynomial. If you graph is given as a Cayley graph (for example) and is too large for the above strategies, you may be out of luck because then your problem is NP-hard $\endgroup$– Chris GodsilCommented Oct 18, 2012 at 11:17
-
1$\begingroup$ To continue Chris's comment, if you compute the eigenvector of $\pm 1$ in some small examples, you might see a pattern that you can generalize. Note that an eigenvector permuted according to a group element is also an eigenvector, so probably there will be an eigenvector with not many different entry values. Perhaps one which is constant on the blocks of a block system of the group. $\endgroup$– Brendan McKayCommented Oct 18, 2012 at 11:42
-
$\begingroup$ Many thanks for your answers. Yes, it is cayley graph, and it is too large. $\endgroup$– Moh514Commented Oct 18, 2012 at 20:10
-
$\begingroup$ Tell us more about the graph and group. Are there elements of low order? What is their action on the group like? $\endgroup$– Aaron MeyerowitzCommented Oct 19, 2012 at 0:37
-
$\begingroup$ What is "too large"? There are some pretty good packages out there. $\endgroup$– Gordon RoyleCommented Oct 19, 2012 at 0:46
|
Show 1 more comment
3 Answers
$\begingroup$
$\endgroup$
The paper Babai, László. Spectra of Cayley graphs. J. Combin. Theory Ser. B 27 (1979), no. 2, 180–189 gives a "formula" for the eigenvalues $\lambda_k$ of the Cayley graphs: a Vandermonde system of equations, as below, with right-hand sides $r_t$ dependent on values of the irreducible characters of the group on the generators of the Cayley graph.
$\lambda_1+...+\lambda_k=r_1$
$\lambda_1^2+...+\lambda_k^2=r_2$
...
$\lambda_1^t+...+\lambda_k^t=r_t$
...
answered Nov 2, 2012 at 8:52
$\begingroup$
$\endgroup$
0
first (trivial) answer: the spectrum of a bipartite graph is symmetric wrt to 0; hence, +1 is an eigenvalue iff -1 is an eigenvalue.
second (trivial) answer: an individual edge has eigenvalue +1 (and hence also -1).
further (much less trivial) answers: take a look at this article by chan and godsil, where several conditions answering your questions are presented, e.g. at page 76. in a slightly different version you can find on the internet (google is your friend), the same authors show that -1 is an eigenvalue if the graph has a perfect 1-code. also, in this monograph you can find some relevant information, e.g. the observation that +1 is an eigenvalue of so-called collinearity graphs.
$\begingroup$
$\endgroup$
If you only know that the graph is regular then the common degree is an eigenvalue with the all $1$'s vector as an eigenvector. Eigenvectors for any other eigenvalue have entries which add to $0$, but if regularity is all that you have, then it might be that I assure you (truthfully) that $1$ (or some other number) is an eigenvalue and even that it has a particularly simple eigenvector and yet it would be very hard for you to prove it.
If the graph has a particularly simple structure with high symmetry then it might be easy to find eigenvectors. Think of an eigenvector for $\lambda$ as a decoration of each vertex $u$ with a weight $w(u)$ so that the neighbors of $u$ have weights which add to $\lambda w(u).$ Call $u$ a $k$-vertex if $w(u)=k$
Negative Example Let me try to make a graph regular of degree $3$ with $1$ as a hidden eigenvalue. Here is a simple attempt with a slightly more complicated one at the end: Start with two groups of $m$ vertices labelled $1$ and $m$ labeled $-1$. Connect each one to two with the same label and one with the other (so cover each set with cycles of various sizes and have a random matching across.) I think that you might have a hard time finding my eigenvector (or any other for eigenvalue $1$), even If I gave you all the information above. You would just have to find the right split into two $m$ vertex halves but there are many possibilities. If I am wrong, then some similar flavor construction might be very hard. I give a more complicated one at the end.
Positive examples In the other direction let us think of some nice graphs which might have $1$ as an eigenvalue. What about a cycle? Maybe we could have entries $0,1,-1$ with each $0$-vertex connected to $[-1,1]$ and each $x$-vertex connected to $[0,x]$ for $x=\pm 1$. That is easy to acheive if there are $3m$ vertices. How about a cube? Maybe weights $1,-1$ with each $x$-vertex connected to $[x,x,-x].$ Also easy. Similar things can be attempted for other $3$-regular graphs with an even number of vertices. This is basically my negative example except that a graph automorphism might make a good split obvious.
Another attempt at a hidden eigenvector: I'll start with no edges but $2a+2b+2c$ decorated vertices: $a$ each $\pm 1$, $b$ each $\pm 3$, $c$ each $\pm 9.$ A $3$-vertex five possible neighbor configurations: $[1,1,1],[1,-1,3],[3,3,-3],[3,9,-9],[-3,-3,9]$. A $9$-vertex has four: $[1,-1,9],[3,-3,9],[9,9,-9],[3,3,3]$ and a $1$-vertex also has four: $[1,1,-1],[1,3,-3],[1,9,-9],[-1,-1,3].$ So throw in a healthy number of each with no apparent pattern. This can be done randomly then adjusted (if you fail, start over.) Or we could specify feasible counts for the $18$ or $36$ possible four vertex stars and work from there.
answered Oct 18, 2012 at 17:55