复杂网络中二部图的Estrada指标

贾媛媛

（淮南师范学院 金融与数学学院，安徽 淮南 232038）

1 复杂网络

复杂网络是近来非常热门并与很多学科密切相关的一个研究方向，真实世界中存在的大量复杂系统可以通过网络来描述［1-4］.网络由许多节点（node）和连接两点之间的一些边（edge）组成.其中，点用来代表组成真实系统中的个体，而边用来表示个体间的相互联系.比如说，人与人之间的社会关系、物种之间的捕食关系、计算机之间的网络连接、以及科学家之间的合作关系等，都可以用网络模型来描述.复杂网络是刻画和研究复杂系统的结构和行为的关键.与之相关的基础和应用研究已经渗入到物理学、生物学、计算机科学、管理学、社会学以及经济学等许多学科之中.在信息通信、网络搜索、信号传输、传染病控制以及社会学中，对突发事件的预报和处理等方面都具有重要的意义.

在本文中，所有的图都认为是简单的有限的，对于图G，分别用n和m来表示它的顶点数和边数.一个（n，m）图就表示这个图有n个顶点，m条边.对于图G，它的特征多项式P（G，x）就是其邻接矩阵的特征多项式，即P（G，x）＝det（xI-A（G））.

令λ1≥λ2≥…≥λn是邻接矩阵A（G）的特征值，那么图G的谱就是Spec（G）＝｛λ1，λ2，…,λn｝，图G谱中包含的零特征根个数被称作零度，记为η (G)［5］.

2 E s t r a d a指标的引入

在开始研究二部图的Estrada指标之前，首先来熟悉一般图和一些特殊图的Estrada指标.

定理1［5］令G是（n，m）图，那么G的Estrada指标上，下界是：

上面两个等号成立当且仅当G≈Kn。

定理2［6］令G是一个度为r的n阶正则图，那么它的Estrada指标的界为

注2 定理2的下界也可以利用图G的第三谱距性质进行证明

由此，二部正则图可通过考虑（EE-er-e-r）2和EE-er-e-r来进行分析，由于特征值λi的和等于0，这样就可以得到更为简单的下界.

定理3［6］令G是一个度为r的n阶二部正则图，那么它的Estrada指标上，下界为

定理4［6］令G是一个（n，m）二部图，那么G的Estrada指标上，下界为

左边等号成立，当且仅当G≅Kn；右边等号成立，图G要满足G≅Ka,b∪KC，其中a，b，c≥0，a+b+c=n并且ab=m.

猜想：在具有n个顶点的树中，路和星图分别具有最小和最大的Estrada指标，即

这里Tn是一个有n个顶点的树并且T}n,Pn

在文中，主要目标是研究二部图的Estrada指标.在此会给出二部图新的，更为精确的上下界.

3 二部图的Estrada指标

3.1 一些引理

在这一部分，我们首先分析下面这个函数，

其中k是正整数，x1≥x2≥x3≥…≥xt≥0,并且xi=m。

引理1 对于任意的i，j如果xi-xj≥2a ＞ 0，那么当k≥2的时候，有：

证明：我们只需要将不等式变成

因为

所以结果得证.

引理2 对于任意k≥2，有

3.2 二部图的Estrada指标

容易看出，如果G有k个连通分支G1，G2，……，Gk，那么EE(G)=所以在这里我们研究的是连通二部图的Estrada指标

定理5 令G是一个连通二部图，由EE（G）＝no+2ch(λi)，它的Estrada指标的上，下界是：

不等式（5）左边的等号成立，当且仅当图G的所有正特征值都相等；右边的等号成立当且仅当G≈Ka,b。其中a，b≥1，a+b=n≥2且ab=m。

证明：令G是一个连通二部图，由（2）得

因二部图的特征值是关于零点对称的，那么G就有t=（n-η(G)）/2个正特征值，并且由引理2，对任意k≥2，都有可取到最小值当且仅当图G的所有特征值全相等，且当且仅当G只有一个正特征值即t=1的时候，可取到最大值.

值得注意的是，一个连通二部图当且仅当是一个完全二部图的时候只有一个正特征值［8］，因此，结合定理得证.

作为定理5的推论，以下有：

推论1在所有的n个顶点的树中，n阶星图具有最大的Estrada指标，即

这里Tn是一个n阶树并且Tn不同构于Sn

令λ1(G)是图G的最大特征值.那么表示除了λ1(G)以外的所有正特征值的和，我们继续看定理2，证明可类比定理1.

定理6 对于二部连通图G（n，m），图G的Estrada指标的上下界是：

不等式（6）左边的等号成立当且仅当除了λ1(G)以外的所有正特征值都相等；而右边的等号成立当且仅当图G有四个非零特征值.

4 结束语

本文根据有关图的Estrada指标的理论和性质及已有的相关结论，运用代数图论和在复杂网络中的研究成果，得出了：圈和路的直和，以及乘积的运算图的Estrada指标，以及二部图中的Estrada指标更为精确的上下界，这一结果在复杂网络中心度的研究中具有潜在的应用价值.