Kernel

Kernel --- ядро.

An independent set [math]\displaystyle{ S }[/math] of vertices in a digraph such that, for each [math]\displaystyle{ x \in V(G) \setminus S }[/math], there exists [math]\displaystyle{ y \in S }[/math] such that [math]\displaystyle{ (x,y) \in E(G) }[/math]. See also Independent set, Semikernel.

When every induced subdigraph of a digraph [math]\displaystyle{ D }[/math] has a kernel, [math]\displaystyle{ D }[/math] is said to be kernel-perfect. [math]\displaystyle{ D }[/math] is a critical kernel-imperfect digraph if [math]\displaystyle{ D }[/math] does not have a kernel but every proper induced subdigraph of [math]\displaystyle{ D }[/math] has at least one.

[math]\displaystyle{ (k,k-1) }[/math]-Kernel --- [math]\displaystyle{ (k,k-1) }[/math]-ядро. A subset [math]\displaystyle{ J \subset V(G) }[/math] is said to be a [math]\displaystyle{ (k,k-1) }[/math]-kernel of [math]\displaystyle{ G }[/math] if the following properties hold:

(1) for each two distinct vertices [math]\displaystyle{ x,y \in J, \; d_{G}(x,y) \geq k }[/math],

(2) for each [math]\displaystyle{ x' \in V(G) \setminus J }[/math], there exists [math]\displaystyle{ x \in J }[/math] such that [math]\displaystyle{ D_{G}(x',x) \leq k-1 }[/math].

In addition, a subset containing only one vertex is also called a [math]\displaystyle{ (k,k-1) }[/math]kernel of [math]\displaystyle{ G }[/math].

Note that for [math]\displaystyle{ k = 2 }[/math] the definition reduces to the definition of a kernel of a graph [math]\displaystyle{ G }[/math].