The kernel in special directed circular graphs

Abstract

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).

Keywords

Kernel / directed graph / circular graph / Duchet kernel conjecture

RIGHTS & PERMISSIONS

Higher Education Press 2025