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

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

强乘积图的限制边连通度

文章研究了两连通图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阶限制边连通度最优的一个充分条件

设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-最优的.     

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

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

图是极大限制边连通的一个充分条件

设G是n阶简单无向连通图,G的限制边割是删除它以后G不连通,且留下的每个分支不含孤立点的边子集;限制边割的最小基数称为限制边连通度.记G的顶点x的度为d(x)。证明了若对超级连通图G中任意一对不相邻的顶点x和y都有d(x) (dy)n,则G是极大限制边边通的当且仅当G不同构一种特殊图G。     

有关连通度一定理证明方法的探讨

有关图的连通度结论k(G)≤λ(G)≤δ(G),在图论中是一个很重要的定理,下面用一种与传统证明方法不同的新方法对此定理进行了证明.     

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

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

全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-图的边连通性.