Upper bounds of the second largest eigenvalue of graphs

Abstract

Let $\hat{I}{»}_i(G)$ denote the $i$-th largest eigenvalue of adjacency matrix of a graph $G$. Gerschgorin's Theorem indicates $\hat{I}{»}_1(G)$ belongs to the largest disk, i.e., $\hat{I}{»}_1(G)\le \hat{I}{”}_1(G)$, where $\hat{I}{”}_i(G)$ is the $i$-th largest degree of $G$. We show that $\hat{I}{»}_2(G)$ lies in the second largest disk. That is, in detail, $$\hat{I}{»}_2(G)<\hat{I}{”}_2(G)-\frac{1}{n^2}.$$ A classical theorem proved by Hong [\textit{Linear Algebra Appl.} 1988] states that $\hat{I}{»}_1(G)\le \sqrt{2m-n+1}$ for a connected graph $G$ with $n$ vertices and $m$ edges, where the equality holds if and only if $G$ is a star $S_n$ or a complete graph $K_n$. We give a refinement of Hong's theorem by showing $$\hat{I}{»}_1(G)<\sqrt{2m-n}$$ for any connected graph $G\notin \left\{S_n,S_{n-1}^1,K_n,K_{n-1}^1\right\}$. Based on this improved upper bound of $\hat{I}{»}_1(G)$, for a connected graph $G$ with $n$ vertices and $m$ edges, we are able to prove a sharp upper bound of $\hat{I}{»}_2(G)$ that $$\hat{I}{»}_2(G)\le \sqrt{m-\frac{n}{2}-\frac{1}{2}},$$ except $G$ is obtained from two disjoint $S_{\frac{n}{2}}$ by adding an edge between a pendant vertex of each star. Moreover, we provide a complete characterization to extremal graphs attaining the equality.