Note on the sum of the smallest and largest eigenvalues of a triangle-free graph

Abstract

Let $G$ be a triangle-free graph on $n$ vertices with adjacency matrix eigenvalues ${\mu }_1(G)\ge {\mu }_2(G)\ge \cdots \ge {\mu }_n(G)$. In this paper we study the quantity $${\mu }_1(G)+{\mu }_n(G).$$ We prove that for any triangle-free graph $G$ we have $${\mu }_1(G)+{\mu }_n(G)\le (3-2\sqrt{2})n.$$ This was proved for regular graphs by Brandt, we show that the condition on regularity is not necessary. We also prove that among triangle-free strongly regular graphs the Higman-Sims graph achieves the maximum of $$\frac{{\mu }_1(G)+{\mu }_n(G)}{n}.$$

5 pages