(A, ℬ)-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 D = ( V ( D ), A ( D )) a digraph. Consider the set P D = P : P is a non trivial finite directed path in D and let A and ℬ two subsets of P D . A subset N of V ( D ) is said to be an ( A, ℬ )-kernel of D if (1) for every subset u, v of N there exists no u v -directed path P such that P ∈ A ( N is A -independent) and (2) for every vertex x in V ( D ) ∖ N there exist y in N and P in ℬ such that P is an x y -directed path ( N is ℬ -absorbent). In particular, this is a generalization of the concept kernel by monochromatic directed paths in an m -colored digraph when A = ℬ = P ∈ P D : P is a monochromatic directed path. A classical result in kernel theory establishes that if D is a 2-colored digraph without monochromatic infinite outward paths, then D 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 ( A, ℬ )-kernels, for possibly infinite digraphs, as follows: Let D be a digraph, possible infinite, and A and ℬ two subsets of P D such that ( A, ℬ ) P . Suppose that (1) V 1, V 2 is a partition of A such that V i is V i -transitive for each i in 1, 2, (2) for i in 1, 2, if ( x n ) n ∈ N is a V i -infinite outward path, then there exists j in N such that there exists a directed path from x j + 1 to x j in V i . Then D has an ( A, ℬ )-kernel. Generalizations of many previous results are obtained as a direct consequence of this theorem.