一般图与二部图中完美匹配关于距离无符号拉普拉斯谱半径的存在性

令D(G)=(D_(i,j))为连通图G的距离矩阵,其中D_(i,j)等于顶点v_(i)和v_(j)之间的距离.令η1(G)为图G的距离无符号拉普拉斯谱半径,即距离无符号拉普拉斯矩阵Q(G)=Diag(Tr)+D(G)的最大特征值,其中Diag(Tr)为对角矩阵,Diag(Tr)_(ii)=Σ_(vivj∈E)(G)D_(i,j).在本文中,我们研究图中完美匹配的存在性与距离无符号拉普拉斯谱半径之间的关系,并分别给出关于距离无符号拉普拉斯谱半径的一般图和二部图存在完美匹配的充分条件.

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

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

距离无符号拉普拉斯谱半径的一个注记

本文提出三种使得距离无符号拉普拉斯谱半径变小的图的嫁接变换,并确定了距离无符号拉普拉斯谱半径取得最小值的恰有k个圈且含有悬挂顶点的n阶仙人掌图.

给定团数的图的距离无符号拉普拉斯谱半径

设G是n阶简单连通图,T(G)表示图G的点传递度对角矩阵,D(G)表示距离矩阵,G的距离无符号拉普拉斯矩阵定义为:Q(G)=T(G)+D(G),相应的谱半径(即最大特征值)记作q^D(G).图G中一个相互邻接的顶点子集称为G的一个团,定义G的团数为其最大团的顶点个数,记作ω(G).图G的一个正常着色是指使得G中任意2个相邻的顶点着不同颜色的一种着色方案.在G的所有正常着色中,所需颜色数目的最小值称为G的色数,记作!(G).显见,!(G)≥ω(G).为了研究给定团数ω(G)=ω的n阶简单连通图G中取得最小距离无符号拉普拉斯谱半径的极图,文中综合运用代数、矩阵论与图论等方法,分如下2种情形进行讨论:(1)!(G)=ω(G)=ω;(2)X(G)>ω(G)=ω.证明了Turan图T_(n,ω)是团数为ω的n阶简单连通图中具有最小距离无符号拉普拉斯谱半径的唯一图.

变换为团路的团树的距离无符号拉普拉斯谱半径

若一个连通图G的点集是V(G)={v_1,v_2,…,v_n}.图G的距离矩阵D(G)=(d_(ij)),其中dij表示点v_i与v_j之间的距离.Tr_G(v_i)表示点v_i到图G所有其他点的距离之和,Tr(G)表示i行i列位置的元素是Tr_G(v_i)的对角矩阵.G的距离无符号拉普拉斯矩阵QD(G)=Tr(G)+D(G).QD(G)的最大特征值λQ(G)是图G的距离无符号拉普拉斯谱半径.本文分别确定了变换为团路的团树中具有最大与最小的距离无符号拉普拉斯谱半径的极图.

关于图的距离无符号拉普拉斯谱半径的下界

若一个连通图G的点集是V(G)={v1,v2,…,vn},那么图G的距离矩阵D(G)=(dij),其中dij表示点vi与vj之间的距离.令TrG(vi)表示点vi到图G中其他所有点的距离之和,Tr(G)表示i行i列位置的元素TrG(vi)的对角矩阵.图G的距离无符号拉普拉斯矩阵QD(G)=Tr(G)+D(G).QD(G)的最大特征值λQ(G)是图G的距离无符号拉普拉斯谱半径.该文确定了给定匹配数的n个点的图的距离无符号拉普拉斯谱半径的下界.

含割边的连通图最小距离无符号拉普拉斯谱半径

在所有含割边的n阶连通图中,利用特征值与特征向量的关系,刻画了具有最小距离无符号拉普拉斯谱半径的图的结构,在此基础上,给出了含割边的n阶连通图的距离无符号拉普拉斯谱半径的一个下界。

非平衡符号双圈图的拉普拉斯谱半径的排序

研究了非平衡符号双圈图的第一到第六大的拉普拉斯特征值的分布规律,完善了现有结论中一些不准确的情况,推广了现有的结果,并给出了取得极值情况的图例。

给定点连通度的图的补图的无符号拉普拉斯谱半径

假设G是一个具有点集V(G)={v_(1),v_(2),…,v_(n)}和边集E(G)的连通简单图,矩阵Q(G)=D(G)+A(G)被称为图G的无符号拉普拉斯矩阵,其中D(G)和A(G)分别是图G的度对角矩阵和邻接矩阵。称矩阵Q(G)的最大特征值为图G的无符号拉普拉斯谱半径。图G的补图记为G^(c)=(V(G^(c))),E(G^(c)),这里V(G^(c))=V(G)和E(G^(c))={xy|x,y∈V(G),xy∉E(G)}.文章在给定点连通度且直径大于3的图的所有补图中,确定了无符号拉普拉斯谱半径达到最小时的唯一图。

双圈图的补图的无符号拉普拉斯谱半径

设D(G)和A(G)分别是图G的度矩阵和邻接矩阵,则Q(G)=D(G)+A(G)就是G的无符号拉普拉斯矩阵。让Un3是把n−3条悬挂边粘到3圈C3上的一点后得到的单圈图,θn∗是把n−4条悬挂边粘到θ (2,1,2)的一个三度点得到的双圈图。在这篇文章里我们证明了,取得最大无符号拉普拉斯谱半径的单圈图和双圈图分别是Un3和θn∗。

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

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

图的Hamilton性与无符号拉普拉斯距离谱半径

本文利用图及其补图的无符号拉普拉斯距离谱半径分别给出了一个图包含Hamilton路、Hamilton圈以及是Hamilton连通图与泛圈图的充分条件。

循环图的无符号拉普拉斯谱半径

给出一个图G,称矩阵Q=D+A为无符号拉普拉斯谱矩阵,其中A表示G的邻接矩阵,D表示G的顶点度对角矩阵.研究了循环图的无符号拉普拉斯谱半径的上界,得到了几个有意义结果.进一步,讨论了循环图的卡氏积图的无符号拉普拉斯谱半径上界.

一些图的无符号拉普拉斯谱半径

令A(G)表示G的邻接矩阵,Q(G)=D(G)+A(G)是G的无符号拉普拉斯矩阵,Q(G)的最大特征值是G的无符号拉普拉斯谱半径.在这篇文章中,我们分别确定了给定点连通度、给定块数和给定悬挂点数的图类中无符号拉普拉斯谱半径最大的图的结构.

三圈图的无符号拉普拉斯谱半径

假设图G的点集是V(G)={v_1,v_2,…,v_n},用d_(v_i)(G)表示图G中点v_i的度,令A(G)表示G的邻接矩阵,D(G)是对角线上元素等于d_(v_i)(G)的n×n对角矩阵,Q(G)=D(G)+A(G)是G的无符号拉普拉斯矩阵,Q(G)的最大特征值是G的无符号拉普拉斯谱半径.现确定了所有点数为n的三圈图中无符号拉普拉斯谱半径最大的图的结构.

图的无符号拉普拉斯谱半径的一个新上下界（英文）

D为图的G度序列对角矩阵,A为图的邻接矩阵.Q=D+A为图的无符号拉普拉斯矩阵.Q的最大特征值ξ(G)称为图G的无符号拉普拉斯谱半径.这里将图的2度,平均2度等概念推广到k度与平均k度,得到了图的关于无符号拉普拉斯谱半径的一个新的上、下界.最后举例与图的几个已知经典的界进行了比较.

无符号拉普拉斯谱半径的新上界

如果一个图存在定向满足其最大出度△^+不超过最大度△的一半,则通过估计图的半边路径(semi-edge walk)的个数,得到了该图的无符号拉普拉斯谱半径的一个新上界.进而根据D.Goncalves对平面图边分解的结果,得到了平面图无符号拉普拉斯谱半径的一个新上界.

具有最小距离拉普拉斯谱半径的双圈图（英文）

一个连通图的距离拉普拉斯矩阵的最大特征值称为这个图的距离拉普拉斯谱半径.本文中,我们先得到距离拉普拉斯谱半径的一个好的下界,然后利用这个下界确定了单圈图中具有最小距离拉普拉斯谱半径的唯一极图.最后,再次利用这个下界,并结合距离拉普拉斯矩阵的特征多项式确定出了双圈图中具有最小距离拉普拉斯谱半径的极图.

距离无符号拉普拉斯整谱的完全r-部图（英文）

对一个n个顶点的图G,G的距离无符号拉普拉斯矩阵记为D^Q(G)=Tr(G)+D(G),其中Tr(G),D(G)分别表示G的顶点传输矩阵及其距离矩阵.G的距离无符号拉普拉斯特征多项式(或简称D^Q-多项式)是DQ/G(λ)=|λI_n-D^Q(G)|,其中I_n是n×n阶单位矩阵.如果G的所有D^Q-特征值都是整数,称图G是距离无符号拉普拉斯整谱图.本文将给出完全r-部图是距离无符号拉普拉斯整谱图的一个必要充分条件,从而构造出无穷多类新的距离无符号拉普拉斯整谱图.

偶数顶点不含四圈图的无符号拉普拉斯谱半径(英文)

G是一个简单图,矩阵Q(G)=D(G)+A(G)记为图G的无符号拉普拉斯谱半径,其中D(G)和A(G)分别为对角元素为图G顶点度的对角阵和图G的邻接矩阵.本文证明了图G是偶数顶点不含四圈的图,G*是G中有最大无符号拉普拉斯谱半径的图,ρ是G*的无符号拉普拉斯谱半径,则ρ3-ρ2-(n-1)ρ+1-d3u+d2u-∑(du+di)di≤0,对于u∈V(G*).