On the Number of Quasi-Kernels in Digraphs

  • Gregory Gutin
  • Khee Meng Koh
  • Eng Guan Tay
  • Anders Yeo

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 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.

Published
2001-01-07
How to Cite
Gutin, G., Koh, K., Tay, E., & Yeo, A. (2001). On the Number of Quasi-Kernels in Digraphs. BRICS Report Series, 8(7). https://doi.org/10.7146/brics.v8i7.20461