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.