Please use this identifier to cite or link to this item: https://doi.org/10.1002/jgt.10169
Title: On the Number of Quasi-Kernels in Digraphs
Authors: Gutin, G.
Koh, K.M. 
Tay, E.G.
Yeo, A.
Keywords: Digraphs
Kernels
Quasi-kernels
Semi-kernels
Issue Date: May-2004
Source: 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
URI: http://scholarbank.nus.edu.sg/handle/10635/103819
ISSN: 03649024
DOI: 10.1002/jgt.10169
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

6
checked on Feb 21, 2018

WEB OF SCIENCETM
Citations

7
checked on Jan 15, 2018

Page view(s)

17
checked on Feb 18, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.