一些特殊图的反邻接能量

张 飞，高玉斌

（中北大学理学院，太原 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得：