Please use this identifier to cite or link to this item:
|Title:||On the Number of Quasi-Kernels in Digraphs|
|Citation:||Gutin, G., Koh, K.M., Tay, E.G., Yeo, A. (2004-05). On the Number of Quasi-Kernels in Digraphs. Journal of Graph Theory 46 (1) : 48-56. ScholarBank@NUS Repository. https://doi.org/10.1002/jgt.10169|
|Abstract:||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 v x ∈ 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. © 2004 Wiley Periodicals, Inc.|
|Source Title:||Journal of Graph Theory|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Aug 16, 2018
WEB OF SCIENCETM
checked on Jul 31, 2018
checked on Jul 27, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.