MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$: The case where n=3 and k=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.

share|cite|improve this question
Do the examples you've done help you guess the eigenvectors? – Alex Degtyarev Feb 28 '14 at 19:38
I haven't looked at eigenvectors yet - I'll start to do that and see if I can learn anything. – jamisans Feb 28 '14 at 19:52
Can you express them as smaller graphs with a given operation? For example are they ever Cartesian product graphs? Nice construction BTW. – Jernej Feb 28 '14 at 20:05
sage says that G(3,3), G(3,2), G(4,2), G(4,3) and G(3,4) are not Cartesian products. And also that G(3,3), G(3,4) and G(3,5) are also line graphs. – F. C. Feb 28 '14 at 21:41
It appears that all the graphs are vertex-transitive. If this is indeed so you could try to apply the results from or even – Jernej Feb 28 '14 at 22:35
up vote 14 down vote accepted

$\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.

share|cite|improve this answer

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])

share|cite|improve this answer

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)

share|cite|improve this answer

Your Answer


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.