Median eigenvalues of bipartite graphs

Abstract

For a graph $G$ of order $n$ and with eigenvalues ${\lambda }_1⩾\cdots ⩾{\lambda }_n$, the HL-index $R(G)$ is defined as $R(G)=\max \left\{|{\lambda }_{\lfloor (n+1)/2\rfloor }|,|{\lambda }_{\lceil (n+1)/2\rceil }|\right\}.$ We show that for every connected bipartite graph $G$ with maximum degree $\Delta ⩾3$, $R(G)⩽\sqrt{\Delta -2}$ unless $G$ is the the incidence graph of a projective plane of order $\Delta -1$. We also present an approach through graph covering to construct infinite families of bipartite graphs with large HL-index.

References in corpus (1)

• Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem