一些特殊圖的反鄰接能量

張 飛，高玉斌

（中北大學理學院，太原 030051）

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

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

1 預備知識

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

式中：ni是特征值 λi的重數（1≤i≤k）。

圖G的距離能量定義為

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

式中：mi是特征值 ξi的重數（1≤i≤k）。

圖G的反鄰接能量定義為

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

設G1，G2是2個不相交的圖，作G1+G2，并且將G1中每個頂點和G2中的每個頂點連接，得到的新圖稱為 G1與G2的聯圖，記為：G1∨G2。

引理1［11］設M是n×n的對稱矩陣，若π是M的系數矩陣Bπ的一個等價分布，則Bπ的特征值也是M的特征值。

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

2 主要結論

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

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

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

定理 2 設 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 設 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種刪邊方式，考慮一般的情況，即設e是ni中最后一個頂點與 ni+1中第一個頂點的邊，ni≥2，r＞2，i=1，2，…，r-1，易得 Kn1，…，nr-e的反鄰接矩陣為

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

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

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

2）m=3，由推論 4，當 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）有兩個正根和兩個負根，設 α4≤α3＜0＜α2≤α1，則有α3+α4＜-4。由定理1和定理2得：