几类特殊有向循环图的核  

The Kernel in Special Directed Circular Graphs

作　　者：任秀秀 杨卫华 REN Xiuxiu;YANG Weihua(College of Mathematics,Taiyuan University of Technology,Taiyuan,Shanxi,030024,P.R.China)

机构地区：[1]太原理工大学数学学院,太原山西030024

出　　处：《数学进展》2019年第2期137-144,共8页Advances in Mathematics（China）

基　　金：国家自然科学基金资助课题(Nos.11671296)

摘　　要：有向图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).

关 键 词：核 有向图 循环图 Duchet核猜想 

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