A note on the small quasi-kernels conjecture in digraphs

Document Type : Short notes

Authors

LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

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 |V(D)|/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 |V(D)|/2.

Keywords

Main Subjects

References

[1] J. Bang-Jensen and G.Z. Gutin, Digraphs: Theory, Algorithms and Applications, Springer Science & Business Media, 2008.
[2] A. Kostochka, R. Luo, and S. Shan, Towards the small quasi-kernel conjecture, Electron. J. Combin. 29 (2022), no. 3, ID: #P3.49.  https://doi.org/10.37236/11043
[3] A. van Hulst, Kernels and small quasi-kernels in digraphs, arXiv preprint arXiv:2110.00789 (2021).
Communications in Combinatorics and Optimization
Volume 9, Issue 4
December 2024
Pages 799-803

Files

Share

How to cite

Statistics