@article {
author = {Blidia, Mostafa and Chellali, Mustapha},
title = {A note on the small quasi-kernels conjecture in digraphs},
journal = {Communications in Combinatorics and Optimization},
volume = {9},
number = {4},
pages = {799-803},
year = {2024},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2023.28155.1459},
abstract = {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.$},
keywords = {Digraphs,kernel,quasi-kernel},
url = {https://comb-opt.azaruniv.ac.ir/article_14608.html},
eprint = {https://comb-opt.azaruniv.ac.ir/article_14608_5b513a0043acd2a9b12a25a1c1def2cb.pdf}
}