孫 潔，邵燕靈

(中北大學(xué) 理學(xué)院，山西 太原 030051)

0 引 言

本文考慮的圖均為簡單圖.設(shè)G為一個具有頂點(diǎn)集V(G)={v1,v2,…,vn}和邊集E(G)的無向圖，如果圖M是對無向圖G的某些邊加上方向后而獲得的，則稱M為混合圖，稱無向圖G為M的基本圖，記為Mu.混合圖M的頂點(diǎn)集V(M)與其基本圖的頂點(diǎn)集V(Mu)相同，邊集E(M)是無向邊的集合E0與有向邊的集合E1的并集.

設(shè)M是頂點(diǎn)集為V(M)={v1,v2,…,vn}和邊集為E(M)的混合圖，用vkvl(或vk?vl)表示M中連接兩個頂點(diǎn)vk和vl的無向邊，用(vk,vl)(或vk→vl)表示從vk到vl的有向邊(或弧).用dk=d(vk)=dG(vk)表示無向圖G中頂點(diǎn)vk的度.對于混合圖M，用dk=d(vk)=dMu(vk)表示其基礎(chǔ)圖Mu中頂點(diǎn)vk的度.

(1)

圖G的ABC指數(shù)定義為[6]

(2)

其相關(guān)的研究見文獻(xiàn)[7-9].

如果在混合圖M的每一條邊和弧上加上ABC權(quán)，就可以得到一個新的加權(quán)埃爾米特鄰接矩陣.下面給出具體定義.設(shè)M是頂點(diǎn)集為V(M)={v1,v2,…,vn}的一個混合圖，定義M的埃爾米特-ABC矩陣為n階矩陣ABCH(M)=((wh)kl)，其中

(3)

本文定義了混合圖的埃爾米特-ABC矩陣ABCH(M)，給出了混合圖的埃爾米特-ABC能量的一些界，并刻畫了有向圖D1和D2的埃爾米特-ABC能量與混合圖D1∨D2的埃爾米特-ABC能量之間的關(guān)系，其中D1∨D2是在有向圖D1的每個頂點(diǎn)與有向圖D2的所有頂點(diǎn)之間各添加一條無向邊而得到的混合圖.

1 預(yù)備知識

引理1[8]設(shè)G為無孤立點(diǎn)的n≥2階無向圖，Δ(G)與δ(G)分別為G的最大度與最小度，則

(4)

兩邊等號成立當(dāng)且僅當(dāng)G為正則圖.

引理2 設(shè)M為n階混合圖，Mn為M的基本圖，η1≥η2≥…≥ηn為ABCH(M)的特征值，則

2(n-2R-1(Mu)),

(5)

證明因?yàn)?/p>

(6)

故結(jié)論成立.證畢.

2 混合圖的埃爾米特-ABC能量的界

證明設(shè)η1≥η2≥…≥ηn為ABCH(M)的特征值，則存在一個n階酉矩陣U，使得

U*ABCH(M)U=U*ABCH(M)*U=

diag{η1,η2,…,ηn}.

(7)

定理2 設(shè)M為n≥3階混合圖，Mu為M的基本圖，η1≥η2≥…≥ηn為ABCH(M)的特征值，p=|detABCH(M)|，則

(8)

(9)

另一方面，

(10)

由算術(shù)幾何平均不等式，得到

(11)

因此

(12)

由柯西-施瓦茨不等式和算術(shù)幾何平均不等式可知，式(12)等號成立當(dāng)且僅當(dāng)|η1|=|η2|=…=|ηn|，再由定理1知，結(jié)論成立.證畢.

推論1 設(shè)M為n階混合圖，M的基本圖Mu為k正則圖，且Mu的邊數(shù)為m，η1≥η2≥…≥ηn為ABCH(M)的特征值，p=|detABCH(M)|，則

(13)

定理3 設(shè)M為n≥3階的無孤立點(diǎn)的混合圖，且Mu為M的基本圖，η1≥η2≥…≥ηn為ABCH(M)的特征值，Δ與δ分別表示Mu的最大度與最小度，則

(14)

上界等式成立當(dāng)且僅當(dāng)Mu為正則圖且|η1|=|η2|=…=|ηn|；下界等式成立當(dāng)且僅當(dāng)Mu為正則圖且|η1|=|ηn|≠0,ηj=0,j=2,…,n-1.

證明由柯西-施瓦茲不等式及引理2，

(15)

(16)

再由引理1，

(17)

由上面證明過程并結(jié)合引理1，可知上界等式成立當(dāng)且僅當(dāng)Mu為正則圖且|η1|=|η2|=…=|ηn|.

(18)

4(n-2R-1(Mu)),

(19)

3 一類混合圖的埃爾米特-ABC能量

設(shè)D1和D2為兩個有向圖，圖D1∨D2是在D1的每個頂點(diǎn)與D2的所有頂點(diǎn)之間各添加一條無向邊而得到的混合圖.用odD(u)表示有向圖D中頂點(diǎn)u的出度(即D中以頂點(diǎn)u為始點(diǎn)的邊數(shù))，idD(u)表示有向圖D中頂點(diǎn)u的入度(即D中以頂點(diǎn)u為終點(diǎn)的邊數(shù)).本節(jié)刻畫了有向圖D1和D2的埃爾米特-ABC能量與混合圖D1∨D2的埃爾米特-ABC能量之間的關(guān)系.

φABC(D1∨D2,λ)=

(20)

(21)

則混合圖D1∨D2的埃爾米特-ABC矩陣的特征多項(xiàng)式為

φABCH(D1∨D2∶λ)=

由于對任意頂點(diǎn)u∈V(Dj)都有odDj(u)=idDj(u)，故

(23)

對式(22)作如下變換：從第n1+2行到第n1+n2行，每一行都減去第n1+1行，再從第n1+2 列到第n1+n2列，每一列都加到第n1+1列上，然后從第2行到第n1行，每一行都減去第1行，再從第2列到第n1列，每一列都加到第1列上，并利用式(23)得

φABCH(D1∨D2∶λ)=

(λ2-n1n2a2)|A||B|,

(24)

其中

將|A|升階為n1階行列式

|A|=

(25)

從第2列到第n1列，每一列都乘-1加到第1列上，再從第2行到第n1行，每一行都加上第1行，可得

|A|=

(26)

εABCH(D1∨D2)=bεABCH(D1)+

(27)

證明由定理4知，

λ2φABCH(D1∨D2∶λ)=

(28)