𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the existence of kernels and h-kernels in directed graphs

✍ Scribed by H. Galeana-Sánchez

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
272 KB
Volume
110
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Kernels in directed graphs: a poison gam
Kernels in directed graphs: a poison game
✍ P. Duchet; H. Meyniel 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 282 KB

We consider a two player game on a progressively and locally finite directed graph and we prove that the first player wins if and only if the graph has a local kernel. The result is sharp. From it, we derive a short proof of a general version of the Galeana-Sanchez & Neuman-Lara Theorem that give a

Recent problems and results about kernel
Recent problems and results about kernels in directed graphs
✍ C. Berge; P. Duchet 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 355 KB

In Section 1, we survey the existence theorems for a kernel; in Section 2, we discuss a new conjecture which could constitute a bridge between the kernel problems and the perfect graph conjecture. In fact, we believe that a graph is 'quasi-perfect' if and only if it is perfect. ## Proposition 1.1.

On the existence of (k, l)-kernels in di
On the existence of (k, l)-kernels in digraphs
✍ Hortensia Galeana-Sánchez 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 264 KB

In this paper we present some results on the existence of /c-kernels and (k, [)-kernels in digraphs which generalize the following Theorem of P. Duchet [2]: "If every directed cycle of odd length in a digraph D has at least two symmetrical arcs, then D has a kernel.

On a class of kernel-perfect and kernel-
On a class of kernel-perfect and kernel-perfect-critical graphs
✍ Kiran B. Chilakamarri; Peter Hamburger 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 275 KB

Chilakamarri, K.B. and P. Hamburger, On a class of kernel-perfect and kernel-perfect-critical graphs, Discrete Mathematics 118 (1993) 253-257. In this note we present a construction of a class of graphs in which each of the graphs is either kernel-perfect or kernel-perfect-critical. These graphs or