设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-连通图的一些性质.
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 Ap,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.