Article ID Journal Published Year Pages File Type
8902780 AKCE International Journal of Graphs and Combinatorics 2017 7 Pages PDF
Abstract
Let D be a digraph, possibly infinite, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. A subset K of V(D) is said to be a kernel if it is both independent (a vertex in K has no successor in K) and absorbing (a vertex not in K has a successor in K). An infinite digraph D is said to be a finitely critical kernel imperfect digraph if D contains no kernel but every finite induced subdigraph of D contains a kernel. In this paper we will characterize the infinite kernel perfect digraphs by means of finitely critical imperfect digraphs and strong components of its asymmetric part and then, by using some previous theorems for infinite digraphs, we will deduce several results from the main result. Richardson's theorem establishes that if D is a finite digraph without cycles of odd length, then D has a kernel. In this paper we will show a generalization of this theorem for infinite digraphs.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,