有向图的边割(X,Y)中|X|和|Y|的下界与有向图的极大性和超级性

LOWER BOUNDS OF |X| AND |Y| OF EDGE-CUT(X,Y) AND MAXIMALITY AND SUPERIORITY OF A DIGRAPH

在已有的极大边连通、超级边连通、极大局部边连通有向图概念的基础上,提出超级局部边连通有向图的概念,对一般的、二部的、基础图的团数至多为p的有向图、定向图分别给出|(X,Y)|<δ(D)的边割(X,Y)、非平凡的最小边割(X,Y)中|X|和|Y|的下界,据此分别得到极大边连通、超级边连通有向图的最小度条件.类似地分别得到满足|(X,Y)|≤min{d^+(u),d^-(v)}-1的u-v边割(X,Y)、非平凡的λ(u,v)-边割(X,Y)中|X|和|Y|的下界,据此分别得到极大局部边连通、超级局部边连通有向图的最小度条件.

Motivated by the existing concepts of maximally edge-connected digraph, super-edge-connected digrapn and maximally local-edge-connected one,the concept of superlocal -edge-connected digraph is proposed.Lower bounds of ｜X｜and ｜Y｜ of edge-cut（X,Y） with ｜（X,Y）｜δ（D） and of nontrivial minimum edge cut（X,Y） for arbitrary,bipartite digraphs and oriented graphs as well as ones with clique number at most p are settled,respectively.Making use of them,minimum degree conditions for a digraph to be maximally edge-connected and super-edge-connected are derived.Analogously lower bounds of ｜X｜ and ｜Y｜ of u—v edge-cut （X,Y） with ｜（X,Y）｜≤min{d~＋（u）,d~＋（v）}—1 and of nontrivial minimumλ（u—v） edge-cut are presented;and then minimum degree conditions for maximally local-edge-connected and super-local-edge-connected digraphs are yielded.