Kernels in pretransitive digraphs

Abstract

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. A kernel N of D is an independent set of vertices such that for every w is an element of V(D) - N there exists an are from w to N. A digraph D is called right-pretransitive (resp. left-pretransitive) when (u, v) is an element of A(D) and (v, w) is an element of A(D) implies (u, w) is an element of A(D) or (w, v) is an element of A(D) (resp. (u, v) is an element of A(D) and (v, w) is an element of A(D) implies (u, w) is an element of A(D) or (v, u) is an element of A(D)). This concepts were introduced by P. Duchet in 1980. In this paper is proved the following result: Let D be a digraph. If D = D-1 boolean OR D-2 where D-1 is a right-pretransitive digraph, D-2 is a left-pretransitive digraph and D-i contains no infinite outward path for i is an element of {1, 2}, then D has a kernel. (C) 2003 Elsevier B.V. All rights reserved.