Resistance Distance and Kirchhoff Index of a Class of Join Graphs

For some complicated graphs obtained by graph operations,it is very difficult to compute resistance distance and Kirchhoff index.Define a new graph operation,and obtain a class of new join graphs:the subdivision-vertex-vertex join G_1* G_2.Then,describe the Laplacian matrix of the graph G_1 * G_2 and use generalized inverse of the Laplacian matrix to get formulas for resistance distance and Kirchhoff index.Through the obtained formulas,the resistance distance of any pairs of vertices and Kirchhoff index of the join graph can be computed.     

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

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

关于图Cn1,n2,n3,n4及Cp,q,s的邻接谱

图的谱确定问题是图论中的一个重要问题,它是根据已知的特征值去确定图形,一般说来这是一件很困难的事.图论界的许多学者研究了一些特殊情形,主要涉及图的邻接谱(或图的Laplacian谱)的研究,其研究的一般途径是通过图的邻接矩阵(或Laplacian矩阵)表示,建立图的拓扑结构(特别是图的各种不变量).通过矩阵论,以及组合矩阵论中的经典结论,用于图的拓扑结构的研究.在已有文献的基础上研究了Cn1,n2,n3,n4图和Cp,q,s图的邻接谱问题,得到了不同构的Cn1,n2,n3,n4图及Cp,q,s图没有相同的邻接谱这个结论.     

直径为n-1,n-2和n-3的树的补图的奇异性

利用图谱理论对树的补图的奇异性进行了研究,得到了直径为n-1,n-2和n-3的树的补图的奇异性的一般判断方法,推广了前人的研究成果.     

给定独立数的双圈图的最大拟拉普拉斯谱半径

设(B)(n,α)是独立数为α的n阶双圈图,(B)1(n,α)是由(B)(n,α)中含有两个边不交的圈构成的双圈图子集,(B)2(n,α)=(B)(n,α)＼(B)1(n,α).文中分别研究了(B)1(n,α)和(B)2(n,α)中具有最大拟拉普拉斯谱半径的极图.进一步地,得到了(B)(n,α)中拟拉普拉斯谱半径的上界...     

拟无爪图的性质

讨论了比无爪图更广泛的图——拟无爪图,得到了以下两个结果： (ⅰ)　若图G是拟无爪图,且满足ω(G-S)≤t(G), 则2t(G)=κ(G). (ⅱ) 若图G是拟无爪图,对于任意的控制集D及任意t∈D,至多存在3点u1,u2,u3∈(V-D)满足N(ui)∩D={t}(i=1,2,3), 则γ(G)=i(G),该结果是最好可能的. 以上结果扩展了无爪图的相应结果.     

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

设G=（y,E）是n阶简单连通图,D（G）和A（G）分别表示图G的度对角矩阵和邻接矩阵,则L（G）=D（G）-A（G）称为G的拉普拉斯矩阵利用图的度序列,平均二次度和图的公共邻点数结合非负矩阵谱理论给出了L（G）的最大特征值的一些上界．     

双圈图的Laplacian谱展

设G是一个简单连通图,矩阵L(G)=D(G)-A(G)称为图的Laplacian矩阵,其中D(G)是图的度对角线矩阵,A(G)是G的邻接矩阵.连通图G的Laplacian谱展是图的最大特征值与次小特征值之差.边数等于顶点数加1的连通图叫做双圈图.研究了双圈图的Laplacian谱展,并确定了具有最大Laplacian谱展的双圈图.     

图的广义距离特征值

图G的广义距离矩阵定义为D_α(G)=αTr(G)+(1-α)D(G),0≤α≤1,其中D(G)和Tr(G)分别表示图G的距离矩阵和传递度对角矩阵.研究了广义距离相关谱,给出了其谱半径、第二大特征值的界,及自补图的广义距离谱.     

圈的定向距离图的性质

图G的两个定向D与D’的定向距离d0（D,D＇）是指与D’同构的定向与D之间不相同的弧数的最小值．G的定向距离图D0（G）的顶点是互不同构的定向,如果d0（D,D＇）=1,则D与D在D0（G）中相邻,并获得定向距离图D0（Cn）的性质．     

6-连通图最长圈上的可收缩边

 图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图一些性质的有力工具。设G是一个6-连通图,e∈E（G）,若收缩e后得到的图仍是6-连通的,则称e是G的可收缩边。采用树型结构理论进行分类讨论,得到如下结论：① 如果P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,xi xi+1是一条不可收缩边,且S={xi,xi+1,u1,u2,u3,u4}是其对应的6-点割,则G-S的每一个断片至少包含P上的一个点;② 设P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,且G的任意断片的阶都大于2。如果P上任意顶点xi都满足条件d（xi）≥7或者若d（xi）=6则[V（P）]中无3-圈包含它,那么P上至少包含一条可收缩边。在上述结论的基础上,进一步研究了任意断片阶都大于2的6-连通图中最长圈上的可收缩边的分布情况,得到如下新结果：任意断片阶都大于2的6-连通图最长圈上至少有两条可收缩边。     

强正则图的能量

设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|.利用代数和图论的方法,得到了五一正则图的最大和最小能量,以及最大、最小拉普拉斯能量,并刻划了能量取到最值时对应的图的结构.     

图的Laplacian矩阵谱半径

设G为n阶简单连通图,若L(G)为图G的度对角矩阵与邻接矩阵的差,则称L(G)为图G的Laplacian矩阵.结合非负矩阵谱理论,利用图的顶点度和平均二次度给出了图G的Laplacian矩阵的谱半径的新上界,同时给出了达到上界的极图.     

单圈图的Laplacian谱

G 是一个图，A（G），D（G）分别是G 的邻接矩阵和顶点度序列对角矩阵，则矩阵L（G）=D（G）-A（G）称为G 的Laplacian 矩阵。作者考察了单圈图的Laplacian 矩阵的谱性质，并着重讨论了单圈图的代数连通度。     

基于图谱归一化编辑距离的聚类算法

图之间的距离度量一直是研究的难点之一。文中提出了一种基于图谱归一化编辑距离的聚类方法。首先利用图的谱方法实现图中点的排序,再用串编辑距离进行两图之间的相似性度量,以此距离构成的不相似矩阵,应用基于矩阵理论的聚类算法实现序列图的聚类研究。考虑到图中点的多少差异,给出归一化串编辑距离的方法解决长短谱序列间距离差异误差问题。实验表明,基于图谱归一化编辑距离的聚类方法是有效的。     

5-连通图的可收缩边的分布

图的可收缩边问题对于研究图的结构和证明图的某些性质有着重要作用。本文给出了5-连通图中某些最长圈可收缩边的分布情况,用树型结构理论进行分类讨论,得到如下结论:不含2-断片的5-连通图的最长圈上至少有三条可收缩边。     

一种基于图论的LDPC码构造算法的研究

在对低密度奇偶校验(LDPC)码进行分析的基础上,提出了一种基于图论的构造算法.该算法从对LDPC码的校验矩阵进行图论分析入手,分析了组成校验矩阵中的圈的校验点之间的关系,得出了由这些校验点对应的结构图是彼此同构的欧拉图的定理,利用这个定理以及根据定理得到的性质,可以通过构造一个辅助的校验点结构图的邻接矩阵,渐进地生成LDPC码的校验矩阵,在生成的过程中避免短长度圈的出现.仿真实验表明提出的算法对中短码长的LDPC码构造具有良好的性能.     

关于D-图的注记

为了研究具有完美匹配图的Tutte集和极端集,D Bauer等提出了一种新的图运算D-图,并且得到许多有趣的性质.本文研究了基本图的水平,证明了对于任何非二部的基本图,它的D~2(G)是一个完全图.此外,还给出了饱和图G的D-图的刻画,并且对于一般图的情形做出了分析.     

近双三图的两个定理

本文考虑一类有向图(一近双三图)的性质,用归纳法证明一些近双三图中存在一些特别的子图—可调形。     

图的空间理论:与图有关的线性代数理论 (上)

对图的空间理论(尤其是圈空间)进行了总结: 介绍了目前在这个方面的重要理论, 结果和方法. 与经典的组合矩阵等方法不同的是, 本文侧重于介绍各种数域上的有限空间理论和方法对于图的组合结构的作用和影响.