On the existence of (k,)-kernels in digraphs
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.
- On the existence of \(k\)-kernels in digraphs and in weighted digraphs
- A sufficient condition for the existence of k-kernels in digraphs
- On the existence of \((k, l)\)-kernels in digraphs with a given circumference
- On the existence of \((k,l)\)-kernels in infinite digraphs: a survey
- On the existence of (k,k-1)-kernels in directed graphs
- k-Kernels and some operations in digraphs
- On (k,l)-kernels in D-join of digraphs
- Some sufficient conditions for the existence of kernels in infinite digraphs
- On the existence and the number of (2-d)-kernels in graphs.
- A new generalization of kernels in digraphs
- A parity digraph has a kernel
- On the existence of kernels and h-kernels in directed graphs
- On the existence of 3- and 4-kernels in digraphs
- Kernels in digraphs with covering number at most 3
- Absorbant of generalized de Bruijn digraphs
- On the existence of \((k, l)\)-kernels in digraphs with a given circumference
- The depression of a graph and \(k\)-kernels
- On the existence of \((k,l)\)-kernels in infinite digraphs: a survey
- On the existence and the number of (2-d)-kernels in graphs.
- A construction that preserves the number of k-kernels
- Cyclically k-partite digraphs and k-kernels
- (k,l)-kernels in line digraphs
- Extending digraphs to digraphs with (without) \(k\)-kernel
- On the existence of (k,k-1)-kernels in directed graphs
- Kernels and k-kernels in orientations of the path graph
- A sufficient condition for the existence of k-kernels in digraphs
- scientific article; zbMATH DE number 579329 (Why is no real title available?)
- Semikernels and (k,l)-Kernels in Digraphs
- Kernels in Cartesian products of digraphs
- A dichotomy for the kernel by H‐walks problem in digraphs
- On the number of quasi-kernels in digraphs
- scientific article; zbMATH DE number 915661 (Why is no real title available?)
- (k,)-kernels in P_m+e
- \(k\)-kernels in digraphs formed by some operations from other digraphs
- A new generalization of kernels in digraphs
- The kernel in special directed circular graphs
- k-Kernels and some operations in digraphs
- On the existence of \(k\)-kernels in digraphs and in weighted digraphs
- On the kernel and related problems in interval digraphs
- \(k\)-kernels in multipartite tournaments
- The theorem of Richardson and its generalizations: a survey
- \(\Pi\)-kernels in digraphs
- Almost all digraphs have a kernel
This page was built for publication: On the existence of (k,\(\ell)\)-kernels in digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q805626)
