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

p r e c e q

of graphs, defined by

G p r e c e q H

if

M_{k} (G) l e q M_{k} (H)

for all

k g e q 0

, and are interested in the question when is

p r e c e q

a linear order within a specified set of graphs? Our main result is that

p r e c e q

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

p r e c e q

ordering of starlike trees with constant number of vertices coincides with the shortlex order of sorted sequence of their branch lengths.

This page was built for publication: Ordering starlike trees by the totality of their spectral moments