Which algebraic real numbers are eigenvalues of a finite graph?

Question

Since the adjacency matrix of a finite graph has integer entries, its eigenvalues are algebraic. Since the adjacency matrix is also symmetric, the eigenvalues are all real. Can all algebraic real numbers be produced by this way? Or are there algebraic numbers which are not realized as any of the eigenvalues of the adjacency matrix of any finite graph?

Answer 1

If a real algebraic integer $\alpha$ is an eigenvalue of a symmetric adjacency matrix $A$, all its conjugates must also be eigenvalues of $A$, so a necessary condition is that all of the conjugates of $\alpha$ must be real. So, for example, $\alpha = \sqrt[3]{2}$, whose conjugates are $\sqrt[3]{2} \omega$ and $\sqrt[3]{2} \omega^2$, is not such an algebraic integer.

If we want to characterize which sets of eigenvalues $\alpha_1, \dots \alpha_k$ can occur (and not just which individual eigenvalues) then a stronger necessary condition is that

$$\text{tr}(A^n) = \sum_{i=1}^k \alpha_i^n \ge 0$$

for all $n$; these traces count closed walks on the corresponding graph. Actually we must also have the more complicated condition

$$\frac{1}{n} \sum_{d \mid n} \mu(d) \text{tr}(A^{n/d}) \ge 0$$

where these numbers count aperiodic closed walks. Some years ago I asked on MO whether this necessary condition characterizes eigenvalues of the adjacency matrices of directed multigraphs (equialently, matrices with non-negative integer entries, not necessarily symmetric) and the answer turns out to be yes. That paper references other papers addressing the question for non-negative symmetric matrices but seems to imply that the question is open in general.

Answer 2

See Salez: https://arxiv.org/abs/1302.4423: an algebraic integer is an eigenvalue of a graph if and only if it, and all its conjugates, are real. (Equivalently all roots of its minimal polynomial are real.)

This was first proved by Estes (see the references in the cited paper). Salez actually proves that a totally real algebraic integer is an eigenvalue of a tree.