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

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.     

正则图的代数连通度

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

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

【目的】确定给定匹配数的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时等式成立.     

树的代数连通度的极限点的分布

文章通过研究双星图的代数连通度的极限点 ,给出树的代数连通度的极限点的分布范围 :[0,(3- 5)/2] ,以及分布情况的一个结论 : ε>0 ,至少存在一个树类 ,其代数连通度的极限为r>0 ,且r<ε。     

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

文章利用图G的代数连通度与其线图的邻接谱半径之间的关系,给出:任n阶拟双星图G ,s0-1相似文献   

给定控制数的树的代数连通度的上界

讨论了给定控制数的树的代数连通度的上界,并对极图给出了刻画.     

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

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

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

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

定向图连通度的下界

有向图和二部有向图连通度的下界已由Hellwing和Volkmann给出.定向图是没有二圈的有向图.文章研究了这类特殊的有向图-定向图,同时通过改进Hellwing等人的证明方法,得到了定向图和二部定向图连通度的更好的下界.     

简单连通图的反比度和几何反比度

反比度和几何反比度是Ｇｒａｆｆｉｔｉ猜想程序中首先出现的关于图的两个量。本文研究了它们的性质，从面确定其上下界。     

图有较高连通度的一个充要条件

图的连通性理论是图论学科重要而基础的研究领域,通过该领域的研究,人们对图的结构和性质有了进一步的认识,并且将所得到的结果应用于网络设计、城市交通等实际问题中,取得了很多应用成果,例如,量化一个图或网络的脆弱程度,便始于图的连通性研究。因此,我们总是希望图能具有较高的连通度。对n个顶点的图G来说,当连通度不小于顶点数n的一半时,我们认为这个图有较高的连通度。本文试图给出图具有较高连通度的一个充分必要条件。我们指出,对一个给定的正整数k且k≤2n,有κ(G)≥n-k成立当且仅当对顶点集V(G)的任意一对不交子集S和T,G[S,T]有一个完美匹配,这里|S|=|T|=k,G[S,T]=G[S∪T]-E(G[S])-E(G[T])。     

基于代数连通度的软件定义网络节能算法

软件定义网络(software defined network,SDN)在快速发展中面临许多新挑战,其中能耗问题尤为突出.学者们提出了许多节能方案,但目前已有的方案存在依赖传统网络背景,需要实时流量数据,不易部署,连通稳定性兼顾不全等问题.因此,提出一种基于代数连通度的软件定义网络节能算法(energy saving ...     

连通图的拟拉普拉斯谱半径的一个上界

对于连通图G,矩阵Q(G)=D(G) A(G)称为图G的拟拉普拉斯矩阵,其中D(G)为图的度对角矩阵,A(G)为图的邻接矩阵.本文利用矩阵的一些性质,推导出连通图的拟拉普拉斯谱半径的一个上界.并将该上界与已有的一些结论结合具体图例作了优越性比较.     

强乘积图的连通度

用k1＞0和δi表示图Gi(i=1,2)的连通度和最小度,给出了无向图强乘积的连通度一个下界κ(G1(□×)G2)≥min{κ1(1+δ2),k2(1+δ1)}.