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

2019-05-05 10:49徐幼专
关键词:单圈边数邻接矩阵

徐幼专

(邵阳广播电视大学,湖南 邵阳,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去估计结果更准确一些。

猜你喜欢
单圈边数邻接矩阵
轮图的平衡性
一类单圈图的最大独立集的交
单圈图关联矩阵的特征值
盘点多边形的考点
基于模拟退火算法的模型检索
单圈图的Seidel拉普拉斯能量
基于邻接矩阵变型的K分网络社团算法
基于子模性质的基因表达谱特征基因提取
具有最多与最少连通子图的单圈图
有关多边形边数问题的思考方法