Distant digraph domination

A k-kernel in a digraph G is a stable set X of vertices such that every vertex of G can be joined from X by a directed path of length at most k. We prove three results about k-kernels. First, it was conjectured by Erdős and Székely in 1976 that every digraph G with no source has a 2-kernel |K| with |K| ⩽ |G|/2. We prove this conjecture when G is a “split digraph” (that is, its vertex set can be partitioned into a tournament and a stable set), improving a result of Langlois et al., who proved that every split digraph G with no source has a 2-kernel of size at most 2|G|/3. Second, the Erdős-Székely conjecture implies that in every digraph G there is a 2-kernel K such that the union of K and its out-neighbours has size at least |G|/2. we prove that this is true if V (G) can be partitioned into a tournament and an acyclic set. Third, in a recent paper, Spiro asked whether, for all k ⩾ 3, every strongly-connected digraph G has a k-kernel of size at most about |G|/(k + 1). This remains open, but we prove that there is one of size at most about |G|/(k − 1).