Kernel And Hamiltonian Of Several Special Directed Circular Graphs

A kernel in a directed graph=(（1,）is a setof vertices ofsuch that no two vertices inare adjacent and for every vertexin(1?there is a vertexin,such that（,）is an arc of.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 open problem（Problem 12.3.5）in their book[Digraphs:Theory,Algorithms and Ap-plications,Springer,London]:characterize all circular digraphs with kernels.In the second chapter,we first study the problem of existence of the kernel for several special classes of circular digraphs₉)（1,）,₉)（1,,+1）and₉)（1,2,···,）.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 exist an arc which can be removed and the obtained digraph is still kernel-less）.In the third chapter,the hamiltonian of the directed cyclic graph₁₂₈)(3,4,（8）is s-tudied.We mainly prove that the circulai digraph₁₂₈)（3,4,128）-3)and₁₂₈)（3,4,128）-4)have hamiltonian cycles.