(, )-kernels and Sands, Sauer and Woodrow's theorem. Issue 3 (1st December 2019) - Galeana-Sánchez, Hortensia; Rojas-Monroy, Rocío; Sánchez-López, Rocío
Abstract: Let = ( ( ), ( )) a digraph. Consider the set = { : is a non trivial finite directed path in } and let and two subsets of . A subset of ( ) is said to be an (, )-kernel of if (1) for every subset {, } of there exists no -directed path such that ( is -independent) and (2) for every vertex in ( ) there exist in and in such that is an -directed path ( is -absorbent). In particular, this is a generalization of the concept kernel by monochromatic directed paths in an -colored digraph when = { : is a monochromatic directed path}. A classical result in kernel theory establishes that if is a 2-colored digraph without monochromatic infinite outward paths, then has a kernel by monochromatic directed paths; this result is known as Sands, Sauer and Woodrow's theorem. In this paper we show an extension of this result in the context of (, )-kernels, for possibly infinite digraphs, as follows: Let be a digraph, possible infinite, and and two subsets of such that (, ) . Suppose that (1) {, } is a partition of such that is -transitive for each in {1, 2}, (2) for in {1, 2}, if ( ) is a -infinite outward path, then there exists in such that there exists a directed path from to in . Then has an (, )-kernel. Generalizations of many previous results are obtained as a direct consequence of this theorem.