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...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 the existence of a kernel is NP-complete for a general digraph.Bang-Jensen and Gutin pose 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 the 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).展开更多
文摘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 the existence of a kernel is NP-complete for a general digraph.Bang-Jensen and Gutin pose 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 the 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).
