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

賈媛媛

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

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

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

在本文中，所有的圖都認(rèn)為是簡(jiǎn)單的有限的，對(duì)于圖G，分別用n和m來(lái)表示它的頂點(diǎn)數(shù)和邊數(shù).一個(gè)（n，m）圖就表示這個(gè)圖有n個(gè)頂點(diǎn)，m條邊.對(duì)于圖G，它的特征多項(xiàng)式P（G，x）就是其鄰接矩陣的特征多項(xiàng)式，即P（G，x）＝det（xI-A（G））.

令λ1≥λ2≥…≥λn是鄰接矩陣A（G）的特征值，那么圖G的譜就是Spec（G）＝｛λ1，λ2，…,λn｝，圖G譜中包含的零特征根個(gè)數(shù)被稱作零度，記為η (G)［5］.

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

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

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

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

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

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

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

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

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

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

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

這里Tn是一個(gè)有n個(gè)頂點(diǎn)的樹(shù)并且T}n,Pn

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

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

3.1 一些引理

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

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

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

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

因?yàn)?/p>

所以結(jié)果得證.

引理2 對(duì)于任意k≥2，有

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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