13
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Do the examples you've done help you guess the eigenvectors? $\endgroup$ Feb 28, 2014 at 19:38
  • $\begingroup$ I haven't looked at eigenvectors yet - I'll start to do that and see if I can learn anything. $\endgroup$
    – jamisans
    Feb 28, 2014 at 19:52
  • $\begingroup$ Can you express them as smaller graphs with a given operation? For example are they ever Cartesian product graphs? Nice construction BTW. $\endgroup$
    – Jernej
    Feb 28, 2014 at 20:05
  • 2
    $\begingroup$ 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. $\endgroup$
    – F. C.
    Feb 28, 2014 at 21:41
  • 1
    $\begingroup$ It appears that all the graphs are vertex-transitive. If this is indeed so you could try to apply the results from link.springer.com/article/10.1007%2FBF02018821#page-1 or even sciencedirect.com/science/article/pii/0095895679900790 $\endgroup$
    – Jernej
    Feb 28, 2014 at 22:35

3 Answers 3

15
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.