2
$\begingroup$

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.

  • 0
    Non unicit$y$ of a graph given its characteristic pol$y$nomial is discussed in http://mathworld.wolfram.com/DeterminedbySpectrum.html .2011-07-04

2 Answers 2

5

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.

  • 0
    I bet the two-vertex case can be done without over-exertion, and recommend that Alexander try it.2011-07-05
4

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.