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

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

作　　者：高敬振[1] 

机构地区：[1]山东师范大学数学科学学院,济南250014

出　　处：《系统科学与数学》2011年第12期1602-1612,共11页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(10901097);山东省自然科学基金(ZR2010AQ003);山东省高等学校科技计划(J10LA11)资助项目

摘　　要：在已有的极大边连通、超级边连通、极大局部边连通有向图概念的基础上,提出超级局部边连通有向图的概念,对一般的、二部的、基础图的团数至多为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.

关 键 词：边割 极大边连通有向图 超级边连通有向图 极大局部边连通有向图 超级局部边连通有向图 

分 类 号：O157.5[理学—数学]