復(fù)雜網(wǎng)絡(luò)中二部圖的Estrada指標(biāo)

賈媛媛

（淮南師范學(xué)院 金融與數(shù)學(xué)學(xué)院，安徽 淮南 232038）

1 復(fù)雜網(wǎng)絡(luò)

復(fù)雜網(wǎng)絡(luò)是近來非常熱門并與很多學(xué)科密切相關(guān)的一個研究方向，真實世界中存在的大量復(fù)雜系統(tǒng)可以通過網(wǎng)絡(luò)來描述［1-4］.網(wǎng)絡(luò)由許多節(jié)點（node）和連接兩點之間的一些邊（edge）組成.其中，點用來代表組成真實系統(tǒng)中的個體，而邊用來表示個體間的相互聯(lián)系.比如說，人與人之間的社會關(guān)系、物種之間的捕食關(guān)系、計算機之間的網(wǎng)絡(luò)連接、以及科學(xué)家之間的合作關(guān)系等，都可以用網(wǎng)絡(luò)模型來描述.復(fù)雜網(wǎng)絡(luò)是刻畫和研究復(fù)雜系統(tǒng)的結(jié)構(gòu)和行為的關(guān)鍵.與之相關(guān)的基礎(chǔ)和應(yīng)用研究已經(jīng)滲入到物理學(xué)、生物學(xué)、計算機科學(xué)、管理學(xué)、社會學(xué)以及經(jīng)濟學(xué)等許多學(xué)科之中.在信息通信、網(wǎng)絡(luò)搜索、信號傳輸、傳染病控制以及社會學(xué)中，對突發(fā)事件的預(yù)報和處理等方面都具有重要的意義.

在本文中，所有的圖都認為是簡單的有限的，對于圖G，分別用n和m來表示它的頂點數(shù)和邊數(shù).一個（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譜中包含的零特征根個數(shù)被稱作零度，記為η (G)［5］.

2 E s t r a d a指標(biāo)的引入

在開始研究二部圖的Estrada指標(biāo)之前，首先來熟悉一般圖和一些特殊圖的Estrada指標(biāo).

定理1［5］令G是（n，m）圖，那么G的Estrada指標(biāo)上，下界是：

上面兩個等號成立當(dāng)且僅當(dāng)G≈Kn。

定理2［6］令G是一個度為r的n階正則圖，那么它的Estrada指標(biāo)的界為

注2 定理2的下界也可以利用圖G的第三譜距性質(zhì)進行證明

由此，二部正則圖可通過考慮（EE-er-e-r）2和EE-er-e-r來進行分析，由于特征值λi的和等于0，這樣就可以得到更為簡單的下界.

定理3［6］令G是一個度為r的n階二部正則圖，那么它的Estrada指標(biāo)上，下界為

定理4［6］令G是一個（n，m）二部圖，那么G的Estrada指標(biāo)上，下界為

左邊等號成立，當(dāng)且僅當(dāng)G?Kn；右邊等號成立，圖G要滿足G?Ka,b∪KC，其中a，b，c≥0，a+b+c=n并且ab=m.

猜想：在具有n個頂點的樹中，路和星圖分別具有最小和最大的Estrada指標(biāo)，即

這里Tn是一個有n個頂點的樹并且T}n,Pn

在文中，主要目標(biāo)是研究二部圖的Estrada指標(biāo).在此會給出二部圖新的，更為精確的上下界.

3 二部圖的Estrada指標(biāo)

3.1 一些引理

在這一部分，我們首先分析下面這個函數(shù)，

其中k是正整數(shù)，x1≥x2≥x3≥…≥xt≥0,并且xi=m。

引理1 對于任意的i，j如果xi-xj≥2a ＞ 0，那么當(dāng)k≥2的時候，有：

證明：我們只需要將不等式變成

因為

所以結(jié)果得證.

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

3.2 二部圖的Estrada指標(biāo)

容易看出，如果G有k個連通分支G1，G2，……，Gk，那么EE(G)=所以在這里我們研究的是連通二部圖的Estrada指標(biāo)

定理5 令G是一個連通二部圖，由EE（G）＝no+2ch(λi)，它的Estrada指標(biāo)的上，下界是：

不等式（5）左邊的等號成立，當(dāng)且僅當(dāng)圖G的所有正特征值都相等；右邊的等號成立當(dāng)且僅當(dāng)G≈Ka,b。其中a，b≥1，a+b=n≥2且ab=m。

證明：令G是一個連通二部圖，由（2）得

因二部圖的特征值是關(guān)于零點對稱的，那么G就有t=（n-η(G)）/2個正特征值，并且由引理2，對任意k≥2，都有可取到最小值當(dāng)且僅當(dāng)圖G的所有特征值全相等，且當(dāng)且僅當(dāng)G只有一個正特征值即t=1的時候，可取到最大值.

值得注意的是，一個連通二部圖當(dāng)且僅當(dāng)是一個完全二部圖的時候只有一個正特征值［8］，因此，結(jié)合定理得證.

作為定理5的推論，以下有：

推論1在所有的n個頂點的樹中，n階星圖具有最大的Estrada指標(biāo)，即

這里Tn是一個n階樹并且Tn不同構(gòu)于Sn

令λ1(G)是圖G的最大特征值.那么表示除了λ1(G)以外的所有正特征值的和，我們繼續(xù)看定理2，證明可類比定理1.

定理6 對于二部連通圖G（n，m），圖G的Estrada指標(biāo)的上下界是：

不等式（6）左邊的等號成立當(dāng)且僅當(dāng)除了λ1(G)以外的所有正特征值都相等；而右邊的等號成立當(dāng)且僅當(dāng)圖G有四個非零特征值.

4 結(jié)束語

本文根據(jù)有關(guān)圖的Estrada指標(biāo)的理論和性質(zhì)及已有的相關(guān)結(jié)論，運用代數(shù)圖論和在復(fù)雜網(wǎng)絡(luò)中的研究成果，得出了：圈和路的直和，以及乘積的運算圖的Estrada指標(biāo)，以及二部圖中的Estrada指標(biāo)更為精確的上下界，這一結(jié)果在復(fù)雜網(wǎng)絡(luò)中心度的研究中具有潛在的應(yīng)用價值.