About this Computer Science article
On Kernels and Semikernels of Digraphs by H Galeana-Sánchez; V Neumann-Lara is a Computer Science article available to read on EtoBox.
A kernel N of a digraph D is an independent set of vertices of D such that for every w ~ V(D)-N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be an R-digraph. Minimal non-R-digraphs are called R--digraphs. In this paper some structural results concerning R--digraphs and sufficient conditions for a digraph to be an R-digraph are presented. In particular, it is proved that every vertex (resp. arc) in an R--digraph is contained in an odd directed cycle not containing special pseudodiagonals. It is also proved that any digraph in which every odd directed cycle has two pseudodiagonals with consecutive terminal endpoints is an R-digraph. Previous results of other authors (Richardson, Meyniel, Duchet, and others) are generalized.
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- H Galeana-Sánchez; V Neumann-Lara
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0012-365X)
- Published
- 1984
- Language
- EN
- Field
- Computer Science (Physical Sciences)