(, )-kernels and Sands, Sauer and Woodrow's theorem. Issue 3 (1st December 2019)

• Record Type: Journal Article
• Authors: Galeana-Sánchez, Hortensia; Rojas-Monroy, Rocío; Sánchez-López, Rocío
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 16:Issue 3(2019)
• Page Start: 284
• Page End: 290
• Publication Date: 2019-12-01
• Subjects: Kernel -- Kernel by monochromatic paths -- (, )-kernel -- -colored digraph -- -kernel
• DOI: 10.1016/j.akcej.2019.03.002
• Languages: English
• ISSNs: 0972-8600

Abstract

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.