Almost all digraphs have a kernel

DOI10.1016/0012-365X(90)90373-PMaRDI QIDQ915737zbMATH OpenOpenAlexFDO

Authors Ioan Tomescu

Publication date 1990

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(90)90373-p

zbMATH Keywords

digraphdirected graphkernel

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Review text

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\).

Recommendations

• scientific article; zbMATH DE number 4212085
• A parity digraph has a kernel
• Kernels in a special class of digraphs
• A sufficient condition for the existence of k-kernels in digraphs
• Kernels of digraphs with finitely many ends
• Kernels in circulant digraphs
• Kernels in digraphs that are not kernel perfect
• On the existence of (k,\(\ell)\)-kernels in digraphs
• Kernels in planar digraphs
• About quasi-kernels in a digraph

Cites work

• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• On cliques in graphs

Cited in

(6)

• Kernels in random graphs
• Kernels in planar digraphs
• scientific article; zbMATH DE number 4212085 (Why is no real title available?)
• A note on the kernel number
• scientific article; zbMATH DE number 1275896 (Why is no real title available?)
• Graph theoretical structures in logic programs and default theories

This page was built for publication: Almost all digraphs have a kernel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q915737)