4
$\begingroup$

The eigenvalues associated to a graph's adjacency matrix are necessarily algebraic integers, because the adjacency matrix itself is entirely integer. I'm curious as to whether it's possible to have all irrational eigenvalues $\lambda$ simultaneously obey $\lambda > 1$. This is not possible for all eigenvalues, as the trace is zero, so there must be negative eigenvalues. There are many graphs whose integer eigenvalues are all negative, so intuitively we might feel that if we put enough negative integers in the spectrum, then we could a significant positive set of algebraic integers all conjugate to each other. The "obstruction" is that these would then need to have a norm that's a significantly large integer, and it's difficult to find these.

A natural starting place to look, perhaps, would be for a graph that has $x^2-5x+5$ as one of the factors of its characteristic polynomial.

I'm sorry if many of these statements are somewhat elementary, I'm just trying to provide the little ideas I have on the question. I couldn't find anything elsewhere online.

$\endgroup$
  • $\begingroup$ A graph with all eigenvalues integral will satisfy this vacuously. I presume you want to assume at least one eigenvalue is irrational? $\endgroup$ – Wojowu Feb 7 at 11:26
  • $\begingroup$ Yes, my mistake. I will clarify in the title. $\endgroup$ – Alex Meiburg Feb 7 at 11:34
8
$\begingroup$

Yes, the graph with adjacency matrix

 0     0     1     0     1     1     1     1
 0     0     0     1     0     0     0     1
 1     0     0     0     1     1     1     1
 0     1     0     0     0     0     0     0
 1     0     1     0     0     1     1     1
 1     0     1     0     1     0     1     1
 1     0     1     0     1     1     0     0
 1     1     1     0     1     1     0     0 

and graph6 string

GQil^W

is such a graph, as the characteristic polynomial is $x(x+2)(x+1)^4(x^2-6x+6)$, and the two roots of $(x^2-6x+6)$ are both larger than $1$.

$\endgroup$
  • $\begingroup$ yep, I can confirm it's a good example :-) $\endgroup$ – Dima Pasechnik Feb 7 at 12:00
  • $\begingroup$ Lovely, thank you! Did you have a system to find or construct this graph? Some sort of modified companion matrix or something? $\endgroup$ – Alex Meiburg Feb 7 at 12:30
  • 2
    $\begingroup$ @AlexMeiburg The graphs are generated by geng. For precomputed graphs, one can also use the House of Graphs collection. $\endgroup$ – Bullet51 Feb 7 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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