强乘积图的限制边连通度

文章研究了两连通图G1和G2的强乘积图G1G2的限制边连通度,给出了强乘积图的限制边连通度的一个上界,并确定一类特殊强乘积图的限制边连通度.     

图是极大3限制边联通的充分条件

设S是连通图G中的一个边子集。若G S不连通且它的每个连通分支的阶至少为k,则称S是G的一个k限制边割。图G的最小k限制边割的边数称为G的k限制边连通度,记为λκ(G)。定义ξκ(G)=min{|［X,X］|:|X|=k,G［X］连通},其中X=V(G)＼X。若λk (G)=ξk(G),则称G是极大k限制边连通的。设G是一个围长至少为5的λ3 连通图。本文证明了若G中不存在5个点u1,u2,v1,v2,v3使得d(ui,vj)≥3(i=1,2;j=1,2,3),则G是极大3限制边连通的。     

图是超级λk-连通(k=4,5)的一个Ore型充分条件

图的k阶限制边连通度λk（G）对衡量网络可靠性起重要的作用．本文给出图是超级λk（k=4,5）连通的一个Ore型条件．     

λ（m）≤ξm（G）的一般充分条件

已经证明，当m≤3时，λ（m）-连通图G满足λ（m）（G）≤ξm（G）。当m≥4时，Bonsma等人指出不等式λ（m）（G）≤ξm（G）一般不再成立。最近，欧见平证明阶大于等于11的λ4-连通图G满足λ4（G）≤ξ4（G）.本文通过研究满足λ（m）（G）〉ξm（G）的λm-连通图所具有的结构性质，不仅易得以上结论，还得到如下一般结论：当m≥5时，阶大于m（m-1）的λm-连通图G均满足λm（G）≤ξm（G）.最后，通过构造例子说明本文给出的条件是最好的.     

图是λ4-最优及超级-λ3的最小度条件

为精确估计网络的可靠度,我们需要最优化其图模型的限制边连通度,证明一个n≥11阶最小度δ(G)≥[n/2]-3的λ4-连通图G,在一定的条件下是λ4-最优的.进而,若n≥12,则G是超级-λ3图.并举例说明了最小度的下界是最好可能的.     

全P_k-图的边连通性(英文)

图G的Pk-路图Pk(G)是以G的k-长路构成的集合为点集,这两个路在Pk(G)中相邻当且仅当这两个k-长路在G中的交为一个k-1-长路且并未一个k+1-长路或者k-长圈时.令Ek={(v,p):p∈V(Pk(G)),v是图Pk(G)的一个顶点},定义全Pk-图Tk(G)如下:Tk(G)=(V(G)∪V(Pk(G)),E(G)∪E(Pk(G))∪Ek).该文研究全Pk-图的边连通性.     

给定边连通度的图的最小距离谱半径(英文)

本文研究了边连通度为r的n阶连通图中距离谱半径最小的极图问题,利用组合的方法,确定了K(n-1,r)为唯一的极图,其中K(n-1,r)是由完全图K_(n-1)添加一个顶点v以及连接v与K_(n-1)中r个顶点的边所构成.上述结论推广了极图理论中的相关结果.     

λ_4-最优图的一个充分条件

文章给出了λ4-最优图的一个充分条件.设G是阶为n≥11的λ4-连通图,若对G中任意一对不相邻顶点u,v,有｜N（u）∩N（v）｜≥6且G｜N（u）∩N（v）｜至少包含16条边,则G是λ4-最优的.     

无向Kautz图的超级限制边连通性

限制边连通度作为边连通度的推广,是计算机互连网络可靠性的一个重要度量.Superλ-′是比限制边连通度更精确的一个网络可靠性指标.一个图是Superλ-′的,如果它的任一最小限制边割都孤立一条有最小边度的边.本文考虑一类重要的网络模型-无向K autz图UK(d,n)的限制边连通度λ,′证明了当d 3,n 2时,λ(′UK(d,n))=4d-4,并进一步指出此时的UK(d,n)是Superλ-′的.