Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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 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

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.