特殊度条件下有向图的最大有向割

Maximum directed cuts of digraphs with special degree restrictions

对于整数k,l≥0,用D(k,l)表示一类有向图的集合,这类图的每个顶点要么入度不超过k要么出度不超过l.研究了度条件下有向图中的最大有向割问题,目的是确定图类D(k,l)中有向图的最大有向割包含的弧的条数.对于包含m条弧的有向图,通过分析图的结构,采用数学归纳法,得到(1)若D∈D(2,3)∪D(3,2),则存在至少包含2m/7条弧的有向割;(2)设D∈D(k,k),若存在顶点集的一个二部划分(X,Y),使得X中点的入度与Y中点的出度都不超过k,并且起点在X中终点在Y中的弧的集合的导出图的基础图不含圈,则存在至少包含(1/4+1/(8k+4))m条弧的有向割.

For integers k,l≥0, let D（k,l） denote the family of digraphs in which every vertex has either indcgree at most k or outdegree at most l. The maximum directed cut problem on digraphs with constrained indcgrcc or outdegree is investigated, and the aim is to find the maximum size of a directed cut in digraphs in D （ k, l）. For a digraph D with m arcs, the following results are proved by using mathematical induction： （ 1 ） If D E D （2, 3） UD（3,2）, then m has a directed cut with at least 2m/7 arcs. （2） IfD∈D（k,k） has a bipartition （X,Y） of the vertex set such that each vertex in X（Y） has indegree （outdegree） at most k, and the underlying graph of the digraph which is induced by the set of arcs with heads in X and tails in Y contains no cycle, then D has a di- rected cut with at least （ 1/4 ＋ 1/（8k ＋4） ）m arcs.