Kernels in a special class of digraphs Original Research Article

A kernel N of a digraph D is an independent set of vertices of D such that for every w ∈ V(D)⧹N there exists an arc from w to N. A digraph D is complete if for every two vertices u, v ∈ V(D) at least one of (u, v) ∈ A(D) or (v, u) ∈ A(D) holds. The covering number of a digraph D, denoted by θ(D) is the minimum number of complete subdigraphs of D that partition V(D). Let D be a digraph with θ(D) ⩽ 3 such that every directed triangle is symmetrical. In this paper we prove the following two results: 1. (1) If every directed cycle of length 5 has three symmetrical arcs, then D has a kernel. 2. (2) If every directed cycle of length 5 has two diagonals, then D has a kernel.