a note on the small quasi-kernels conjecture in digraphs

A subset $k$ of vertices of digraph $d=(v(d),a(d))$ is a kernel if the following two conditions are fulfilled: (i) no two vertices of $k$ are connected by an arc in any direction and (ii) every vertex not in $k$ has an ingoing arc from some vertex in $k.$ a quasi-kernel of $d$ is a subset $q$ of vertices satisfying condition (i) and furthermore every vertex can be reached in at most two steps from $q.$ a vertex is source-free if it has at least one ingoing arc. in 1976, p.l. erdös and l.a. székely conjectured that every source-free digraph $d$ has a quasi-kernel of size at most $leftvert v(d)rightvert /2.$ recently, this conjecture has been shown to be true by allan van hulst for digraphs having kernels. in this note, we provide a short and simple proof of van hulst’s result. we additionally characterize all source-free digraphs $d$ having kernels with smallest quasi-kernels of size $leftvert v(d)rightvert /2.$