2
$\begingroup$

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?

$\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$ 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$ Oct 18, 2012 at 11:42
  • $\begingroup$ Many thanks for your answers. Yes, it is cayley graph, and it is too large. $\endgroup$
    – Moh514
    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$ Oct 19, 2012 at 0:37
  • $\begingroup$ What is "too large"? There are some pretty good packages out there. $\endgroup$ Oct 19, 2012 at 0:46

3 Answers 3

4
$\begingroup$

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$

...

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.