CKI-Digraphs, Generalized Sums and Partitions of Digraphs

摘要

A kernel of a digraph is a set of vertices which is both independent and absorbent. Let be a digraph such that every proper induced subdigraph of has a kernel; is said to be kernel perfect digraph (KP-digraph) if the digraph has a kernel and critical kernel imperfect digraph (CKI-digraph) if the digraph does not have a kernel. We characterize the CKI-digraphs with a partition into an independent set and a semicomplete digraph. The generalized sum of a family of mutually disjoint digraphs over a graph is a digraph defined as follows: Consider , and for each and with choose exactly one of the two arcs or . We characterize the asymmetric CKI-digraphs which are generalized sums over an edge or a cycle. Furthermore, we give sufficient conditions on and the family , such that the generalized sum has a kernel or is a is KP-digraph.