𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On kernels and semikernels of digraphs

✍ Scribed by H Galeana-Sánchez; V Neumann-Lara

Book ID
103059751
Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
445 KB
Volume
48
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

On kernel-perfect critical digraphs
On kernel-perfect critical digraphs
✍ H. Galeana-Sánchez; V. Neumann-Lara 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 528 KB

In this paper we investigate new sufficient conditions for a digraph to be kernel-perfect (KP) and some structural properties of kernel-perfect critical (KPC) digraphs. In particular, it is proved that the asymmetrical part of any KPC digraph is strongly connected. A new method to construct KPC digr

On the number of quasi-kernels in digrap
On the number of quasi-kernels in digraphs
✍ Gregory Gutin; Khee Meng Koh; Eng Guan Tay; Anders Yeo 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 89 KB

## Abstract A vertex set __X__ of a digraph __D__ = (__V, A__) is a __kernel__ if __X__ is independent (i.e., all pairs of distinct vertices of __X__ are non‐adjacent) and for every __v__ ∈ __V__‐__X__ there exists __x__ ∈ __X__ such that __vx__ ∈ __A__. A vertex set __X__ of a digraph __D__ = (__V

Disjoint quasi-kernels in digraphs
Disjoint quasi-kernels in digraphs
✍ Scott Heard; Jing Huang 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB

## Abstract A __quasi‐kernel__ in a digraph is an independent set of vertices such that any vertex in the digraph can reach some vertex in the set via a directed path of length at most two. Chvátal and Lovász proved that every digraph has a quasi‐kernel. Recently, Gutin et al. raised the question o