Equitable 2-partitions of the Hamming graphs with the second eigenvalue

Abstract

The eigenvalues of the Hamming graph $H(n,q)$ are known to be ${\lambda }_i(n,q)=(q-1)n-qi$, $0\le i\le n$. The characterization of equitable 2-partitions of the Hamming graphs $H(n,q)$ with eigenvalue ${\lambda }_1(n,q)$ was obtained by Meyerowitz in [15]. We study the equitable 2-partitions of $H(n,q)$ with eigenvalue ${\lambda }_2(n,q)$. We show that these partitions are reduced to equitable 2-partitions of $H(3,q)$ with eigenvalue ${\lambda }_2(3,q)$ with exception of two constructions.