✦ LIBER ✦

Fractional Kernels in Digraphs

✍ Scribed by Ron Aharoni; Ron Holzman

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 171 KB
Volume: 73
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1731

No coin nor oath required. For personal study only.

✦ Synopsis

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 Duchet) that every clique acyclic orientation of a perfect graph has a kernel.

📜 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

On claw-freeM-oriented critical kernel-i

On claw-freeM-oriented critical kernel-imperfect digraphs

✍ Galeana-S�nchez, H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB

A kernel of a digraph D is an independent and dominating set of vertices of D. A chord of a directed cycle C = (0, 1 , . . . , n, 0) is an arc of D not in C with both terminal vertices in C . A diagonal of C is a chord with j # i -1. Meyniel made the conjecture (now know to be false) that if D is a

A sufficient condition for a digraph to

A sufficient condition for a digraph to be kernel-perfect

✍ P. Duchet 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 205 KB

Extraction and fractionation of proteins

Extraction and fractionation of proteins of sorghum kernels

✍ Madhuri Haikerwal; A. R. Mathieson 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 395 KB

Girth in digraphs

✍ J. C. Bermond; A. Germa; M. C. Heydemann; D. Sotteau 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 211 KB

## Abstract For an integer __k__ > 2, the best function __m__(__n, k__) is determined such that every strong digraph of order __n__ with at least __m__(__n, k__) arcs contains a circuit of length __k__ or less.