Extensions of Richardson’s theorem for infinite digraphs and (𝒜, ℬ)-kernels

Abstract

Let D be a digraph and and two subsets of where = {P: P is a non trivial finite path in D}. A subset N of V(D) is said to be an ()-kernel of D if: (1) for every {u,v} N there exists no uv-path P such that P (N is -independent), (2) for every vertex x in V(D) there exist y in N and P in such that P is an xy-path (N is -absorbent). As a particular case, the concept of ()-kernel generalizes the concept of kernel when = = A(D). A classical result in kernel theory is Richardson’s theorem which establishes that if D is a finite digraph without odd cycles, then D has a kernel. In this paper, the original results are sufficient conditions for the existence of ()-kernels in possibly infinite digraphs, in particular we will present some generalizations of Richardson’s theorem for infinite digraphs. Also we will deduce some conditions for the existence of kernels by monochromatic paths, H-kernels and (k,l)-kernels in possibly infinite digraphs.

Keywords

• kernel
• kernel by monochromatic paths
• h-kernel
• -kernel
• ()-kernel