(, )-kernels and Sands, Sauer and Woodrow’s theorem

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.

Keywords

• kernel
• kernel by monochromatic paths
• (, )-kernel
• -colored digraph
• -kernel