(A, ℬ)-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 -- (k, l)-kernel -- H-colored digraph -- H-kernel
• DOI: 10.1016/j.akcej.2019.03.002
• Languages: English
• ISSNs: 0972-8600

Abstract

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.