极小强连通有向图  

Minimal Strong Connected Digraphs

作　　者：徐志霞[1,2] 

机构地区：[1]南开大学组合数学中心,天津300071 [2]新疆大学数学与系统科学学院,新疆乌鲁木齐830046

出　　处：《厦门大学学报（自然科学版）》2009年第5期627-631,共5页Journal of Xiamen University：Natural Science

基　　金：国家自然科学基金(10601044)资助

摘　　要：强连通有向图D称为极小的,若在D中删去任意一条弧,则所得的有向图不是强连通的.讨论了极小强连通有向图的耳朵分解的一些性质,构造了非平面极小强连通有向图的例子,证明了极小强连通图的点色数至多是3,并且当极小强连通图的耳朵分解中每个耳朵的长度不小于4时,它有两个不相交的准核.最后确定了给定顶点数的极小强连通有向图的弧数的界,刻画了相应的极图.A strong connected digraph D is called minimal,if thedeletion of any are from D will result in a digraph that is not strong connected. In this paper we discuss the properties of ear-decompositions of minimal strong digraphs, construct a family of nonplanar minimal digraphs and prove that the chromatic number of minimal digraphs is at most 3. Furthermore,we prove that if the length of each ear is no less than 4 in the ear-decomposition of the minimal digraph D,then there are two disjoint quasi-kernels in D. We also determine the bounds for the number of arcs in minimal strong digraphs and characterize completely the corresponding extremal digraphs.

关 键 词：强连通有向图 极小强连通有向图 耳朵分解 准核 

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