On the Number of Quasi-Kernels in Digraphs

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.