%0 Journal Article
%T A note on the small quasi-kernels conjecture in digraphs
%J Communications in Combinatorics and Optimization
%I Azarbaijan Shahid Madani University
%Z 2538-2128
%A Blidia, Mostafa
%A Chellali, Mustapha
%D 2024
%\ 12/01/2024
%V 9
%N 4
%P 799-803
%! A note on the small quasi-kernels conjecture in digraphs
%K Digraphs
%K kernel
%K quasi-kernel
%R 10.22049/cco.2023.28155.1459
%X 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 $\left\vert V(D)\right\vert /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 $\left\vert V(D)\right\vert /2.$
%U https://comb-opt.azaruniv.ac.ir/article_14608_5b513a0043acd2a9b12a25a1c1def2cb.pdf