图的代数连通度及其点连通度

G是一个简单图.a(G),k(G)分别为G的代数连通度和点连通度,该文刻画了满足a(G)=k(G)的图.G=(V,E)是一个n阶简单图,点连通度为k(G)≤[n/2].H是G的任意最小点割集,则a(G)=k(G)当且仅当对任意u∈H和v∈V\H,有uv∈E.     

给定匹配数的图的代数连通度的上界

【目的】确定给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图。【方法】首先,利用图的匹配数与奇连通分支个数的关系与图的变换等方法刻画了给定匹配数的n个点图的拉普拉斯代数连通度上界所对应的极图;其次,利用具有相同邻点集的图与对应特征值的关系得到给定匹配数的n个点图的拉普拉斯代数连通度上界。【结果】借助图与补图的关系以及拉普拉斯特征方程证明得到给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图是一一对应且唯一确定的,从而同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图。【结论】用全新的方法同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图,克服了以往利用图的最小度,最大连通度与代数连通度的关系只刻画了给定匹配数的图中具有最大代数连通度的图类特征,但无法得到此类图的连通度的上界这一弊端。     

关于图的代数连通度的注记

n阶连通图G的代数连通度、点连通度和边连通度分别记作α(G) ,κ(G)和λ(G) .本文给出了当 2 κ(G) n- 2时 ,α(G) =κ(G)成立的充要条件 ,讨论了α(G)的代数重数以及相应于特征值α(G)的特征向量的性质 .最后给出了当 1 λ(G) n- 2时 ,α(G) =λ(G)的充要条件 .     

拟正则图的最大边边连通度

定义了图的边边连通度，设计了一类具有最大边边连通度的拟正则图。     

给定最大度的树的代数连通度

研究给定最大度的树在移接变形下的代数连通度的变化.这些结果可以用来刻画给定最大度和顶点个数的树中具有最小代数连通度的极图,并且给出了该极图的代数连通度的一个下界.     

Ln,p图的代数连通度

Kp表示p阶完全图.选取Kp的任意r个顶点分别点粘接r棵树,得到n阶图Ln,p.所有n阶图Ln,p的集合记为（L）n,p.代数连通度是刻画图的连通性的重要参数,笔者分别确定了Ln,p中具有最大、最小和第二小代数连通度的图.     

双圈图的N-G型的代数连通度的界

对任一个n阶单图G,用a(G)表示G的代数连通度,GC表示它的补图.针对双圈图,即边数等于顶点数加1的且只含有2个边不交的基本圈的简单连通图,证明了对任一n阶双圈图G,有1≤a(G)+a(GC),当且仅当G≌G1时等式成立.     

3—连通正则无爪图的Hamilton圈

证明了每一个3－连通k-正则无爪图G，当G的点数n≤5k-5时，G包含一个Hamilton圈。     

Nordhaus-Gaddum型的代数连通度的界

对任一个n阶单图G,用a(G)表示G的代数连通度,Gc为G的补图.通过代数连通度与Laplacian谱半径的关系,给出了几类图的Nordhaus-Gaddum的代数连通度的和的界.     

双圈图的N—G型的代数连通度的界

对任一个凡阶单图G,用0（G）表示G的代数连通度,Gc表示它的补图．针对双圈图．即边数等于顶点数加1的且只含有2个边不交的基本圈的简单连通图,证明了对任一n阶双圈图G,有1≤a（G）＋a（G^C）,当且仅当3G兰G1时等式成立．     

单圈图的Laplacian谱

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

关于图的超常边连通度和等周边连通度的等值性

图的超常边连通度和等周边连通度是图的通常边连通度概念的推广，首先举例说明在一般情形下两者可以不等，然后再论证明当正则边可迁图的阶不小于3k时，它的k阶超常边连通度与k阶等周边连通度相等。     

树的移接变形与代数连通度

讨论了树的代数连通度.利用移接变形给出树的代数连通度的一种变化关系,同时给出了两类树的代数连通度与直径的关系.     

笛卡尔乘积图的限制边连通性

设G是一个极大限制边连通k-正则图,k≥2．论文证明了：如果│G│〉2k且n≥3,那么笛卡尔乘积图Pn×G是超级限制边连通的,除非G包含子图Kk;如果│G│〉k＋1且n≥3,那么Cn×G是超级限制边连通的,除非n=3且G是圈．