图变换及其在图的最小无符号拉普拉斯特征值的应用

假定G是一个带有点集V(G)={v_(1),v_(2),···,v_(n)}的连通简单图,图G的邻接矩阵A(G)=(a_(ij))_(n×n),其中点vi与点vj相邻,则a_(ij)=1;否则a_(ij)=0。我们定义度矩阵D(G)=diag(dG(v_(1)),dG(v_(2)),···,dG(v_(n))),其中dG(v_(i))是图G中点v_(i)(1≤i≤n)的度数。定义图G的无符号拉普拉斯矩阵Q(G)=D(G)+A(G),因为Q(G)是一个半正定矩阵,所以可将其特征值设为λ_(1)(G)≥λ_(2)(G)≥···≥λ_(n)(G)≥0,其中特征值λn(G)也称为图G的最小无符号拉普拉斯特征值。对补图的最小无符号拉普拉斯特征值问题进行了研究,报告了相关问题的研究现状,给出了两种图变换,并且应用他们去确定所有双圈图的补图中最小无符号拉普拉斯特征值取最小的唯一图。

给定悬挂点的非平衡符号图的最小拉普拉斯特征值

符号图是边赋值为±1的一类图.设符号图Γ的拉普拉斯矩阵为L(Γ)=D(G)-A(Γ),这里D(G)表示度矩阵, A(Γ)表示符号图的邻接矩阵.Γ是平衡的当且仅当最小拉普拉斯特征值λn=0.因此当Γ非平衡时λn>0.本文研究了非平衡符号图的最小拉普拉斯特征值问题.利用图特征值的嫁接方法,获得了给定悬挂点非平衡符号图的最小拉普拉斯特征值,并且刻画了达到最小特征值的极图.

符号图网拉普拉斯最大特征值的一个上界

本文给出了符号图Γ的网拉普拉斯最大特征值κ1的上界:σ(ij)表示边ij的符号;Ni,Ni+和Ni−分别表示顶点i的邻域、正邻域和负邻域;|U|表示集合U中所含元素的个数。

图的第四大无符号拉普拉斯特征值的一个下界(英文)

设G是一个阶数大于等于4的简单连通图.K_4(G)和d_4(G)分别表示G的第四大无符号拉普拉斯特征值和第四大度.本文证明了k_4(G)≥d_4(G)—2.

给定最小度和边连通度的图的最大无符号拉普拉斯谱半径

利用无符号拉普拉斯谱半径与特征向量之间的关系式,研究有n个顶点、最小度为δ且边连通度k′<δ的这一类图中无符号拉普拉斯谱半径最大的图。假设G0是这一类图中无符号拉普拉斯谱半径最大的图,证明G_(0)≌B_(n,δ)^(k′),其中B_(n,δ)^(k′)是从K_(δ+1)和K_(n-δ-1)之间加入k′条边获得的。

无符号拉普拉斯谱半径与图的若干性质

对于给定的简单图G,如何判断图G具有某种结构性质,这一问题一直广受图论学者们的青睐。由于图的谱能够很好地反映图的结构性质且便于计算,近年来,诸多学者利用图谱理论来研究图的相关性质。首先找到了原图对应结构性质的稳定性,其次构造原图的对应闭包,最后利用反证法,根据补图的无符号拉普拉斯谱半径分别给出了具有较大最小度的图G是s-连通、s-边-连通、s-路-覆盖、s-哈密尔顿、s-边-哈密尔顿、s-哈密尔顿-连通或α(G)≤s的充分条件。

无符号拉普拉斯谱半径与图的哈密尔顿性

在结构图论中,图的哈密尔顿性的谱刻画是最具有影响力的课题之一,其主要思想是判断一个图是不是哈密尔顿图,这是NP-完全问题。因此,诸多学者对哈密尔顿性问题的研究主要集中在寻找适当的充分条件。本文借助补图的无符号拉普拉斯谱半径来刻画具有较大最小度的图的哈密尔顿性。首先,采用反证法构造了原图的闭包,将原图是否具有某性质转化到其闭包中;其次对闭包补图的结构进行了合理的分类讨论;最后分别给出了具有较大最小度的图G是哈密尔顿的,哈密尔顿-连通的以及从任意点出发可迹的关于无符号拉普拉斯谱半径的充分条件。

图的Sum-connectivity指标与其无符号拉普拉斯谱半径

设G=(V,E)为简单连通图.图G的Sum-connectivity指标被定义为χ(G)=Σuv∈E(G)2/√d_(u)+d_(v),其中d_(u)表示顶点u的度.用q(G)表示图G的无符号拉普拉斯谱半径.本文研究了χ(G)与q(G)之间的关系,证明了对于所有顶点数n≥3的简单连通图G,都有q(G)/χ^(2)(G)≤n^(2)/(n-1)^(2)等式成立当且仅当G■S_(n).

曲面上图的拉普拉斯谱半径(英文)

本文研究了图嵌入到给定紧致曲面上的拉普拉斯谱半径,确定了将顶点数为n、最大度为的图分别嵌入到亏格为g的定向曲面和亏格为h的不可定向曲面上的新上界.

图的2-边覆盖与拉普拉斯谱

覆盖图是指对原图G进行边和顶点的变化新得到一个图H,且G和H之间保持同态的关系,若图G的每2条边对应图H中的一条边,就称图H是G的一个2-边覆盖图。本文将证明图G的拉普拉斯谱可由它的2-边覆盖图H的两个变化图的谱而得到。

关于图的最小Q-特征值

研究了基于n阶二部图和s阶完全图构造的一个图类,得到了该图类的无符号拉普拉斯最小特征值(即最小Q-特征值)的一个可达上界为s.基于此,对于任意给定的正整数s和正偶数n,构造了最小Q-特征值为s的一类n+s阶图.另外,对于任意给定的最小度δ和阶数n,在满足2≤δ≤n-1/2条件下,构造了最小Q-特征值为δ-1的一类n阶图.

图经广义并接运算后的(无符号拉普拉斯)特征值的一些结论（英文）

设G是一个顶点集为{u_1,u_2,…,u_n}的点标号图,H_1,H_2,…,H_n是n个顶点不交的图,将图G中的顶点u_i(i=1,2,…,n)用图H_i代替,若点u_i与点u_j在G中相邻,则连接H_i与H_j中的所有的点,这样得到的图定义为G[H_1,H_2,…,H_n].本文确定了图G[H_1,H_2,…,H_n]的Q-特征多项式和A-特征多项式.最后,作为应用,构造了很多对(无符号拉普拉斯)-同谱图,并给出了一些关于特殊图类的Q-特征值和A-特征值的不等式序列.

最小Q-特征值为给定整数的一类图

研究了基于二部图H构造的一类图的最小无符号拉普拉斯特征值,即最小Q-特征值,得到了它的最小Q-特征值的可达上界为1.给出了最小Q-特征值为1的2个必要条件,并构造了最小Q-特征值为1的一类图.另外,给出了利用H∨K1的最小Q-特征值来判断简单图H没有完美匹配的方法,以及图G增加边后最小Q-特征值保持不变的1个充分条件.最后,构造了最小Q-特征值为任意给定的正整数t的一类图.

图的无符号拉普拉斯特征值α次幂总和的界

令G为简单图.sα（G）等于图G的无符号拉普拉斯特征值α次幂的总和,其中α为实数且α≠0,1.本文我们得到一些连通图的sα（G）的新的界,并给出了正则图的Mycielskian图、正则图及半正则二部图的Double图这些特殊图类的sα（G）的新的界.由这些结论的特殊情况可得到相应图的关联能量的界.

含一个割点的连通图的最小特征值

一个图的无符号拉普拉斯最小特征值在某个图类中的所有图中达到最大时常称为极大图;通过利用特征向量方程研究特征值的方法,对只含有一个割点的连通图的无符号拉普拉斯最小特征值进行了研究,且得到了最小特征值的值,从而得到了只含有一个割点的具有相同阶数的所有的连通图中最小特征值的极大值,并且刻画了最小特征值取到极大值时所对应的极大图的结构.

补图是独立数为n-2的双圈图的最小特征值

图的邻接矩阵的最小特征值定义为图的最小特征值,图的无符号拉普拉斯矩阵的最小特征值定义为图的无符号拉普拉斯最小特征值,它们都是刻画图的结构性质的重要参数。本文在给定阶数且补图是独立数为n-2的双圈图的图类中,分别刻画了最小特征值与无符号拉普拉斯最小特征值并且达到极小图。

恰有两个Q-主特征值的三圈图

图G的无符号拉普拉斯矩阵定义为图G的邻接矩阵与度对角矩阵的和,其特征值称为图G的Q-特征值.图G的一个Q-特征值称为Q-主特征值,如果它有一个特征向量其分量的和不等于零.确定了所有恰有两个Q-主特征值的三圈图.

图的第四大Q-特征值的一个下界

给出了图的第四大Q-特征值的一个下界.

图的Q-特征值的若干结果

研究了删点集对图的无符号拉普拉斯谱(Q-谱)的影响,给出了删点集插值定理.进一步,得到了一个下界q_i(G)≥d_i-i+1(i=1,2,…,n),其中q_i(G)为n阶图G的第i大Q-特征值,d_i为第i大顶点度.另外,给出了q_i(G)≥d_i-1(i=2,…,k)成立的一个充分条件,以及等号成立的必要条件等.

符号图的一些谱关系(英文)

符号图Σ=(|Σ|,σ)由无符号图|Σ|=(V,E)和一个映射组成,其中V和E分别为顶点集和边集,|Σ|是它的基础图,σ:E→{+1,-1}是符号函数.文章给出了一些符号图的谱关系,并得到了符号图的特征值的一些边界.