How can I prove that a particular family of graphs is integral?

Question

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. As another example, $G_{2,k} \cong K_{2k}$.

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.

Answer 1

$\def\CC{\mathbb{C}}$The specturm is integral.

The following trick is very useful in computing spectra of highly symmetric graphs. Let $G$ be a finite graph, let $\Gamma$ be a group of symmetries of $G$, and let $V$ be the set of vertices of $G$. Let $A$ be the adjacency matrix, so $A : \CC^V \to \CC^V$. Then $A$ commutes with the action of $\Gamma$ on $\CC^V$. Therefore, if $\CC^V = \bigoplus W_i$ is the decomposition of $\CC^V$ into isotypic summands, then the spectrum of $A$ is the disjoint union of the spectra of $A$ restricted to the $W_i$.

In our case, we'll take $\Gamma = (\mathbb{Z}/k)^n$. For $(g_1, \ldots, g_n) \in \Gamma$ and $(x_1, \ldots, x_n)$ in $G_{n,k}$, we have $\left( (g_1, \ldots, g_n) \ast (x_1, \ldots, x_n) \right)_j = 0$ if $x_j=0$ and $\left( (g_1, \ldots, g_n) \ast (x_1, \ldots, x_n) \right)_j = g_j+x_j \bmod k$ if $x_j \neq 0$.

Let $\chi: (g_1, \ldots, g_n) \mapsto \exp(\frac{2 \pi i}{k} \sum g_i c_i)$ be a character of $\Gamma$, where the $c_i$ in $\mathbb{Z}/k$. We will compute the action of $A$ on the corresponding eigenspace of $\CC^V$.

Reorder the coordinates so that $c_1=c_2=\cdots=c_j=0$ and the other $c_i$ are not $0$. The corresponding eigenspace has dimension $j$: For $1 \leq r \leq j$, there is a one dimensional space of functions in $\CC^V$ which transform by this character and have the $0$ entry in position $r$.

I get that $A$ acts on this $j$ dimensional eigenspace by the matrix whose diagonal entries are $(j-1) (k-1) + (n-j) (-1)= jk -k-n+1$ and whose off diagonal entries are $k$. This matrix has one eigenvalue of $2jk - 2k+n+1$ and all the others are $jk-2k+n+1$. In particular, they are integers.

Answer 2

As a service, here is a sage program.

def G(n, k): """ Mathoverflow Question 159022 """ vertices = Words(range(k + 1), n) vertices = [w for w in vertices if w.count(ZZ(0)) == 1] def edge_func(w, v): if len([i for i in range(n) if w[i] != v[i]]) == 1: return True wi = w.find(Word([0])) vi = v.find(Word([0])) if wi == vi: return False return all(w[i] == v[i] for i in range(n) if i != wi and i != vi) return Graph([vertices, edge_func])

Answer 3

Since your graph has a rather large symmetry group, I am guessing you can mimic the computation in this short paper. (I. Rivin; simplices and spectra of graphs)