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

Let D = (V(D), A(D)) a digraph. Consider the set PD= {P: P is a non trivial finite directed path in D} and let A and ℬ two subsets of PD. 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 uv-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 xy-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∈PD: 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 PDsuch that (A, ℬ)P. Suppose that (1) {V1, V2} is a partition of A such that Viis Vi-transitive for each i in {1, 2}, (2) for i in {1, 2}, if (xn)n∈Nis a Vi-infinite outward path, then there exists j in N such that there exists a directed path from xj+1to xjin Vi. Then D has an (A, ℬ)-kernel. Generalizations of many previous results are obtained as a direct consequence of this theorem. Keywords: Kernel, Kernel by monochromatic paths, (k, l)-kernel, H-colored digraph, H-kernel

Abstract licence: CC BY-NC

15 more references, whose wording the paper’s licence keeps private.

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.