On the Number of Quasi-Kernels in Digraphs

Gregory Gutin
Khee Meng Koh
Eng Guan Tay
Anders Yeo

January 2001

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

Last modified: 2003-06-08 by webmaster.