一些特殊圖的反鄰接能量

張 飛，高玉斌

（中北大學(xué)理學(xué)院，太原 030051）

近年來(lái)，關(guān)于1個(gè)圖的矩陣和能量的研究非常廣泛，取得了很多重要結(jié)論。當(dāng)然，一個(gè)圖可以定義多種不同的能量，比如文獻(xiàn)［1］中首先定義了圖的鄰接矩陣A（G），在此基礎(chǔ)上Gutman定義了鄰接能量。在文獻(xiàn)［2-5］中，從圖的矩陣的譜中定義了相似圖的能量不變量，比如距離能量等。關(guān)于距離能量的文獻(xiàn)和結(jié)論很多，比如文獻(xiàn)［6］中得出Km，n有m+n-2個(gè)-2距離特征值，根據(jù)距離能量的定義很容易知道Km，n的距離能量為 ED（Km，n）=4（m+n-2）。文獻(xiàn)［7］采用更簡(jiǎn)潔的方法來(lái)計(jì)算 Km，n的距離能量以及刪邊后的Km，n-e的距離能量，從而得出 Km，n在刪除任何1條邊后其距離能量增大，即 ED（Km，n）＜ED（Km，n-e）。根據(jù)圖論中的一些概念，在文獻(xiàn)［5］中由圖的距離矩陣定義了圖的反鄰接矩陣，進(jìn)而定義了圖的反鄰接能量。圖的反鄰接能量來(lái)源于化學(xué)圖論，因此研究其代數(shù)不變量是很有意義的。從這些新的矩陣中得到的結(jié)果可以與化學(xué)圖的理化性質(zhì)相關(guān)聯(lián)，比如通過(guò)選擇1個(gè)或多個(gè)分子特性并使用執(zhí)行MRA（多元回歸分析）來(lái)完成分子描述和新的矩陣不變量。在文獻(xiàn)［8］中給出分子中不同長(zhǎng)度的路徑數(shù)，可能對(duì)分子表征有用；在文獻(xiàn)［9］中Randic'和Wilkins表明辛烷值C8H18的18點(diǎn)同分異構(gòu)體關(guān)于P2和P3（分別是長(zhǎng)度為2的路徑和長(zhǎng)度為3的路徑）可以識(shí)別很多它們的物化性質(zhì)的規(guī)律性等。在文獻(xiàn)［5］中也給出了反鄰接能量在化學(xué)圖論中的一些應(yīng)用。關(guān)于反鄰接能量的文章，目前不是很多，在文獻(xiàn)［10］中計(jì)算了含有n個(gè)頂點(diǎn)的路、環(huán)、雙星圖等一些特殊圖的反鄰接能量，研究了鄰接能量和反鄰接能量的關(guān)系，并得到一些特殊圖的反鄰接能量的上界和下界。

受文獻(xiàn)［7，10-11］的啟發(fā)，本文中首次計(jì)算了完全 r部圖 Kn1，…，nr和 Kn1，…，nr∨Km的反鄰接能量，并引用刪邊的方式來(lái)研究在刪除Kn1，…，nr和團(tuán)圖T（n，r）的任意一條邊后其反鄰接能量的變化情況。

1 預(yù)備知識(shí)

令G=（V（G），E（G））是含有 n個(gè)頂點(diǎn)的連通圖，其中 n≥1。V（G）是 G的頂點(diǎn)集，即 V（G）={v1，v2，…，vn} ；E（G）是 G的邊集。G的距離矩陣是n×n矩陣 D（G）=[di，j]，其中 di，j是頂點(diǎn) vi和 vj的距離。D（G）的特征值 { λ1，…，λn}稱為G的距離特征值，而D（G）是一個(gè)實(shí)對(duì)稱矩陣，因此其特征值均為實(shí)數(shù)。把一個(gè)圖的距離譜寫為

式中：ni是特征值 λi的重?cái)?shù)（1≤i≤k）。

圖G的距離能量定義為

圖G的反鄰接矩陣是將圖G的距離矩陣的每1行和每1列的最大元保留、其余元變成0后得到的矩陣。我們把圖 G的反鄰接矩陣稱為ε（G），ε（G）的特征值{ξ1，…ξn}稱為G的反鄰接特征值，而ε（G）是一個(gè)實(shí)對(duì)稱矩陣，因此其特征值均為實(shí)數(shù)。我們把一個(gè)圖的反鄰接譜寫為

式中：mi是特征值 ξi的重?cái)?shù)（1≤i≤k）。

圖G的反鄰接能量定義為

團(tuán)圖 T（n，r）是一個(gè)完全 r部圖，即將頂點(diǎn)集 {v1，v2，…，vn}分成r個(gè)子集，這些子集的基數(shù)盡可能相等，任意2個(gè)頂點(diǎn)vi和vj鄰接，當(dāng)且僅當(dāng)這2個(gè)頂點(diǎn)在不同的子集中。

設(shè)G1，G2是2個(gè)不相交的圖，作G1+G2，并且將G1中每個(gè)頂點(diǎn)和G2中的每個(gè)頂點(diǎn)連接，得到的新圖稱為 G1與G2的聯(lián)圖，記為：G1∨G2。

引理1［11］設(shè)M是n×n的對(duì)稱矩陣，若π是M的系數(shù)矩陣Bπ的一個(gè)等價(jià)分布，則Bπ的特征值也是M的特征值。

引理2［5］令Q是一個(gè)n階方陣，若Q的每1列的和都等于Q的某個(gè)特征值（記為α），則有：

2 主要結(jié)論

定理 1 完全 r部圖 Kn1，…，nr的反鄰接能量 Eε（Kn1，…，nr）=4（n1+n2+… +nr-r），其中 ni≥2，r≥2，i=1，2，…，r。

證明：根據(jù)Kn1，…，nr的距離矩陣，易得其反鄰接矩陣為

因?yàn)?det（xI-ε（Kn1，…，nr））=（x-2n1+2）（x+2）n1-1…（x-2nr+2）（x+2）nr-1，則其反鄰接矩陣的譜為：。又因?yàn)?ni≥2，i=1，2，…，r，則2ni-2＞0，于是 Eε（Kn1，…，nr）=4（n1+n2+… +nr-r）。證畢。

定理 2 設(shè) e是完全二部圖 Kn1，n2的任意一條邊，則 Eε（Kn1，n2）＞Eε（Kn1，n2-e），其中 n1，n2≥2。

證明：由反鄰接矩陣的定義得

det（xI-ε（Kn1，n2-e））=（x-2n1+4）（x-2n2+4）（x+2）n1+n2-4（x-3）（x+3），從而 ε（Kn1，n2-e）的特征值的譜為

由于 n1，n2＞1，則 2n1-4≥0，2n2-4≥0，即 Eε（Kn1，n2-e）=2（n1+n2-4）+3+3+2n1-4+2n2-4=4（n1+n2）-10。由定理 1，Eε（Kn1，n2）=4（n1+n2-2），則 Eε（Kn1，n2）-Eε（Kn1，n2-e）=2＞0，從而Eε（Kn1，n2）＞Eε（Kn1，n2-e）。證畢。

定理 3 設(shè) e是完全 r部圖 Kn1，…，nr的任意一條邊，則 Kn1，…，nr-e的反鄰接能量為：

其中：ni≥2，r＞2，i=1，2，…，r；αi是 f（x）=x4+［8-2（m+n）］x3+［4mn-12（m+n）+20］x2+16（mn-n-m）x+16（m+n-3）的根。其中

證明：由于e是Kn1，…，nr任意1條邊，因此有r-1種刪邊方式，考慮一般的情況，即設(shè)e是ni中最后一個(gè)頂點(diǎn)與 ni+1中第一個(gè)頂點(diǎn)的邊，ni≥2，r＞2，i=1，2，…，r-1，易得 Kn1，…，nr-e的反鄰接矩陣為

推論1 若 m+n＞4，則 f（x）有2個(gè)正根，2個(gè)負(fù)根，即 α4≤α3＜0＜α2≤α1。

證明：由定理 2知，α1，α2，α3，α4是 f（x）的4個(gè)根，則有：

1）m=2，由推論 3，當(dāng) n≥2，Eε（Kn1，…，ni-1，2，ni+1，…，nr）＜Eε（Kn1，…，ni-1，2，ni+1，…，nr-e）。

2）m=3，由推論 4，當(dāng) n≥2，Eε（Kn1，…，ni-1，3，ni+1，…，nr）＜Eε（Kn1，…，ni-1，3，ni+1，…，nr-e）。

3）m≥4，則4≤m≤n。由定理2及推論2知，f（x）有兩個(gè)正根和兩個(gè)負(fù)根，設(shè) α4≤α3＜0＜α2≤α1，則有α3+α4＜-4。由定理1和定理2得：