Results on the Small Quasi-Kernel Conjecture
share
A quasi-kernel of a digraph D is an independent set Q⊆ V(D) such that for every vertex v∈ V(D)\ Q, there exists a directed path with one or two arcs from v to a vertex u∈ Q. In 1974, Chvátal and Lovász proved that every digraph has a quasi-kernel. In 1976, Erdős and Sźekely conjectured that every sink-free digraph D=(V(D),A(D)) has a quasi-kernel of size at most |V(D)|/2. In this paper, we give a new method to show that the conjecture holds for a generalization of anti-claw-free digraphs. For any sink-free one-way split digraph D of order n, when n≥ 3, we show a stronger result that D has a quasi-kernel of size at most n+3/2 - √(n), and the bound is sharp.
READ FULL TEXT