1 or -1 as an eigenvalue of graph 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?
 A: 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$
...
A: 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.
A: 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.
