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

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?

share|improve this question
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 –  Chris Godsil Oct 18 '12 at 11:17
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. –  Brendan McKay Oct 18 '12 at 11:42
Many thanks for your answers. Yes, it is cayley graph, and it is too large. –  Moh514 Oct 18 '12 at 20:10
Tell us more about the graph and group. Are there elements of low order? What is their action on the group like? –  Aaron Meyerowitz Oct 19 '12 at 0:37
What is "too large"? There are some pretty good packages out there. –  Gordon Royle Oct 19 '12 at 0:46
show 1 more comment

3 Answers

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.






share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer


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.