蔡素麗

(福州外語外貿(mào)學(xué)院)

1 基本概念

在該文中，僅考慮無圈，無重邊的無向簡單圖.

設(shè)G=(V，E)是n階簡單圖.其頂點集和邊集分別記為V=V(G)={v1，v2，…，vn}和E=E(G)={e1，e2，…，en}，dG(vi)表示頂點vi在圖G中的度且滿足M(G)+2m，λ1，λ2，…，λn為圖G的鄰接矩陣A(G)的特征值，也稱為圖G的譜.設(shè)λ1≥λ2≥…≥λn.圖G的譜滿足下面的等式關(guān)系:

矩陣L(G)稱為圖G的Laplacian矩陣.設(shè)μ1≥μ2≥…≥μn=0為L(G)的特征值，也稱為圖G的Laplacian譜.

圖的Estrada指標(biāo)定義如下:

定義1.1［1］設(shè)G是一個(n，m)－graph，且其Laplacian特征值為μ1≥μ2≥…≥μn=0，那么G的Laplacian Estrada指標(biāo)定義如下:

定義1.2［2］設(shè)G是一個(n，m)－graph，且其Laplacian特征值是μ1≥μ2≥…≥μn=0，圖G的Laplacian Estrada指標(biāo)定義為:

2 主要結(jié)論

2.1 關(guān)于格子圖的L－Estrada指標(biāo)問題

定義2.1.1［3］平面格子圖Pm×Pn的定義為:

引理2.1.1m階的路Pm的Laplacian譜為

引理 2.1.2［4］設(shè)λi(G1)，λj(G2)分別為圖G1和G2的 Laplacian特征根，則G1×G2的Laplacian特征根為λi(G1)+λj(G2)i=1，…，|V(G1)|，j=1，…，|V(G2)|

定理2.1.1m×n階格子圖Pm×Pn的Laplacian譜為:

定理 2.1.2－ 26.799075+16.843984m.

證明 由引理2.1.1知階為m的路Pm的Laplacian譜為m–1.

根據(jù)定義1.1、引理2.1.1 可得LEE(Pm)=

通過Excel散點觀察(圖略)知路Pm的拉普拉斯Extrada指標(biāo)與階數(shù)m呈線性關(guān)系，設(shè)擬合方程為LEE=am+b，運(yùn)用最小二乘法作線性擬合.

可得LEE(Pm)16.843984m.

定理 2.1.3LEE(Pm×Pn)=LEE(Pm)·LEE(Pn)≈ 283.719786mn– 451.403184(m+n)+718.190427.

證明 根據(jù)定義 2.1.1、定理 2.1.1，定理2.1.2 可得:

2.2 關(guān)于輪圖的L－Estrada指標(biāo)問題

用積分逼近方法得到輪圖的L－Estrada指標(biāo)近似表達(dá)式.

定義2.2.1 圖G和H的聯(lián)圖G∨H定義為:

其中E'={gihj|i=1，2，…，p;j=1，2，…，q}.

定理2.2.1［5］設(shè)|G|=p和|H|=q且圖G和H的Laplacian譜分別為:

則有聯(lián)圖G∨H的Laplacian譜為:

引理2.2.1n階輪圖Wn的Laplacian譜為

定理 2.2.2LEE'(Wn)

證明 因為Wn=Cn－1∨K1，所以E(Wn)=2(n– 1).根據(jù)定義1.2、引理2.2.1 可得:

當(dāng)i=1，2，…，n–1時，角2iπ/n均勻地分布在區(qū)間［0，2π］中，當(dāng)n充分大時，得到近似表達(dá)式:

證畢.

2.3 關(guān)于單點粘合圖的L－Estrada指標(biāo)問題

定義2.3.1 設(shè)G1是(n1，m1)－graph，G2是(n2，m2)－graph，vi、uj分別是G1和G2的任意兩個頂點，G1和G2的單點粘合G1⊙G2是(n1+n2－1，m1+m2)－graph，即為將G1∪G2中點v1與uj粘合所得到的圖.

引理2.3.1 設(shè)G為(n，m)－graph，且它的頂點的最大度為Δ，最小度為δ，那么

等式成立當(dāng)且僅當(dāng)G是正則圖.

引理2.3.2 設(shè)G1，G2是兩個圖，階數(shù)分別為n1，n2，圖G1⊙G2是G1和G2的單點粘合圖，記μ1(G1)≥μ2(G1)≥…≥μn1(G1)=0，μ1(G2)≥μ2(G2)≥ … ≥μn2(G2)=0，μ1(G1⊙G2)≥μ2(G1⊙G1)≥ … ≥μn1+n2(G1⊙G2)=0，那么

定理2.3.1 設(shè)G為(n，m)－graph，且它的頂點的最大度為Δ，最小度為δ，那么:

LEE(G·G)≤2(n–1)+4m+e2M(G)+2Δ2+4m–

證明 對整數(shù)k≥3，

定理2.3.2 設(shè)G為(n，m)－graph，且它的頂點的最大度為Δ，最小度為δ，那么:

當(dāng)且僅當(dāng)G=ˉKn時，等式成立.

證明 假設(shè)n≥1，對非負(fù)實數(shù)a1，a2，…，ap且l≤k，l，k≠ 0，有不等式:

當(dāng)且僅當(dāng)a1=a2=…=ap時，等式成立.那么對

k≥2，p=n，l=2且ai=μi(i=1，2，…，n)，有:

定理2.3.3 設(shè)G是一個r正則圖，頂點數(shù)為n，那么:

證明 如果圖G是r－正則圖，由引理3.1.1有μi(G)－r=–λn－i+1(G)，i=1，2，…，n.其中λ1=r，λ2，…，λn是圖G的一般特征值，它們按遞減的順序排列.通過使用算術(shù)幾何不等式，我們得到:

證畢.

以上給出了關(guān)于格子圖、輪圖的拉普拉斯Estrada指標(biāo)的近似計算公式以及單點粘合圖上界和下界.該文還有待改進(jìn)，如該文只對相同圖的單點粘合拉普拉斯Estrada指標(biāo)進(jìn)行估計，有待進(jìn)一步改進(jìn)為任意圖形單點粘合的情況.

［1］Zhou B，Gutman I.More on the Laplacian Estrada index［J］.Appl Anal Discrete Math，2009(3):371－378.

［2］Li Jianxi，Wai Chee Shiu，Chang An.On the laplacian estrada index of a graph［J］.Appl Anal Diacrete Math，2009(3):147－156.

［3］Noman Biggs Algebraic Graph Theory［M］.2nd ed London:Cambridge Vniversity Press，1974.

［4］Fiedler M.Algebraic connectivity of graphs［J］.Czech Math，1973，23(98):298–305.

［5］Cvetkovi D，Doob M，Sachs H.Spectra of Graphs－Theory and Application［M］.Berlin，Heidelberg，1995.