Welcome to MathOverflow

Question

2

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?

flag	asked Oct 18 at 5:36 Mohsen 189●6

2

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 at 11:17

1

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 at 11:42

Many thanks for your answers. Yes, it is cayley graph, and it is too large. – Mohsen Oct 18 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 at 0:37

What is "too large"? There are some pretty good packages out there. – gordon-royle Oct 19 at 0:46

show 1 more comment

Delio Mugnolo · Answer 1 · 2012-10-18 08:44:22Z UTC

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.

Aaron Meyerowitz · Answer 2 · 2012-10-18 17:55:00Z UTC

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.

Dima Pasechnik · Answer 3 · 2012-11-02 08:52:02Z UTC

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$

...

1 or -1 as an eigenvalue of graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.