Kernels in quasi-transitive 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 arc from w to N. A digraph is called quasi-transitive when (u, v) is an element of A (D) and (v, w) is an element of A (D) implies (u, v) is an element of A (D) or (w, w) is an element of A (D). This concept was introduced by Ghouila-Houri [Caracterisation des graphes non orientes dont on peut orienter les arretes de maniere a obtenir le graphe d' un relation d'ordre, C.R. Acad. Sci. Paris 254 (1962) 1370-1371] and has been studied by several authors. In this paper the following result is proved: Let D be a digraph. Suppose D = D-1 boolean OR D-2 where D-i is a quasi-transitive digraph which contains no asymmetrical infinite outward path (in D-i) for i is an element of {1, 2}

and that every directed cycle of length 3 contained in D has at least two symmetrical arcs, then D has a kernel. All the conditions for the theorem are tight. (c) 2006 Elsevier B.V. All rights reserved.