传递图中的限制性边连通度

设G=(V，E)是一个连通图，S包含于E是一个边子集，如果G—S不再连通，且G—S的每一个连通分支都至少含有r个点，则称S为一个r-限制性边割．最小r-限制性边割中所含的边数为G的r-限制性边连通度，记作λ(G)．如果对所有的i=1，…，r，λ(G)都达到其最大可能值，则称G为λ-最优图．王铭和李乔证明了：若G是一个d-正则的点传递图，d≥4，围长g≥5，或者G是一个d-正则的边传递图，d≥4，围长g≥4，则G是λ（g-1)-最优图．本文推广了这一结果，证明了：在同样的条件下，G是λg-最优图．     

极大限制边连通超图的两个充分条件

图的限制边连通度是经典边连通度的推广,可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到r一致线性超图H,证明当H的最小度δ(H)≥r+1时,H的最小边度ξ(H)是它的限制边连通度λ′(H)的一个上界,并将满足ξ(H)=λ′(H)的H称为极大限制边连通超图,然后证明n个顶点的r一致线性超图H如果满足δ(H)≥(n-1)/(2(r-1))+(r-1),则它是极大限制边连通的,最后证明直径为2,围长至少为4的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广.     

图是λ3-最优和超级-λ3的范型条件

设G是有限简单无向图,使G-S的每个分支都包含至少k个点的边割S称为G的k-限制边割。G的k-限制边连通度λk(G)是G的k-限制边割之中最少的边数。定义ξk(G)=min{[U,U-]:U V(G),|U|=k,G[U]是连通的},若λk(G)=ξk(G),则称G是λk-最优的。若任意最小k-限制边割都孤立一个k阶分支,则称图G是超级-λk的。应用范型条件给出了图是λ3-最优和超级-λ3的充分条件。     

kp,q（G）≤λp,p（G）成立的一些充分条件

设G是简单有限无向连通图,p,q是两个正整数.G的一个边割(顶点割)S是一个p-q-边割(p-q-顶点割),如果G-S不连通,且G-S中有一个分支至少含有p个顶点,另一个分支至少含有q个顶点.G称为λp,q-(kp,q-)连通的,如果一个p-q-边割(p-q-)顶点割存在.用λp,q(G)(kp,q(G))表示最小p-q-边割(p-q-顶点割)的基数.文章证明了在kp,q-连通(p≤q)和λp,p-连通图G中,使kp,q(G)≤λp,p(G)成立的一些充分条件及k1.p-连通图的一些性质.     

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

设G是一个λ5-连通图,定义ξ5(G)=min{|[X,X]|:X■V(G),|X|=5,G[X]是连通子图},若λ5(G)=ξ5(G),则称G是λ5-最优图.文章给出了满足顶点数v≥17且最小度δ≥v/2-4的λ5-连通图G在一定特殊条件下是λ5-最优图的一个充分条件.     

图中顶点子集的边连通度与最优分级边连通图的构造问题

G =(V ,E)是无向连通图 ,无环允许有重边 .S是V的至少包含两个顶点的子集 ,S的边连通度λG(S)被定义为使S中的顶点不属于同一连通分支所需去掉的最少边数 .给定集合V和V的一个划分V =V1∪V2 ∪…∪Vr(|r|≥ 1,|V1|≥ 2 )以及正整数序列k1>k2 >… >kr≥ 2 .记Si=V1∪V2 ∪…∪Vi,1≤i≤r.构造一个连通图G =(V ,E)满足 :λG(Si)≥ki(1≤i≤r)且边数 |E|最小 .这种图G称为与所给划分和正整数序列相对应的最优分级边连通图 .在给出顶点子集的边连通度概念的基础上 ,本文提出并讨论了有关最优分级边连通图的构造问题     

几类图的相邻顶点可区别的全染色

给出了几类特殊图相邻顶点可区别的全色数,如双路间和二部(V1,V2)间叠加匹配形成的系列图、双圈(prism)、双轮.并得到边连通度λ(G)=1的图相邻顶点可区别的全染色的性质.     

无向de-Bruijn图的超级边连通性和限制性边连通度

super-λ和限制性边连通度是两个比边连通度更能刻画网络可行性的参数。本文证明了无向无向de-Bruijn图UB（d,n)是super-λ（d≥2,n≥2)。对n≥4，我们证明了UB（2,n)的限制性边连通度为4；UB（2，3）的限制性边连通度是3。对d≥3我们指出UB(d,n)(n≥3)的限制性连连通度λ‘，满足2d-2λ‘≤4d-4。     

图的超级限制边连通性

在Moor-Shannon网络模型中,边连通度和限制边连通度较大的网络一般有较好的可靠性和容错性.本文证明:除两种平凡情形外,无向Kautz网络的拓扑结构,无向Kautz图UK(2,n)是超级限制边连通的.因此,它们比de Bruijn网络有更好的限制边连通性.     

可迁图的超常边连通度的最优性

图的超常边连通度是图的边连通度概念的推广.对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λh一定存在(1≤h≤n/2).本文证明了当dr正则的n-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d-正则的n-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h1≤h≤min{g-1,n/2},λh达到其最大可能值,即λh=hd-2(h-1).