Ln,p图的代数连通度

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

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

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

正则图的代数连通度

设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表示正则图的度.     

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

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

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

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

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

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

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

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

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

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

多重图的线图连通度

提出了多重图的线图的概念,研究了多重图的线图连通度的上界和下界.刻画了图的最小度与其线图连通度的关系:若δ(G)≥μ([p/2] 1),则kl(G)≥δL(G)-2(μ-1),并通过构造出一系列的图,证明此结果是最好的:条件不能够被削弱,结论不能够被加强.同时,揭示了图的限制性边连通度就是线图连通度,推广了已有文献的结果.     

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

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

线图连通度的界

首先给出了线图连通度K_L的一个上界:K_L≤δ+Δ-2;其次得出了在条件δ≥[n/2]+1下K_L的一个很好的下界:K_L≥2δ-2;由此得到当δ≥[n/2]+1时,若G为正则图,则K_L=2δ-2,若G为拟正则图,则K_L=2δ-2或2δ-1.     

单圈图的Laplacian谱

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

2-边-轨道图的点连通性

本文研究2-边-轨道图的点连通性问题,给出关于Ⅱ-类和Ⅲ-类2-边-轨道图点连通度等于最小度的充分条件。     

点可迁图的顶点划分

设G是k正则连通点可迁图。图G的一个边割S称为限制性边割，如果G－S不含孤立点，最小限制性边割所含的边数λ′称为限制性边连通度。已经证明λ′≤2k-2，等号成立时，称图G是极大限制性边连通的。本文证明了：如果G不是极大限制性边连通的，那么G的顶点集存在一个划分π＝（C1，…，Cm)，使得由Ch导出的子图同构于一个连通k-1正则点可迁图H,h=1,2，…，m，而且k≤|H|≤2k-3。     

含有两个基本圈的简单图的N-G型代数连通度的界

对任一个n阶简单图G,用a（G）表示G的代数连通度.在已有文献研究的基础上,通过分类研究和个别图具体研究,证明了对任一含有两个基本圈的简单图G,有1≤a（G）＋a（Gc）.