On strong nodal domains for eigenfunctions of Hamming graphs

The Laplacian matrix of the $n$-dimensional hypercube has $n+1$ distinct eigenvalues $2i$, where $0\le i\le n$. In 2004, Bıyıkoğlu, Hordijk, Leydold, Pisanski and Stadler initiated the study of eigenfunctions of hypercubes with the minimum number of weak and strong nodal domains. In particular, they proved that for every $1\le i\le \frac{n}{2}$ there is an eigenfunction of the hypercube with eigenvalue $2i$ that have exactly two strong nodal domains. Based on computational experiments, they conjectured that the result also holds for all $1\le i\le n-2$. In this work, we confirm their conjecture for $i\le \frac{2}{3}(n-\frac{1}{2})$ if $i$ is odd and for $i\le \frac{2}{3}(n-1)$ if $i$ is even. We also consider this problem for the Hamming graph $H(n,q)$, $q\ge 3$ (for $q=2$, this graph coincides with the $n$-dimensional hypercube), and obtain even stronger results for all $q\ge 3$.