Almost all digraphs have a kernel (Q915737)

A kernel of a directed graph \(D_ n\) is a subset X of independent vertices such that for every vertex u not in X there is at least one edge joining u to some vertex v in X. The author shows that almost all directed graphs \(D_ n\) have the following properties: (a) the number of kernels of \(D_ n\) lies between \(n^{.931+o(1)}\) and \(n^{1+o(1)}\); (b) the size of every kernel of \(D_ n\) lies in a certain interval of length 3.54 containing \(\log n-\log \log n\).