On the combinatorial structure of graphs with a spectral idempotent of small dual diameter

Abstract

Let $\Gamma$ be a connected regular graph with an eigenvalue $\lambda$ and corresponding idempotent $E_{\lambda }$. Let ${\mathcal{E}}_{\lambda }=⟨J,E_{\lambda }{⟩}^{\circ }$ be the algebra generated by $J$ and $E_{\lambda }$ with respect to the entrywise-Hadamard product, where $J$ is the all-$1$ matrix. We study the combinatorial structure of a graph $\Gamma$ for which ${\mathcal{E}}_{\lambda }$ has dimension $2$, giving a combinatorial characterization of such graphs in terms of equitable partitions. We present many examples and classify the distance-regular graphs with this property, as well as graphs that generate a $3$-class association scheme. We also study the graphs that have two eigenvalues $\lambda$ for which $\dim ({\mathcal{E}}_{\lambda })=2$ and determine all such graphs with four distinct eigenvalues.