Open AccessOn the Number of Quasi-Kernels in Digraphs
Author(s) -
Gregory Gutin,
Khee Meng Koh,
Eng Guan Tay,
Anders Yeo
Publication year - 2001
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v8i7.20461
Subject(s) - digraph , combinatorics , mathematics , conjecture , disjoint sets , vertex (graph theory) , kernel (algebra) , discrete mathematics , graph
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 in V − X there exists x in X such that vx in A. A vertex set X of a digraph D = (V,A) is a quasi-kernel if X is independent and for every v in V − X there exist w in V − X, x in X such that either vx in A or vw,wx in A: In 1994, Chvatal and Lovasz 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. We conjecture that every digraph with no sink has a pair of disjoint quasi-kernels and provide some support to this conjecture.