Distant digraph domination

Journal article

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).

Authors: Nguyen, T; Scott, A; Seymour, P

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Electronic Journal of Combinatorics
• Journal: Electronic Journal of Combinatorics
• Volume: 33
• Issue: 1
• Article number: P1.32
• Publication date: 2026-02-13
• Acceptance date: 2025-11-10
• DOI: 10.37236/13556
• EISSN: 1077-8926
• Language: English