Structural properties of CKI-digraphs

Abstract

A kernel of a digraph is a set of vertices which is both independent and absorbant. Let Dbe a digraph such that every proper induced subdigraph has a kernel. IfDhas a kernel, thenDis kernel perfect, otherwiseDis critical kernel-imperfect (for short CKI-digraph). In this work we prove that if a CKI-digraphDis not 2-arc connected, thenD−ais kernel perfect for any bridgeaofD. IfDhas no kernel but for all vertexx,D−xhas a kernel, thenDis called kernel critical. We give conditions on a kernel critical digraphDso that for allx∈V(D) the kernel ofD−xhas at least two vertices. Concerning asymmetric digraphs, we show that every vertexuof an asymmetric CKI-digraphDonn≥5 vertices satisfies d + (u) +d − (u)≤n−3 andd + (u), d − (u)≤n−5. As a consequence, we establish that there are exactly four asymmetric CKI-digraphs onn≤7 vertices. Furthermore, we study the maximum order of a subtournament contained in a not necessarily asymmetric CKI-digraph.