周 后 卿

(邵阳学院 数学系, 湖南 邵阳 422000)



循环图的预解Estrada指标

周 后 卿

(邵阳学院 数学系, 湖南 邵阳 422000)

循环图；整循环图；预解Estrada指标；特征值

Journal of Zhejiang University(Science Edition), 2016,43(5):517-520

0　引　言

设G是一个具有n个顶点的简单图,G的邻接矩阵记为A(G).设A(G)的特征值为λ1,λ2,…,λn. 定义G的预解Estrada指标(以下用EEr(G) 表示)为

图的预解Estrada指标在测量复杂网络中心度时具有重要作用,许多学者对其进行了研究.CHEN等[1]讨论了EEr(G)的下界问题,得到:

文献[2]推出了一个计算预解Estrada指标的公式：

对任何一个具有n个顶点的非完全图G,其预解Estrada指标为

其中Φ(G,λ)为G的特征多项式.

文献[2]还证明了,若图G去掉一条边e后,其预解Estrada指标就会下降,即

EEr(G-e)

从而得到完全图的预解Estrada指标最大.

文献[3]也讨论了具有最小预解Estrada指标的极图问题,得到如下结果：

在具有n(n≥1)个顶点的所有连通图中,路图的预解Estrada指标最小.

本文主要研究循环图、整循环图的预解Estrada指标问题.

1　有关循环图的背景知识

若一个图是循环群上的Cayley图,其邻接矩阵是一个循环矩阵，则称其为循环图.具有n个顶点的循环图记为G(n,S),S⊆{0,1,2,…,n-1},0∉S,集合S为循环图G(n,S)的符号集.它是这样一个集合：若其任意2个顶点i与j相邻,当且仅当i-j(modn)∈S,n为正整数,S=-S.一个图若其邻接矩阵的特征值都为整数，则称其为整谱图.特征值全为整数的循环图称为整循环图.为便于表述,习惯将整循环图记为ICGn(D).在过去的几十年里,循环图已广泛应用于编码理论、VLSI设计、Ramsey理论、并行计算和分布式计算，在量子物理学中也有应用，并发挥了重要作用.

循环图具有重要的互联网络拓扑结构,同……