کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648594 | 1342418 | 2009 | 14 صفحه 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. If every induced subdigraph of DD has a kernel, DD is said to be a kernel perfect digraph. DD is called a critical kernel imperfect digraph when DD has no kernel but every proper induced subdigraph of DD has a kernel. If FF is a set of arcs of DD, a semikernel modulo FF of DD is an independent set of vertices SS of DD such that for every z∈V(D)−Sz∈V(D)−S for which there exists an (S,z)(S,z)-arc of D−FD−F, there also exists an (z,S)(z,S)-arc in DD. In this work we show sufficient conditions for an infinite digraph to be a kernel perfect digraph, in terms of semikernel modulo FF. As a consequence it is proved that symmetric infinite digraphs and bipartite infinite digraphs are kernel perfect digraphs. Also we give sufficient conditions for the following classes of infinite digraphs to be kernel perfect digraphs: transitive digraphs, quasi-transitive digraphs, right (or left)-pretransitive digraphs, the union of two right (or left)-pretransitive digraphs, the union of a right-pretransitive digraph with a left-pretransitive digraph, the union of two transitive digraphs, locally semicomplete digraphs and outward locally finite digraphs.
Journal: Discrete Mathematics - Volume 309, Issue 11, 6 June 2009, Pages 3680–3693