On the existence of (k,k-1) - kernels in directed graphs
Dorota Bród, Andrzej Włoch, Iwona Włoch · Journal of Mathematics and Applications · 2006
Abstract: We call a subset J of vertices of a digraph D as a (k, k−1) kernel of D, for a fixed k ≥ 2, if all distances between vertices from J are at least k and the distance from each vertex not belonging to J to the set J is at most k − 1. Some theorems concerning the existence of (k, k − 1) kernels are proved. The results generalize the well known Richardson theorem [9], which says: A digraph without odd circuits has a kernel.