𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Sur les quasi-noyaux d'un graphe

✍ Scribed by Pierre Duchet; Yahya Ould Hamidoune; Henry Meyniel

Publisher
Elsevier Science
Year
1987
Tongue
English
Weight
237 KB
Volume
65
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We define three classes of quasi-kernels for a directed graph. As a consequence, we show the existence of quasi-kernels in every progressively finite graph and in every locally finite graph, generalizing the result of Chv~ital and Lov~tsz which deals with the finite case. Our method shows that the problem of finding a quasi-kernel in a finite digraph and the problem of finding the unique kernel of an acircuitic finite digraph have the same algorithmic complexity.

📜 SIMILAR VOLUMES

Sur les atomes d'un graphe de Cayley inf
Sur les atomes d'un graphe de Cayley infini
✍ Yahya Ould Hamidoune 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 351 KB

## Let G be an infinite group and let S be a finite subset of G. The outconnectivity of the Cayley graph X=Cay(G, S) is K+(X)=M~~{((FS~\F(:F is a finite nonvoid subset of G). A positive end is a finite subset R such that K+(X) = ((RS)\ RI, which is minimal with respect to this property. We prove t

Sur la contractibilité d'un graphe orien
Sur la contractibilité d'un graphe orienté en K∗4
✍ Pierre Duchet; Viktor Kaneti 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 853 KB

We prove that every directed graph with n vertices and at least k-8 arcs admits the complete symmetric digraph of order 4 as a minor. The result is sharp. This answers a question raised by Meyniel (1983). We conclude with some open problems.