zbMATH — the first resource for mathematics

Trees with given degree sequence in \(S\)-order. (English) Zbl 1346.05033
Let \(A(G)\) be the adjacency matrix of a graph \(G\) on \(n\) vertices and let \(\lambda_1(G),\lambda_2(G),\ldots,\lambda_n(G)\) be the eigenvalues of \(A(G)\). The \(k\)-the spectral moment of \(G\), denoted by \(S_k(G)\), is defined as \(\sum\limits_{i=1}^n(\lambda_1(G))^k\); \(0\leq k\leq n-1\). The \(S\)-order is a natural lexicographical ordering of graphs introduced by the sequence \(S(G)=S_0(G),S_1(G),S_2(G),\ldots,S_{n-1}(G)\) of spectral moments. A graph \(G\) is said to appear earlier in the \(S\)-order than a graph \(H\) if and only if for some \(k\), \(0\leq i\leq k\), \[ S_i(G)=S_i(H)\;\text{and}\;S_{k+1}(G)<S_{k+1}(H) \] .
Using the result that the \(k\)-th spectral moment of a graph \(G\) is equal to the number of closed walks of length \(k\), the authors prove that for a tree \(T\) with given distinct degree sequence that appear first in the \(S\)-order and a longest path \(P=v_0v_1v_2v_iv_{i+1}\) in \(T\) and for \(i\leq \frac{t+1}{2}\), \[ \deg(v_i)\leq \deg(v_{t+1-i})<\deg(v_k) \] for \(i<k<t+1-i\) if \(i\) is even and \[ \deg(v_i)> \deg(v_{t+1-i})>\deg(v_k) \] for \(i<k<t+1-i\) if \(i\) is odd.
The article has exactly one major result mentioned above, but in the final section, the authors initiate a discussion on the degree sequence with repeated roots and highlight the need of a novel idea to study the \(k\)-th spectral moments for higher values of \(k\).
In this paper, the authors consider the lexicographical ordering by spectral moments of trees with given degree sequence. They tried to address to some of the questions on the trees appearing in the ordering mentioned above and made some progress in this direction. The article is nicely written and successful in creating some interest for future studies.
05C05 Trees
05C07 Vertex degrees
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)