Spectral moments of trees with given degree sequence

Abstract

Let ${\lambda }_1,\dots ,{\lambda }_n$ be the eigenvalues of a graph $G$. For any $k\ge 0$, the $k$-th spectral moment of $G$ is defined by $\M_k(G)=λ_1^k+\dots+λ_n^k$. We use the fact that $\M_k(G)$ is also the number of closed walks of length $k$ in $G$ to show that among trees $T$ whose degree sequence is $D$ or majorized by $D$, $\M_k(T)$ is maximized by the greedy tree with degree sequence $D$ (constructed by assigning the highest degree in $D$ to the root, the second-, third-, \dots highest degrees to the neighbors of the root, and so on) for any $k\ge 0$. Several corollaries follow, in particular a conjecture of Ilić and Stevanović on trees with given maximum degree, which in turn implies a conjecture of Gutman, Furtula, Marković and Glišić on the Estrada index of such trees, which is defined as $\EE(G)=e^{λ_1}+\dots+e^{λ_n}$.

24 pages 5 figures

References in corpus (1)

• Trees with given degree sequences that have minimal subtrees