On claw-freeM-oriented critical kernel-imperfect digraphs
✍ Scribed by Galeana-S�nchez, H.
- Publisher
- John Wiley and Sons
- Year
- 1996
- Tongue
- English
- Weight
- 382 KB
- Volume
- 21
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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 digraph such that every odd directed cycle has at least t w o chords then D has a kernel. Here w e obtain some properties of claw-free M-oriented critical kernel-imperfect digraphs. As a consequence w e show that if D is an M-oriented Kl,3-free digraph such that every odd directed cycle of length at least five has t w o diagonals then D has a kernel.