边界能量图研究的综述
邓波;李学良
【摘 要】The energy ε(G)of a graph G is the sum of the absolute values of the eigenvalues of G.Let Gbe an n-vertex graph.If Ghas the same energy as the n-vertex complete ,ε(G) = 2(n - 1),then G is said to be a borderenergetic graph.In the paper,the main results on the borderenergetic graphs would be presented.%图G的能量 ε(G)定义为其邻接矩阵特征根的绝对值之和.设G是一个具有n个顶点的图,如果G的能量值等于n个顶点的完全图的能量值2(n-1),则称图G为边界能量图.介绍了近年来关于边界能量图研究方面的主要结果.
【期刊名称】《安徽大学学报（自然科学版）》
【年(卷),期】2018(042)001
【总页数】11页(P1-11)
【关键词】图的特征根;图能量;边界能量图;拉普拉斯能量
【作 者】邓波;李学良
【作者单位】南开大学 组合数学中心,天津 300071;青海师范大学 数学与统计学院,青海 西宁 810001;南开大学 组合数学中心,天津 300071
【正文语种】中 文
【中图分类】O157.5
摘 要:图G的能量ε(G)定义为其邻接矩阵特征根的绝对值之和.设G是一个具有n个顶点的图，如果G的能量值等于n个顶点的完全图的能量值2(n-1), 则称图G为边界能量图.介绍了近年来关于边界能量图研究方面的主要结果.
关键词:图的特征根；图能量; 边界能量图；拉普拉斯能量
设G是一个n顶点的图，图G的点集和边集分别记为V(G)和E(G).表示图G的补图.顶点数为n的圈和完全图分别记为Cn和Kn. 令λ1≥λ2≥…≥λn是图G的邻接矩阵A(G)的n个特征根.当λ1≥λ2≥…≥λn都是整数，则G称为整谱图(或称为整图).图G的能量[1]定义如下
关于图能量及其应用的相关内容,可以参考文[2-5].
关于图能量，一个很自然的问题是: 哪类图具有最大的图能量? 起初，人们通常会认为当图越稠密，则对应图的图能量越大，因此认为完全图Kn具有最大的图能量，其能量值为ε(Kn)=2(n-1).实际上，存在大量的图满足其图能量是大于这个值，这类图被称为是超能量的.超能量图的概念提出后，陆续出现许多寻和刻画超能量图的结果[6-8]，不过这个研究方向很快被发现是平凡的，原因是Nikiforov通过使用概率方法证明了几乎所有的图都是超能量的.类似地，如果具有n个顶点的图G的图能量小于n(或者n-1),则图G是次能量的(或者是强次能量的)，相关的研究结果见文[9-11].
次能量图的概念源于化学实验，人们在化学研究中很早就发现绝大多数分子图的能量是大于其顶点数的.1973年理论化学家England和Ruedenberg发表在J.Am.Chem.Soc.上的一篇文章曾提到这样一个问题[12]: 为什么化合物的能量总大于其化学图的阶数? 围绕这个问题,Gutman等[9]进行了相关的研究，给出具有n个顶点和最大度为Δ的树是次能量的充分条件，并且分别证明当Δ=3,4和Δ≥5时，次能量树的存在性.
定理1[9] (a) 如果Δ=3, 则仅当n=4和n=7时，存在次能量树.
(b) 如果Δ=4, 则当n≥5和满足n≡k(mod 4), k=0,1,3时，存在次能量树.
(c) 如果Δ≥5, 则当n≥Δ+1时，存在次能量树.
然而当最大度Δ至多为3时，除了如下几个特殊树外，都不存在次能量树.
定理2[9] 除了树S1,S2,S3和W(见图1)，不存在最大度至多3的次能量树.
正则匹配关键词图1 树S1,S2,S3和W
Li等[10]证明了完全二部图K2,3是唯一含圈的满足Δ≤3的次能量连通图，同时出了所有的满足Δ≤3的次能量连通图.
定理3[10] 完全二部图K2,3是唯一含圈的满足Δ≤3的次能量连通图.
定理4[10] 图S1,S2,S3,W和K2,3是仅有的5个满足Δ≤3的次能量连通图.
定理3、4解决了由等[13]提出的猜想: 完全二部图K2,3是唯一含有四边形C4的满足Δ≤3的次能量连通图.
当图G的图能量值为n时，对应的图类也存在相关的研究[14].Li等给出了由等[13]提出的猜想的一个肯定证明，即定理5..
定理5[13-14] 在n个顶点和Δ≤3的连通图中，恰好存在4个连通图G∈{K2,K2,2,Q,K3,3}(见图2)，满足ε(G)=n.
图2 图K2,K2,2,Q和K3,3
化学图一般是指最大度不超过3的图.由上可见，只有少数几个图同时满足Δ≤3和ε(G)=n, 所以，这从理论上证明了化学家们在文[12]中观察的结果是正确的.然而当ε(G)=2(n-1)时，Gong等[15]发现存在大量的图满足这个条件.2015年，Gong等[15]提出边界能量图的概念: 如果G是一个具有n个顶点的图，满足G的图能量值与n个顶点的完全图的图能量值相等且为ε(G)=2(n-1),则称图G为边界能量的.类似地，Tura[16]把边界能量的概念推广到拉普拉斯能量.设μ1≥μ2≥…≥μn-1≥μn是图G的拉普拉斯特征根，图G的拉普拉斯能量定义如下
其中:是图G的平均度.如果满足LE(G)=LE(Kn)=2(n-1), 则图G被称为是拉普拉斯边界能量的.目前关于拉普拉斯边界能量图的搜索与刻画方面也存在一些结果[16-19].
论文主要介绍近年来关于边界能量图的主要结果.内容安排如下: 第一部分介绍边界能量图的搜索与构造方面的结果; 第二部分介绍边界能量图的边数的下界; 第三部分介绍在度条件下边界能量图的结构性质方面的结果；第四部分介绍拉普拉斯边界能量图方面的结果.
1 边界能量图的搜索与构造
为了研究边界能量图的存在性，Gong等[15]通过计算机搜索的方式，出顶点数不超过9的所有非完全边界能量图.特别地，当顶点数小于7时，不存在非完全边界能量图.当顶点数分别为7，8，9时，则有命题1～3.
命题1[15] 最小的非完全边界能量图G0具有7个顶点，17条边，而且是唯一的(见图3).
图3 最小的非完全边界能量图G0,其邻接谱为Sp(G0)={5,1,-1,-1,-1,-1,-2}
命题2[15] 顶点数为8的非完全边界能量图恰好存在6个(见图4).
图4 6个具有8个顶点的非完全边界能量图
命题3[15] 顶点数为9的非完全边界能量图恰好存在17个(见图5).
图5 17个具有9个顶点的非完全边界能量图
当顶点数为10时，Li等[20]通过计算机搜索到49个非完全边界能量图.当顶点数为11时，Shao等[21]以同样的方式搜索到158个非完全边界能量图.故当顶点数不超过11时，所有非完全边界能量图已全部到.然而当顶点数很大时，也存在非完全边界能量图，而且存在大量的这样的图.接下来将通过如下几种方式展示如何构造非完全边界能量图.
方式1 图的张量积.两个图G1和G2的张量积G1⊗G2, 是以V(G1)×V(G2)为点集，两个顶点(u1,u2)与(v1,v2)相邻，当且仅当u1v1∈E(G1)和u2v2∈E(G2). 基于张量积，则有定理6.
定理6[15] 设G是一个边界能量图，假设G是两个整谱图G1和G2的张量积，则|V(G1)|和|V(G2)|都是奇数.
方式2 强正则图.设G是具有n个顶点的k-正则非完全图，如果满足每对相邻顶点有a个共同的邻点，每对不相邻的顶点有c个共同的邻点，则称G是一个具有参数(n,k,a,c)的强正则图.在(n,k,a,c)-强正则图G中，如果其邻接谱满足
即特征根1的重数为1，特征根的重数为mθ, 特征根的重数为mτ, 其中Δ=(a-c)2+4(k-c), m0和mτ满足m0+mτ=n-1和m0θ+mττ=-k, 而且mθ=mτ, 则称图G为一个会议图.基于这种形式的强正则图，则有定理7.
定理7[15] 设G是一个会议图，而且满足是整谱的和非完全边界能量的，则G具有参数(9,4,1,2).

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。