单圈图的Seidel无符号拉普拉斯能量

设G是一个具有n个顶点、m条边的简单图,S(G)表示G的Seidel矩阵,d_i表示顶点v_i的度,又以DS(G)=diag(n-1-2d_1,n-1-2d_2,…,n-1-2d_n)来表示对角矩阵,再依次定义图G的Seidel拉普拉斯矩阵为SL(G)=DS(G)-S(G)、图G的Seidel无符号拉普拉斯矩阵为SL~+(G)=DS(G)+S(G)和图G的Seidel无符号拉普拉斯能量为■,这里σ1L+,σ2L+,…,σnL+为矩阵SL+(G)的特征值.文章利用不等式讨论单圈图G的Seidel无符号拉普拉斯能量的上界,得到了几个有意义的结果.     

图的Seidel Laplacian-Estrada指标

设G为简单图,d_i表示顶点v_i的度,G的Seidel Laplacian矩阵S_L(G)是一个对角元为n-1-2d_i,非对角元为±1的实对称矩阵,当顶点v_i和v_j相邻时,(S_L(G))_(ij)=1,否则,(S_L(G))_(ij)=-1。引入并研究了Seidel Laplacian矩阵的Estrada指标,给出了该指标的上、下界,以及它与Seidel Laplacian能量之间的关系。     

双圈图的Seidel无符号拉普拉斯能量

设G是具有顶点n,边数m的简单图。定义G的Seidel无符号拉普拉斯能量为Seidel无符号拉普拉斯矩阵的特征值与■的差的绝对值之和。文中利用不等式技巧讨论了双圈图的Seidel无符号拉普拉斯能量的上界,得到了几个有意义的结果。     

正则图的代数连通度

设G=(V,E)是一个具有n个顶点的简单图,A(G)是G的邻接矩阵,D(G)表示G的度对角矩阵,图G的拉普拉斯矩阵定义为L(G)=D(G)-A(G).若矩阵L(G)的特征值为μ1≥μ2≥…≥μn-1≥μn=0,则称μn-1为G的代数连通度.研究了正则图的代数连通度,得到了下列结论:μn-1≤(nrln(n-l))/(6n-8-4r-nln(n-1))这里,r表示正则图的度.     

强正则图的能量

设G是阶为n边数为m的简单图,λ1,λ2,…,λn是G的邻接矩阵的特征值,μ1,μ2,…,μn是G的拉普拉斯矩阵的特征值.图G的能量定义为E(G)=n∑i=1|λ1|,拉普拉斯能量LE(G)=n∑i=1|μ1-2m/n|.利用代数和图论的方法,得到了五一正则图的最大和最小能量,以及最大、最小拉普拉斯能量,并刻划了能量取到最值时对应的图的结构.     

具有固定顶点的树的代数连通度

设G是一个n阶简单连通图,图G的邻接矩阵记为A(G),令D(G)是G的顶点度对角矩阵,定义G的拉普拉斯矩阵L(G)=D(G)—A(G),设L(G)的特征值为λ_1≥λ_2≥…≥λ_(n-1)≥λ_n=0.在本文中,采用移接变形方法,讨论了树的代数连通度和直径之间的关系,获得了下面的结论:当树的顶点数固定时,树的代数连通度随着树的直径的增加而减少.进一步地,利用Cauchy-Schwarz不等式,讨论了树的代数连通度的界.     

Cartesian积图的最大拉普拉斯特征值

设G=(V(G)),E(G)),H=(V(H),E(H))是两个简单的连通图,定义与的Cartesian积G×H图是:其顶点集为V(G×H)=V(G)×V(H),其中任何两个顶点(u,u’),(v,v’),相邻当且仅当u=v且u’,v’在H中相邻;或u’=v’且u,v在G中相邻,这里u,v∈V(G),u’,v’∈V(H).本文研究两个图的Cartesian图的拉普拉斯矩阵的最大特征值,得到如下结论:设简单图G具有n顶点m条边,图H具有P个顶点q条边,那么G和H的Cartesian积图G×H的拉普拉斯最大特征值p(L(G×H))≤2m/n[1+(n-1)(((n3/4m2)-(1/n-1))～(1/2))]+((2p-1)～(1/2))+1.     

与图Zeta函数相关的一个函数的导数值

设G是含有n个顶点和ε条边的图,G的Zeta函数可以表示为ZG(u)=(1-u2)n-ε/f(u),其中f(u)=det(I-uA (G)+u2(D (G)-I)),A(G)与D (G)分别表示G的邻接矩阵与度对角矩阵。分别利用正则图的TU子图的权重ω和二部图的顶点n和边数ε来表示相应的f′(-1)的值。     

图的路(无符号)拉普拉斯谱半径及其能量

图G的顶点集V(G)={v₁,v₂,…,v_n},其路矩阵记为P(G)=(p_ij)_n×n,p_ij表示图中v_i,v_j之间内部顶点不相交路径的最大数目。定义路拉普拉斯矩阵和路无符号拉普拉斯矩阵并得到了其谱半径和能量的界。     

具有n-3个悬挂点的树的距离无符号拉普拉斯谱半径(英文)

一个连通图G的距离无符号拉普拉斯谱半径是G的距离无符号拉普拉斯矩阵的谱半径.G的距离无符号拉普拉斯矩阵定义为Q(G)=Tr(G)+D(G),这里Tr(G)是G的顶点传递的对角阵,且D(G)是G的距离矩阵.研究了所有n阶具有n-3个悬挂点的树的距离无符号拉普拉斯谱半径的极小值,并刻画了一类n阶具有n-3个悬挂点的树的距离无符号拉普拉斯谱半径的极大值与极小值.     

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

设G=(V,E)是一个具有顶点集■的简单图,顶点v_i的度数用d_i表示。定义图G的扩展矩阵■,这里■。定义图G的扩展谱半径为其扩展矩阵的最大特征值;定义图的扩展能量E_(ex)(G)为扩展邻接矩阵特征值的绝对值之和。利用分析和基本不等式技巧,得出了单圈图的扩展谱半径与能量的几个上界。     

关于边连通度与最小线度

本文主要证明了下面的结论: 设G是一个有n个顶点的简单田,若G中任何K(k≤4)个顶点v_1,…,v_k满足d(v_1)+d(v_2)+…+d(v_k)≥k/2(n-2)-1/2 则λ(G)=σ(G)。     

双圈图和三圈图的最大拉普拉斯分离度(英)

设G是一个n阶无向简单图,L(G)是G的拉普拉斯矩阵,且μ_1(G)≥μ_2(G)≥…≥μ_n(G)是L(G)的特征值.G的拉普拉斯分离度定义为SL(G)=μ_1(G)-μ_2(G).研究了给定阶数的双圈图和三圈图的最大拉普拉斯分离度,并刻画了相应的极图.     

完全四部图的Seidel多项式及其谱

设G是一个简单无向图,A(G)是图G的(0,1)邻接矩阵.定义S(G)=J-I-2A(G)是图G的Seidel矩阵,SG(λ)=det(λI-S(G))是图G的Seidel特征多项式(本文中简记为Seidel多项式),其中I是单位矩阵,J是全1矩阵.如果SG(λ)的特征值都是整数,则图G被称为是S-整图.本文主要研究完全四部图G=Kn1,n2,n3,n4的Seidel多项式及SG(λ)的特征根,给出了完全四部图Kn1,n2,n3,n4是S-整图的充要条件.     

树的最大与次小Laplacian特征值和的上界

随着计算机技术和网络技术的不断发展,图的谱被广泛应用于网络拓扑结构的特征分析,Laplacian矩阵的谱(特别是最大特征值和次小特征值)在网络结构中扮演重要角色.设G=(V,E)是一个具有n个顶点的简单图,A(G)为G的邻接矩阵,D(G)为G的度对角矩阵.定义G的Laplacian矩阵为L(G)=D(G)-A(G),设L(G)的特征值为μ1(G)≥μ2(G)≥…≥μn-1(G)≥μn(G)=0,最大特征值μ1(G)称为图G的Laplacian谱半径;次小特征值μn-1也称作图G的代数连通度.本文讨论了树的L(G)的最大与次小特征值和μ1(G)+μn-1(G)的上界,得到几个有意义的结论.     

三角化图的团划分数

在本文,我们证明了下述结果:(1)如果G=(V,E)是72个顶点的三角化图,则K(G)=α(G)≤cc(G)≤cp(G),cc(G)≤n-1,其中图G顶点独立数为α(G),它可在O(|V|+|E|)时间内求出;(2)如果G=(V,E)是n个顶点的特殊三角化图,V=S∪K,具有度序列为n-1≥d_1≥d_2≥…≥d_n,若对于S中任意顶点对x_i,x_j有|Adj(x_i)∩Adj(x_i)|≤1,则α(G)≤cp(G)≤α(G)+δ,其中,m=w(G)是图G的最大团的顶点个数。     

有向图的无符号拉普拉斯谱半径的新上下界

设G是一个n阶的简单有向连通图,令A(G)为有向图G的邻接矩阵,D(G)为有向图G的出度对角矩阵,则有向图G的无符号拉普拉斯矩阵可以表示为Q(G)=A(G)+D(G).利用图中顶点v_i的出度d_i~+和平均二次出度m_i~+,给出一些有向图G的无符号拉普拉斯矩阵谱半径q_1(G)更精细化的上下界,并通过数值例子证实新上下界的有效性.     

图的最大拉普拉斯特征值的上界

设G=(V,E)是n阶简单连通图,D(G)和A(G)分别表示图的度对角矩阵和邻接矩阵,L(G)=D(G)-A(G)则称为图G的拉普拉斯矩阵。利用图的顶点度和平均二次度结合非负矩阵谱理论给出了图的最大拉普拉斯特征值的新上界,同时给出了达到上界的极图,并且通过举例与已有的上界作了比较,说明在一定程度上优于已有结果。     

双圈图的(无符号)拉普拉斯积和多项式的刻画性质

令G为n个顶点的图,L(G)与Q(G)分别表示图G的拉普拉斯矩阵和无符号拉普拉斯矩阵。多项式π(L(G);x)=per(xI-L(G))(或π(Q(G);x)=per(xI-Q(G)))称为G的拉普拉斯积和多项式(或无符号拉普拉斯积和多项式)。在本文中,证明了两类双圈图是(无符号)拉普拉斯积和多项式确定的。     

边界能量图研究的综述

图G的能量ε(G)定义为其邻接矩阵特征根的绝对值之和.设G是一个具有n个顶点的图,如果G的能量值等于n个顶点的完全图的能量值2(n-1),则称图G为边界能量图.介绍了近年来关于边界能量图研究方面的主要结果.