Kernels in infinite digraphs
Rocı́o Rojas-Monroy, Juana Imelda Villarreal-Valdés, Xueliang Li · 2010
Let D be a digraph, possibly infinite, V (D )a ndA(D) denote the sets of vertices and arcs of D, respectively. Ak ernelN of D is an independent set of vertices such that for every w ∈ V (D) − N there exists an arc from w to N .A setS ⊆ V (D )i s as emikernel ofD if it is independent and (u,v) ∈ A(D )w ithu ∈ S implies that there is an arc from v to some vertex in S. In this paper we introduce sufficient conditions for the existence of kernels in some kinds of infinite digraphs, such as transitive digraphs, symmetric digraphs, acyclic digraphs and digraphs without odd cycles. We use strongly the concept of semikernel.