Kernels in quasi-transitive digraphs

AbstractLet 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∈V(D)-N there exists an arc from w to N. A digraph is called quasi-transitive when (u,v)∈A(D) and (v,w)∈A(D) implies (u,w)∈A(D) or (w,u)∈A(D). This concept was introduced by Ghouilá–Houri [Caractérisation des graphes non orientés dont on peut orienter les arrêtes de maniere à 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=D1∪D2 where Di is a quasi-transitive digraph which contains no asymmetrical infinite outward path (in Di) for i∈{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