New bounds on the spectral radius of graphs based on the moment problem

Abstract

Let $\mathcal{G}$ be an undirected graph with adjacency matrix $A$ and spectral radius $\rho$. Let $w_k,{\varphi }_k$ and ${\varphi }_k^{(i)}$ be, respectively, the number walks of length $k$, closed walks of length $k$ and closed walks starting and ending at vertex $i$ after $k$ steps. In this paper, we propose a measure-theoretic framework which allows us to relate walks in a graph with its spectral properties. In particular, we show that $w_k,{\varphi }_k$ and ${\varphi }_k^{(i)}$ can be interpreted as the moments of three different measures, all of them supported on the spectrum of $A$. Building on this interpretation, we leverage results from the classical moment problem to formulate a hierarchy of new lower and upper bounds on $\rho$, as well as provide alternative proofs to several well-known bounds in the literature.