单圈图的扩展矩阵的谱半径与能量

徐幼专

(邵阳广播电视大学，湖南 邵阳，422000)

能量的概念起源于化学，20世纪30年代，Huckel 分子轨道理论提出了一种对共轭烃的薛定谔方程求近似解的方法，这一方法，可以用来估计共轭烃中π-电子的分子轨道能级，并计算π-电子的总能量。图的特征值和共轭碳氢化合物中π-电子的分子轨道能级之间有着紧密对应，碳氢化合物系统的碳原子对应于相关分子图的顶点，分子图的能量定义为其邻接矩阵的特征值的绝对值之和。图的能量是图的一个不变量，对于图的能量研究有许多结果，参见文献[1-4]。能量的概念有很多推广，至今为止，已有63种能量得到研究[5]。

这篇文章主要研究单圈图的扩展谱半径和扩展能量。

1 预备知识

设G是具有n个顶点的简单图，其顶点集为V(G)={v1，v2，…，vn}，边集为E(G)，令|E(G)|=m。用di表示顶点vi的度，同时，用Δ、δ分别表示G中的最大度和最小度。若顶点vi与vj相邻，则记作vivj∈E(G)。图G的邻接矩阵用A(G) 表示，设A(G)的特征值为λi(i=1，2，…，n)，不妨设λ1≥λ2≥…≥λn，这个最大的特征值λ1称为图G的谱半径。因为A(G)是一个实对称矩阵，它的所有特征值都是实数。图G的谱是指其邻接矩阵A(G)的所有特征值的集合。单圈图就是边数等于顶点数的简单连通图，单圈图是除树之外结构最简单的图类，它在图谱理论、复杂网络、图染色理论等都发挥着不可替代的作用。

图的扩展邻接矩阵被YANG介绍过[6]，定义图的扩展邻接矩阵Aex=(aexij)，这里

1)设G是顶点数为n、边数为m的简单图，则

(1)

等式成立当且仅当G≌K1，n-1，这里K1，n-1表示具有n个顶点的星图。

2)设G是最大度为Δ、最小度为δ的简单图，则

(2)

等式成立当且仅当G是正则图，这里λ1为图G的邻接谱半径。

设G是顶点数为n、边数为m、最大度为Δ、最小度为δ的简单图，则

(3)

(4)

2 定理及其证明

先介绍几个引理。

下面证明文中的主要结论。

定理1 设G是顶点数为n的单圈图，则G的扩展谱半径满足

图1 具有5个顶点的单圈图S35Fig.1 Unicyclic graph S35 with 5 vertices

证明 因为G是顶点数为n的单圈图，所以其边数m=n。代入(1)式即得结论。

例如，以单圈图S35为例(见图1)，计算它的扩展谱半径。利用mathematica软件直接计算单圈图的扩展矩阵的特征值谱为{4.25，0，0，0，-4.25}，得到扩展谱半径为η1=4.25。 若利用定理1求得η1≤5.205。显然，η1=4.25<5.205，定理1成立。

定理2 设G是顶点数为n、最大度为Δ、最小度为δ的单圈图，则G的扩展谱半径满足

证明 分两种情形给予讨论

(5)

情形2 若单圈图的最小度δ>1，根据引理1和(2)式，得到

(6)

于是推出定理的结论。

再以单圈图S35为例，因为其最大度Δ=4，若用(5)式计算，则η1≤13.47。显然，η1=4.25<13.47，定理2是成立的。

定理3 设G是n(n≥9)阶、最大度为Δ、最小度为δ的单圈图，则G的扩展谱半径满足

同定理2证明一样，利用引理2，马上得出结论，这里略去证明。

比较定理1、2、3，发现定理1的结果要优于定理2、3的结果，定理3要优于定理2。

下面，研究单圈图的扩展能量。

定理4 设G是顶点数为n、最大度为Δ、最小度为δ的单圈图，则扩展能量满足

证明 对于单圈图G，其边数m与顶点数n相等，即m=n。

现分两种情形讨论：

于是，定理得到证明。

仍以单圈图S35为例说明定理4 的准确性。由于单圈图S35的扩展谱为{4.25，0，0，0，-4.25}，因而求得S35的扩展能量为Eex(S35)=8.5。因为Δ=4，δ=1，若用定理4计算，则Eex(S35)≤15.03。显然有8.5<15.03成立。

定理5 设G是顶点数为n、最大度为Δ、最小度为δ的单圈图，r表示当δ=1时的个数。则扩展能量满足

证明 对于单圈图G，若δ=1，不妨设d1=d2=…=dr=1，dr+1>1，dr+2>1，…，dn>1。

若δ>1，则有F(G)≤nΔ3。所以有

从而定理得到证明。

继续以单圈图S35为例，验证定理5 的准确性。由于单圈图S35的最大度为4，最小度为1的有2个，因此有Eex(S35)≤45.40，显然定理5成立。

从上发现用定理4估计，比用定理5去估计结果更准确一些。