✦ LIBER ✦

About quasi-kernels in a digraph

✍ Scribed by H. Jacob; H. Meyniel

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 122 KB
Volume: 154
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)e0035-3

No coin nor oath required. For personal study only.

✦ Synopsis

We generalize a result by Maghout who had shown that every tournament of radius 2 admits three distinct centers. Here we prove that every graph without kernel has at least three distinct quasi-kernels.

📜 SIMILAR VOLUMES

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

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

Fractional Kernels in Digraphs

✍ Ron Aharoni; Ron Holzman 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 171 KB

We define a fractional version of the notion of ``kernels'' in digraphs and prove that every clique acyclic digraph (i.e., one in which no clique contains a cycle) has a fractional kernel. Using this we give a short proof of a recent result of Boros and Gurvich (proving a conjecture of Berge and Duc

About the shortest chain between two ver

About the shortest chain between two vertices in a quasi strongly connected digraph with a potential

✍ Jean-Pierre Barthelemy 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 370 KB

A closed form solution is provided for the length, relatively between two vertices of a quasi strongly connected digraph. to a potential Cr, of a chain ## I. Detidtions and nobtion!!i Let G = (V, A) denote a finite connected digraph without loop; V is the set of vertices and A the set of arcs. A

Almost all digraphs have a kernel

✍ Ioan Tomescu 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 561 KB

About some cyclic properties in digraphs

✍ M.C Heydemann; D Sotteau 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 847 KB