On the existence of (k,\(\ell)\)-kernels in digraphs (Q805626)

A kernel in a digraph D is a set of vertices S such that no two vertices of S are joined by an arc and for every vertex \(x\not\in S\) there exists a vertex \(s\in S\) and an arc from s to x. Let k and \(\ell\) be natural numbers with \(k\geq 2\) and \(\ell \geq 1\). A set \(S\subseteq V(D)\) is a (k,\(\ell)\)-kernel of the digraph D if: (1) for each pair of vertices x, \(x'\in S\), the length of a shortest directed path with endvertices x, \(x'\) is at least k, (2) for each \(v\not\in S\), there exists an \(x\in S\) such that the shortest directed path from x to v is at most \(\ell.\) Hence a kernel is a (2,1)-kernel. A k-kernel is the same as a (k,k-1)- kernel. The paper presents some results on k-kernels and (k,\(\ell)\)- kernels in digraphs which generalize at theorem by P. Duchet: If every directed cycle of odd length in a digraph D has at least two symmetrical arcs (arcs which are in a directed 2-cycle), then D has a kernel.