# Given any polynomial p(x) over Z, can one construct a graph with characteristic polynomial p(x)?

Given any polynomial $p(x)$ over $\mathbb{Z}$, can one construct a graph with characteristic polynomial $p(x)$? [Edit: Title question added to post.}

Further questions include:

• Are there classes of graphs that correspond to different types of polynomials
(e.g., corresponding to polynomials over finite fields? Or perhaps corresponding to certain Galois extensions of $\mathbb{Q}$?)
• If we indeed can construct this, is the graph ever unique?
• If we can't make a graph for $p(x)$ exactly, can we at least make one where we know $p(x)$ divides the characteristic polynomial?

Thanks in advance for any insights.

-
For the first two bullet points, I'm not aware if graphs can be given some kind of characteristic polynomials over finite fields or other algebraic structures, but I do know that it's possible for different graphs to have the same characteristic polynomial. See mathworld.wolfram.com/CharacteristicPolynomial.html and search for "Characteristic polynomials are not diagnostic for graph isomorphism". Also, since the adjacency matrix has trace zero (assuming you aren't allowing loops), the polynomial will have no $x^{n-1}$ term (if it has $n$ vertices). –  anon Jul 4 '11 at 20:07
Non unicity of a graph given its characteristic polynomial is discussed in mathworld.wolfram.com/DeterminedbySpectrum.html . –  Joel Cohen Jul 4 '11 at 20:29

If we consider multigraphs -- i.e., graphs with multiple edges and possibly with loops -- then there are countably infinitely many graphs on $n$ vertices and countably infinitely many degree $n$ monic polynomials in $\mathbb{Z}[t]$, so there is more of a fighting chance that every such polynomial is the characteristic polynomial of some graph than in the situation described in Gerry Myerson's answer.

I can do the case of $1$ vertex: $t-n$ is the characteristic polynomial of a multigraph iff $n \geq 0$.

Moreover the non-negativity condition here is general: the Perron-Frobenius theorem asserts, in particular, that every matrix with non-negative real entries has at least one non-negative real eigenvalue.

There is a large literature on eigenvalues of (multi)graphs: spectral graph theory. I am not an expert on this (I don't even remember everything I used to know...), but there are entire texts written on the subject. Consulting one should give some idea of what is known.

-
I bet the two-vertex case can be done without over-exertion, and recommend that Alexander try it. –  Gerry Myerson Jul 5 '11 at 4:19

Let $n$ be a positive integer. Let $G$ be a graph with $n$ vertices. The adjacency matrix of $G$ is then an $n\times n$ matrix. Its characteristic polynomial is then of degree $n$. There are only finitely many graphs on $n$ vertices (up to isomorphism), but infinitely many polynomials of degree $n$ with integer coefficients. It follws that for most polynomials there is no graph for which that polynomial is the characteristic polynomial.

-