2024/09/08 by Nguyen, Tung, Scott, Alex, Seymour, Paul · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.05039
A \em 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).