极小强连通有向图

Minimal Strong Connected Digraphs

强连通有向图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.