【摘要】 设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-连通图的一些性质.更多还原

【Abstract】 Let G be a finite,undirected and simple connected graph,p and q be positive integers.An edgecut(vertex-cut)S of G is a p-q-edge-cut(p-q-vertex-cut),if one componet of G-S contains at least p vertices and another component of G-S contains an least q vertices,G is called λp,q-connected(kp,q-connected),if a p-q-edge-cut(p-q-vertex-cut) exists.Let λp,q(G)(kp,q(G)) be the minimum cardinality of a p-q-edge-cut(p-qvertex-cut)of G.We prove some sufficient conditions for a graph to be kp,q(G)≤λp,p(G)(p≤q and give some properties of k1,p-connected graphs.更多还原