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.