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

References

[1] Apartsin A., Ferapontova, E. , Gurvich, V. . A circular graph—counterexample to the Duchet kernel conjecture. Discrete Math. 1998; 178(1/2/3): 229–231

[2] Bang-JensenJ.GutinG., Digraphs: Theory, Algorithms and Applications, London: Springer-Verlag, 2000

[3] BergeC., Graphs, Volume 6, Amsterdam: North Holland Publishing Co., 1985

[4] Berge C. , Duchet, P. . Recent problems and results about kernels in directed graphs. Discrete Math. 1990; 86(1/2/3): 27–31

[5] Boros E. , Gurvich, V. . A corrected version of the Duchet kernel conjecture. Discrete Math. 1998; 179(1/2/3): 231–233

[6] ChvátalV., On the computational complexity of finding a kernel, Report NO. CRM-300, Centre de Recherches Mathématiques, Montreal: Université de Montréal, 1973

[7] Duchet P. . Graphes noyau-parfaits. Ann. Discrete Math. 1980; 9: 93–101

[8] Fraenkel A. . Planar kernel and Grundy with d ≤ 3, d_out ≤ 2, d_in ≤ 2 are NP-complete. Discrete Appl. Math. 1981; 3(4): 257–262

[9] Kwaśnik . The generalization of Richardson theorem. Discuss. Math. 1981; 4: 11–14

[10] ManuelP., Rajasingh, I., Rajan, B.. and Punitha, J., Kernel in oriented circulant graphs, In: Combinatorial Algorithms, Lecture Notes in Comput. Sci., Vol. 5874, Berlin: Springer-Verlag, 2009, 396–407

[11] Richardson M. . Solutions of irreflexive relations. Ann. of Math. (2) 1953; 58: 573–590

[12] Szwarcfiter J. , Chaty, G. . Enumerating the kernels of a directed graph with no odd circuits. Inform. Process. Lett. 1994; 51(3): 149–153

[13] Van LeeuwenJ., Having a Grundy-numbering is NP-complete, Report No. 207, Computer Science Dept., University Park, PA: Pennsylvania State University, 1976

[14] Von NeumannJ.. and Morgenstern, O., Theory of Games and Economic Behaviour, Princeton: Princeton Univ. Press, 1994

RIGHTS & PERMISSIONS

Higher Education Press 2025