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

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

具有拟极小Cayley集的Cayley图的限制性边连通度

研究具有拟极小Cayley集的Cayley图的限制性边连通度，证明了除少数例外，具有拟极小Cayley集的Cayley图是最优超级边连通的。     

关于欧拉图的一个猜想的新结果

证明了非平面欧拉图在边连通度满足一定条件下可以表示成不超过｜Ｖ｜－２个边不重的圈的并,其中｜Ｖ｜是图的顶点数。     

点可迁图的限制边连通度

设S是连通图G的边子集.如果G-S不连通而且不含孤立点,那么称S是G的一个限制边割.G中所有限制边割中最小边数称为G的限制边连通度,记为′(G).限制边连通度是对传统边连通度的推广,而且是计算机互连网络容错性的一个重要度量.点可迁图是一类重要的网络模型.本文证明了如下结论 设G是连通的点可迁图.如果G的点数n4,而且点度k2,那么或者′(G)=2k-2,或者n是偶数,G含三角形且存在整数m2,使得k′(G)=n/m2k-3.     

折叠交叉立方体的分支边连通度

r-分支连通度(边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且r是非负整数,如果G中存在某种点子集(边子集)使得G删除这种点子集(边子集)后得到的图至少有r个连通分支.则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的r-分支连通度(边连通度).n-维折叠交叉立方体FCQn是由交叉立方体CQn增加2n-1条边后所得.该文利用r-分支边连通度作为可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到了折叠交叉立方体网络的2-分支边连通度,3-分支边连通度,4分支边连通度.确定了折叠交叉立方体FCQn的r-分支边连通度.     

无向广义De Bruijn图的m-限制边连通性

m-限制边割将连通图G分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图G的m-限制边通度,记作λm（G）.对于包含m-限制边割的连通图G,有λm（G）≤ξm（G）（m≤3）;如果λm（G）=ξm（G）,则称图G是极大m-限制边连通的.本文证明：当n≥7时,无向广义De Bruijn图UBG（2,n）是极大m-限制边连通的（m={2,3}）.     

k阶限制边连通度最优的一个充分条件

设S是图G的一个边子集,若G-S不连通且每个分支的阶至少为k,则称S为G的一个k-限制边割.若G有k-限制连割,G的最小k-限制边割的边数称为G的k阶限制边连通度,记为λk(G).记ξk(G)=min{|[X,]|∶|X|=k,G|X|连通},若λk(G)=ξk(G),则称G是λK-最优的.证明了若对G中任意一对不相邻的顶点x,y都有d(x) d(y)≥n 2(k-2),且G不是G*k图,则G是λk-最优的.     

图是λ3-最优的最小度条件

为精确估计网络的可靠度,我们需要最优化其图模型的限制边连通度.本文证明了一个n阶连通图,当n≥10且最小度至少为[n/2]-2时,在一定的条件下这个图是λ3-最优的,并举例说明了这些条件的下界是最好可能的.     

k元n方体网络的4-限制边连通度

l-限制边连通度是边连通度的推广,可更精确地度量网络的可靠性.k元n方体网络因其特殊的结构和良好的性质成为多处理机系统最常用的互连网络之一.证明了k元n方体的4-限制边连通度和它的最小4-度相等,并确定了它们的值.所得结果说明,当用4-限制边连通度作为度量指标时k元n方体是可靠的.     

图的λ_k最优性和超级性(k=2,3)的邻域交与边度条件

本文给出了图的λk最优性和超级性(k=2,3)的用邻域交与边度表示的充分条件.