I'm working with an infinite family of graphs that seems to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them as follows:

For $n, k>1$, the vertices are sequences of length $n$ with exactly one $0$ and the remaining terms taken from $1, 2, \dots, k$. $G_{n,k}$ thus has $nk^{n-1}$ vertices.

There are two ways vertices $x$ and $y$ can be adjacent:

• If they differ in exactly one term
• For $i \ne j$, if $x_i=y_j=0$, then $x_k=y_k$ for all $k \ne i,j$

An an example, here's a picture of the graph $G_{3,2}$:

A counting argument will show that $G_{n,k}$ is $(n-1)(2k-1)$-regular.

I've looked at over a dozen examples with various small choices for $n$ and $k$ and the eigenvalues (found using Matlab) have always followed these patterns:

• There will be $\lceil \frac{3n-2}{2} \rceil$ distinct eigenvalues
• The maximum eigenvalue will be $(n-1)(2k-1)$, then there will be $\lceil \frac{n-1}{2} \rceil$ jumps of size $2k$ between the next biggest distinct eigenvalues, then jumps of size $k$ down to the smallest eigenvalue of $1-n$.

For example, the eigenvalues of $G_{3,2}$ are $6, 2^{(3)}, 0^{(2)}, -2^{(6)}$.

I've read a few papers on families of integral graphs and it seems like you need a good understanding of the structure of the graphs or their adjacency matrices to show that they are integral. So in this case, is the definition of the graphs alone enough to understand why they might be integral? Are there techniques I can use to try to prove integrality?

Thank you.