New sufficient conditions for the existence of kernels in digraphs
2005
Abstract A kernel N of a digraph D is an independent set of vertices of D such that for every w ∈ V ( D ) − N there exists an arc from w to N . If every induced subdigraph of D has a kernel, D is said to be a kernel perfect digraph. Minimal non-kernel perfect digraph are called critical kernel imperfect digraph. If F is a set of arcs of D , a semikernel modulo F , S of D is an independent set of vertices of D such that for every z ∈ V ( D ) − S for which there exists an S z − arc of D − F , there also exists an z S − arc in D . In this work new sufficient conditions for a digraph to be a critical kernel imperfect digraph, in terms of semikernel modulo F , are presented.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
4
References
0
Citations
NaN
KQI