Ordering starlike trees by the totality of their spectral moments

preprint2020arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.