Spectral moments of trees with given degree sequence

2013/04/17 by Andriantiana, Eric Ould Dadah, Wagner, Stephan · 2 citations
#05C05 #05C35 #05C50 #68R05 #Combinatorics (math.CO) #FOS: Mathematics #G.2.1 #G.2.2

paper · doi:10.48550/arxiv.1304.4696

Abstract

Let λ₁,…,λ_n be the eigenvalues of a graph G. For any k≥ 0, the k-th spectral moment of G is defined by \M_k(G)=λ₁^k+…+λ_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-, … highest degrees to the neighbors of the root, and so on) for any k≥ 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^λ₁+…+e^λ_n.

Cited by

• The Exponential Hyper-Zagreb Indices and Structural Properties of Trees and Bipartite Graphs
• On Topological Indices in Trees: Fibonacci Degree Sequences and Bounds

Related

• On the spectral moment of trees with given degree sequences
• Largest Eigenvalues of Degree Sequences
• Largest Laplacian Eigenvalue and Degree Sequences of Trees
• Largest Laplacian Eigenvalue and Degree Sequences of Trees
• Largest eigenvalues of the discrete p-laplacian of trees with degree sequences