几类特殊有向循环图的核

摘要

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