کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419221 | 683753 | 2016 | 11 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 235–245