TOPICS
Search

Semikernel


A semikernel of a directed graph is an independent vertex set S such that every graph vertex outside S reached by a directed edge from S has a directed edge back to some member of S (Neumann-Lara 1971, Galeana-Sánchez and Neumann-Lara 1984).

Chvátal and Lovász (1974) used the name "semi-kernel" for what is now called a quasi-kernel. In a consistently oriented cycle graph on three vertices, each singleton set is a quasi-kernel, while the empty set is the only semikernel.


See also

Directed Graph, Independent Vertex Set, Quasi-Kernel

Explore with Wolfram|Alpha

References

Chvátal, V. and Lovász, L. "Every Directed Graph Has a Semi-Kernel." In Hypergraph Seminar (Ed. C. Berge and D. Ray-Chaudhuri). Berlin, Germany: Springer, p. 175, 1974. https://doi.org/10.1007/BFb0066192.Galeana-Sánchez, H. and Neumann-Lara, V. "On Kernels and Semikernels of Digraphs." Discrete Math. 48, 67-76, 1984. https://doi.org/10.1016/0012-365X(84)90131-6.Neumann-Lara, V. "Seminúcleos de una Digráfica." An. Inst. Mat. Univ. Nac. Autónoma México 11, 55-62, 1971. https://www.matem.unam.mx/~ilan/2010/2/seminario/Seminucleos.pdf.

Cite this as:

Weisstein, Eric W. "Semikernel." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Semikernel.html

Subject classifications