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 $\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

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.
[3] A. van Hulst, Kernels and small quasi-kernels in digraphs, arXiv preprint arXiv:2110.00789 (2021).
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 05 August 2023

Files

Share

How to cite

Statistics