Gutin, Gregory, Koh, K.M., Tay, E.G. and Yeo, Anders (2004) On the number of quasi-kernels in digraphs. Journal of Graph Theory, 46 (1).
Full text access: Open
A vertex set X of a digraph D = (V, A) is a kernel if X is independent (i.e., all pairs of distinct vertices of X are non-adjacent) and for every v V-X there exists x X such that vx A. A vertex set X of a digraph D = (V, A), is a quasi-kernel if X is independent and for every v V-X there exist w V-X, x X such that either vx A or vw, wx A. In 1974, Chvátal and Lovász proved that every digraph has a quasi-kernel. In 1996, Jacob and Meyniel proved that if a digraph D has no kernel, then D contains at least three quasi-kernels. We characterize digraphs with exactly one and two quasi-kernels, and, thus, provide necessary and sufficient conditions for a digraph to have at least three quasi-kernels. In particular, we prove that every strong digraph of order at least three, which is not a 4-cycle, has at least three quasi-kernels.
This is a Submitted version This version's date is: 2004 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/97e9c1f5-3209-d0a4-9ff3-7322a2d00a9c/4/
Deposited by Research Information System (atira) on 25-Jul-2012 in Royal Holloway Research Online.Last modified on 25-Jul-2012