树,单圈图,双圈图依谱矩的排序

Lexicographical ordering of trees, unicyclic graphs and bicyclic graphs with respect to spectral moments

设G=(V(G),E(G))是一个n阶简单图,V(G),E(G)分别为图G的顶点集和边集.G的k阶谱矩sk(G)为G的所有特征值λ1,λ2,···,λn的k次幂之和,即sk(G)=n i=1λi k.该文首先列出图的五种变换,然后得到了其对任意图的零到四阶谱矩的变化规律,最后依次给出了树和单圈图依谱矩序列S4的字典序分别排在前4-6位和后4-6的图及其特征以及双圈图依谱矩序列S4的字典序排在前6位和后6位的图及其特征.

Let G = （V （G）, E（G）） be a simple graph with n vertices and m edges. The kth spectral moments of G is given by sk（G）=Pni=1λik, where λ1,λ2, … ,λn, are the eigenvalues of the adjacency matrix of G. In this paper, the variation properties of the spectral moments are studied by using five kinds of transformations. The lexicographical ordering of trees, unicyclic graphs and bicyclic graphs with respect to the sequence S4 are obtained respectively. The first fourth to sixth and the last fourth to the last sixth trees and unicyclic graphs with respect to the sequence S4 are characterized, and the first six and the last six bicyclic graphs with respect to the sequence S4 are characterized.