On kernel-perfect critical digraphs (Q1076036): Difference between revisions

Let G be a digraph. An independent set N of vertices of G is called a kernel if for every vertex z of G, \(z\not\in N\), there exists a vertex \(v\in N\) such that (z,v) is an edge of G. A digraph is said to be kernel- perfect (KP) if each of its proper induced subdigraphs has a kernel. A KP digraph which has no kernel is called KP-critical. In the paper some properties of KP-critical digraphs are studied and a construction of such digraphs is given. In a addition, the sufficient conditions for a digraph to be KP are investigated.