Extensions of Richardson’s theorem for infinite digraphs and (𝒜, ℬ)-kernels
Hortensia Galeana‐Sánchez, Rocı́o Rojas-Monroy, Rocío Sánchez-López · AKCE International Journal of Graphs and Combinatorics · 2020
Let D be a digraph and A and B two subsets of PD, where PD = {P: P is a non trivial finite path in D}. A subset N of V(D) is said to be an (A,B)-kernel of D if: (1) for every {u,v} ⊆ N there exists no uv-path P such that P ∈A (N is A-independent), (2) for every vertex x in V(D)∖N there exist y in N and P in B such that P is an xy-path (N is B-absorbent). As a particular case, the concept of (A,B)-kernel generalizes the concept of kernel when A = B = 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 (A,B)-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.