TY - JOUR
ID - 14608
TI - A note on the small quasi-kernels conjecture in digraphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Blidia, Mostafa
AU - Chellali, Mustapha
AD - LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
Y1 - 2024
PY - 2024
VL - 9
IS - 4
SP - 799
EP - 803
KW - Digraphs
KW - kernel
KW - quasi-kernel
DO - 10.22049/cco.2023.28155.1459
N2 - 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.$
UR - https://comb-opt.azaruniv.ac.ir/article_14608.html
L1 - https://comb-opt.azaruniv.ac.ir/article_14608_5b513a0043acd2a9b12a25a1c1def2cb.pdf
ER -