Ordering starlike trees by the totality of their spectral moments

Abstract

The $k$-th spectral moment $M_k(G)$ of the adjacency matrix of a graph~$G$ represents the number of closed walks of length~$k$ in~$G$. We study here the partial order $⪯$ of graphs, defined by $G⪯H$ if $M_k(G)\le M_k(H)$ for all $k\ge 0$, and are interested in the question when is $⪯$ a linear order within a specified set of graphs? Our main result is that $⪯$ is a linear order on each set of starlike trees with constant number of vertices. Recall that a connected graph $G$ is a starlike tree if it has a vertex~$u$ such that the components of $G-u$ are paths, called the branches of~$G$. It turns out that the $⪯$ ordering of starlike trees with constant number of vertices coincides with the shortlex order of sorted sequence of their branch lengths.

22 pages, 3 figures