Skip to main content
2 of 2
edited tags; edited title
M. Winter
  • 13.6k
  • 3
  • 29
  • 70

Factorization of the characteristic polynomial of the adjacency matrix of a graph

Let $G$ be a regular graph of valence $d$ with finitely many vertices, let $A_G$ be its adjacency matrix, and let $$P_G(X)=\det(X-A_G)\in\mathbb{Z}[X]$$ be the adjacency polynomial of $G$, i.e., the characteristic polynomial of $A_G$. In some graphs that came up in my work, the adjacency polynomials $P_G(X)$ have a lot of factors in $\mathbb Z[X]$, many of them repeated factors. So my questions are:

  1. Is it common for the adjacency polynomial of a regular graph to be highly factorizable in $\mathbb Z[X]$, and to have many repeated factors?

  2. If not, what are the graph-theoretic consequences of having many small-degree factors?

  3. If not, what are the graph-theoretic consequences of having factors appearing to power greater than 1?

To give an idea of the numbers involved, one example was a connected 3-regular graph with 64 vertices, and $$ P_G(X) = (x - 3)x^{3}(x + 1)^{3}(x^2 - 3 x + 1)^{3}(x^2 - x - 3)^{3}(x^2 - x - 1)^{6} (x^2 + x - 3)^{3}(x^3 - 3 x^2 - x + 4)^{2}(x^3 - 4 x + 1) (x^6 - x^5 - 11 x^4 + 9 x^3 + 31 x^2 - 19 x - 8)^{3} $$

I've looked at a couple of references and tried a Google search, but didn't find anything relevant.

Joe Silverman
  • 47.4k
  • 2
  • 149
  • 241