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.



Factorization of the characteristic polynomial of the adjacency matrix of a graph
Expanding on Richard's comment: let me rename your graph to $S$ and consider the adjacency matrix $A$ abstractly as a linear operator acting on the free vector space $\mathbb{C}[S]$ on (the vertices of) $S$, and let $G$ be its automorphism group (this is why I wanted a new name). Then $\mathbb{C}[S]$ is a completely reducible representation of $G$ and $A$ is an endomorphism of this representation. Hence if we write


$$\mathbb{C}[S] \cong \bigoplus\_i n\_i V\_i$$


where $V\_i$ are the irreducibles, then $A$ is an element of the endomorphism algebra


$$\text{End}\_G(\mathbb{C}[S]) \cong \prod\_i M\_{n\_i}(\mathbb{C}).$$


This means more explicitly that $A$ is conjugate over $\mathbb{C}$ to a block diagonal matrix with a block for each isotypic component (hence its characteristic polynomial factors accordingly). In the nicest possible case the decomposition above is multiplicity-free in which case the endomorphism algebra is a product of copies of $\mathbb{C}$ and we just have that $A$ must act by a scalar $\lambda\_i$ on each $V\_i$ that occurs in the decomposition, which contributes a multiplicity of $\dim V\_i$ to $\lambda\_i$ as a root of the characteristic polynomial and hence, over $\mathbb{Q}$, contributes a multiplicity of $\dim V\_i$ to the minimal polynomial of $\lambda\_i$ as a factor of the characteristic polynomial.


(I think the result of this analysis comes out the same if you work over $\mathbb{Q}$ from the beginning but it's more annoying to describe.)


I work through a few examples of this in my old blog post [The Schrodinger equation on a finite graph](https://qchu.wordpress.com/2011/01/02/the-schrodinger-equation-on-a-finite-graph/), where I was trying to understand via a toy model the quantum mechanical phenomenon of group symmetries introducing "degeneracies," which is physics speak for eigenvalues (of the Hamiltonian in this case) of multiplicity greater than $1$.


The "most degenerate" case is the complete graph $S = K\_n$, where $G = S\_n$ and the corresponding representation is a copy of the trivial representation and an irreducible representation of degree $n-1$. This means the adjacency matrix $A$ must have at most two eigenvalues, one with multiplicity $1$ and one with multiplicity $n-1$, which turn out to be $n-1$ and $-1$ respectively (this is easily computed by computing $\text{tr}(A)$ and $\text{tr}(A^2)$, or just finding all the eigenvectors of $A + I$), inducing a factorization


$$\det (tI - A) = (t - n + 1)(t + 1)^{n-1}$$


with a factor of multiplicity $n-1$.


One of the "least degenerate" cases where the automorphism group still acts transitively on vertices is $S = C\_n$ the cycle graph, where $G = D\_n$ is the dihedral group and the corresponding representation splits up into mostly $2$-dimensional irreps. This reflects the fairly mild degeneracies of the eigenvalues of the adjacency matrix, which are $2 \cos \frac{2\pi k}{n}, k = 0, \dots n-1$, and/but which also organize themselves into nontrivial Galois orbits coming from the action of the Galois group of $\mathbb{Q}(\zeta\_n)$.


