Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419221 | Discrete Applied Mathematics | 2016 | 11 Pages |
A kernel NN of a digraph DD is an independent set of vertices of DD such that for every w∈V(D)∖Nw∈V(D)∖N there exists an arc from ww to NN. The digraph DD is said to be a kernel-perfect digraph when every induced subdigraph of DD has a kernel. Minimal non kernel-perfect digraphs are called critical kernel-imperfect digraphs. The broader sufficient condition for the existence of kernels in digraphs known so far is that states: (1) If DD is a digraph such that every odd cycle has two consecutive poles, then DD is kernel-perfect.In this paper is studied the structure of critical kernel-imperfect digraphs which belong to a very large special classes of digraphs and many structural properties are obtained. As a consequence (1)(1) is widely generalized in this class of digraphs, where the condition of the poles is requested only for odd cycles whose edges alternate in a set of arcs. As consequence, some classic results of kernel-perfect and finite critical kernel-imperfect digraphs are generalized for these classes of digraphs.