Spectral moments of trees with given degree sequence

DOI10.1016/J.LAA.2013.10.019MaRDI QIDQ2435586zbMATH OpenOpenAlexFDO

Authors Eric Ould Dadah Andriantiana, Stephan Wagner

Publication date 19 February 2014

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.4696

zbMATH Keywords

degree sequenceEstrada indexspectral momentstreeswalks

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Let $lambd{a}_1,dots,lambd{a}_n$ be the eigenvalues of a graph $G$. For any $kgeq0$, the $k$-th spectral moment of $G$ is defined by $M_k(G)=lambd{a}_1^k+dots+lambd{a}_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 $kgeq0$. Several corollaries follow, in particular a conjecture of Ili'c and Stevanovi'c on trees with given maximum degree, which in turn implies a conjecture of Gutman, Furtula, Markovi'c and Gliv{s}i'c on the Estrada index of such trees, which is defined as $EE(G)=e^{lambd{a}_1}+dots+e^{lambd{a}_n}$.

Recommendations

• Trees with given degree sequence in \(S\)-order
• On majorization of closed walk vectors of trees with given degree sequences
• On the distance spectral radius of trees with given degree sequence
• The spectral moments of trees with given maximum degree
• Graphs with given degree sequence and maximal spectral radius

Cites work

• Corrigendum: The extremal values of the Wiener index of a tree with given degree sequence
• Energy, Hosoya index and Merrifield-Simmons index of trees with prescribed degree sequence
• Estimating the Estrada index
• Graph energy
• Graphs with given degree sequence and maximal spectral radius
• Greedy trees, caterpillars, and Wiener-type graph invariants
• Greedy trees, subtrees and antichains
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 6256254 (Why is no real title available?)
• Largest eigenvalues of the discrete p-Laplacian of trees with degree sequences
• On Estrada index of trees
• On maximum Estrada indices of graphs with given parameters
• On the estrada index of graphs with given number of cut edges
• The Estrada index of chemical trees
• The Estrada index of trees
• The Estrada index of unicyclic graphs
• The extremal values of the Wiener index of a tree with given degree sequence
• The Laplacian spectral radii of trees with degree sequences
• The number of subtrees of trees with given degree sequence
• The sum of the distances between the leaves of a tree and the `semi-regular' property
• Wiener index versus maximum degree in trees

Cited in

(13)

• Ordering starlike trees by the totality of their spectral moments
• Extremal trees with fixed degree sequence
• On majorization of closed walk vectors of trees with given degree sequences
• On spectral radius of graphs with pendant paths
• Complete subgraphs in connected graphs and its application to spectral moment
• Tree composition condition and moments vanishing
• scientific article; zbMATH DE number 5532158 (Why is no real title available?)
• Spectral radius of graphs
• Extremal problems for trees with given segment sequence
• On a poset of trees
• An alternative proof of the Sombor index minimizing property of greedy trees
• On the skew spectral moments of trees and unicyclic graphs
• On irregularity measures in trees with Fibonacci degree sequences

This page was built for publication: Spectral moments of trees with given degree sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2435586)