5
$\begingroup$

We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of $\{0,1,\dots,k-1\}^n$, and $\sigma_1\cdots \sigma_n$ is connected to $\tau_1\cdots \tau_{n}$ if and only if $\sigma_i=\tau_{i+1}$ for every $i=1,\dots,n-1$.

We would like to calculate the spectrum of the Laplacian matrix of $DB(n,k)$. Note that since $DB(n,k)$ is $k$-regular, then $\lambda \in Spec(L_{DB(n,k)})$ if and only if $k-\lambda \in Spec(A_{DB(n,k)})$, so we can calculate the eigenvalues of the Laplacian matrix from the eigenvalues of the Adjacency matrix.

We found the following article on the subject, but it only calculates the spectrum of the underlining undirected graph of the De Bruijn graph:

https://core.ac.uk/download/pdf/82810454.pdf

Thanks!

$\endgroup$
5
$\begingroup$

The computation for $k=2$ appears (among other places) on pp. 158--159 of my book Algebraic Combinatorics, second edition. The computation for arbitrary $k$ is completely analogous. Dima Pasechnik is correct that there is one eigenvalue equal to 0, and all the others are equal to $k$.

$\endgroup$
4
$\begingroup$

I believe that for $p$ prime $DB(m,p)$ has one 0 eigenvalue (this is easy to check), and the other eigenvalues are all equal to $p$. This is something that we observed while working on https://arxiv.org/abs/1405.0113, but didn't try to prove (should not be too hard I guess, using a decription of $DB(m,p)$ as the line graph of $DB(m-1,p)$, and then induction).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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