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.

  • 2
    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 http://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).2011-07-04
  • 0
    Non unicity of a graph given its characteristic polynomial 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.