On the Number of Quasi-Kernels in Digraphs Gregory Gutin Khee Meng Koh Eng Guan Tay Anders Yeo January 2001

### Abstract:

A vertex set of a digraph is a kernel if is independent (i.e., all pairs of distinct vertices of are non-adjacent) and for every there exists such that . A vertex set of a digraph is a quasi-kernel if is independent and for every there exist such that either or In 1994, Chvátal and Lovász proved that every digraph has a quasi-kernel. In 1996, Jacob and Meyniel proved that, if a digraph has no kernel, then 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

Available as PostScript, PDF, DVI.