Graphs with rational eigenvalues

Question

Let $A$ be the adjacency matrix of a graph with eigenvalues $\lambda_i$. My questions are:

• Is there any assumption/conditions for a graph to have all rational eigenvalues ($\lambda_i \in \mathbb{Q} \;\forall i$)?

• Could you introduce graphs which can satisfy the above condition? (You may say about a specific application)

Of course, you may consider the case all eigenvalues are integers. Any discussion on the topic above is useful.

---

The question is edited based on the nice comment of @ChrisGodsil.

Answer 1

There exist lots of easy examples, even looking only at integers :

• Complete graph $K_n$ with eigenvalues $\{(n-1)^1,-1^{n-1}\}$
• Complete bipartite graphs $K_{m,n}$ have spectrum $\{\pm \sqrt{mn},0^{n+m-2}\}$. With appropriate values for $m$ $n$ you can have integers values
• The cycle graph $C_n$ has spectrum $\{2cos\frac{2k\pi}{n},k=0,\ldots,n-1\}$ so that $C_3$, $C_4$ and $C_6$ have integer eigenvalues
• The petersen graph has eigenvalues $\{3,1^5,-2^4\}$

However, I doubt that you can find general result for graph with rational eigenvalues. This is because it is very to build such a graph. If a graph $G$ have $\lambda_i$ for eigenvalues, then :

1. If $G$ is regular, its complement its also regular, and the other eigenvalues are $-1-\lambda_i$
2. If $G$ is $r$-regular with characteristic polynomial $\phi(G,x)$, then its line graph has for characteristic polynomial $$\phi(L(G),x)=(x+2)^{m-n}\phi(G,x+2-r)$$ so that its eigenvalues are also integers

But more importantly perhaps, if you have two graphs $G$ and $H$ with eigenvalues $\lambda_i$ and $\mu_j$, then their cartesian product $G\times H$ has eigenvalues $\lambda_i + \mu_j$. It is therefore quite easy to build a graph with integer eigenvalues.

I might be wrong, I never looked at the actual problem. This is only my (strong) intuition.

Answer 2

Given an adjacency matrix $A$, the characteristic polynomial of $A$ will always have leading coefficient $1$, and in particular its roots will be algebraic integers. Hence if an eigenvalue $\lambda$ of $A$ satisfies $\lambda \in \mathbb{Q}$, then necessarily $\lambda \in \mathbb{Z}$, as the rational algebraic integers are precisely the integers. So your question is really about graphs with integer eigenvalues.

These are called integral graphs. The problem of characterising precisely which graphs are integral is incredibly difficult, and wide open -- it was first raised in 1974 by Harary and Schwenk in [Harary, Frank; Schwenk, Allen J. Which graphs have integral spectra? Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), pp. 45–51. Lecture Notes in Math., Vol. 406, Springer, Berlin, 1974.].

They note that the problem seems very intractable. Some good surveys on the topic exist -- see for example the survey by Wang or Balińska et al.