The Sharp Upper Bounds for the Median Eigenvalues of Graphs

Abstract

Let ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$ be the eigenvalues of a simple graph $G$ of order $n$. The HL-index of $G$ is defined by $R(G)=\max \Vert {\lambda }_h|,|{\lambda }_{\ell }|\}$ with $h=\lfloor (n+1)/2\rfloor$ and $\ell =\lceil (n+1)/2\rceil$.In this paper, we prove that if $G$ is $K_4$-minor-free or $K_{2,3}$-minor-free, then $R(G)\le \sqrt{5}-1$ with equality attained by an infinite family of outerplanar graphs.Moreover, we show that $R(G)\le \sqrt{d-2}$ for triangle-free graphs with maximum degree at most $d$ and average degree at most $(d-2)(d^2-2d+2)/(d^2-3d+5)$.

15 pages, 1 figure