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

• 作者: 白延东
• 来源期刊: 纺织高校基础科学学报
• 关键词: 有向图 度条件 最大有向割
• 年，卷（期）: 2010,（4）
• 页码范围: 473-475
• 分类号: O157.5
• 语种: 中文
• DOI: 10.3969/j.issn.1006-8341.2010.04.018

摘要

对于整数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条弧的有向割.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	白延东	西北工业大学应用数学系	1	0	0.0	0.0