几类特殊有向循环图的核

The Kernel in Special Directed Circular Graphs

有向图D=(V,A)的核K是顶点集V的一个子集,其中K中任意两点在D中均不相邻,并且对V\K中任意一个点v,都存在K中的一个点u,使得(v,u)是D中的一条弧.一般有向图核的存在问题是NP-完全的.Bang-Jensen和Gutin在他们的著作[Digraphs:Theory, Algorithms and Applications, London:Springer-Verlag, 2000]中提出公开问题(Problem 12.3.5):刻画有向循环图核存在性.本文研究了几类特殊有向循环图核的存在问题,并给出了Duchet核猜想(对任意一个不是有向奇圈的无核有向图,都存在一条弧,使得删除这条弧所得到的图仍然是无核的)的一类反例.

A kernel in a directed graph D =(V, A) is a set K of vertices of D such that no two vertices in K are adjacent and for every vertex v in V\K there is a vertex u in K, such that(v, u) is an arc of D. It is well known that the problem of existence of a kernel is NP-complete for a general digraph. Bang-Jensen and Gutin posed an interesting problem(Problem 12.3.5) in their book [Digraphs: Theory, Algorithms and Applications, London: Springer-Verlag, 2000]: to characterize all circular digraphs with kernels. In this paper, we study the problem of existence of the kernel for several special classes of circular digraphs. Moreover, a class of counterexamples is given for the Duchet kernel conjecture(for every connected kernel-less digraph which is not an odd directed cycle, there exists an arc which can be removed and the obtained digraph is still kernel-less).