# KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition

H. Galeana-Sánchez; V. Neumann-Lara

Discussiones Mathematicae Graph Theory (1996)

- Volume: 16, Issue: 1, page 5-16
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topH. Galeana-Sánchez, and V. Neumann-Lara. "KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition." Discussiones Mathematicae Graph Theory 16.1 (1996): 5-16. <http://eudml.org/doc/270225>.

@article{H1996,

abstract = {
A digraph D is said to satisfy the k-Meyniel's condition if each odd directed cycle of D has at least k diagonals.
The study of the k-Meyniel's condition has been a source of many interesting problems, questions and results in the development of Kernel Theory.
In this paper we present a method to construct a large variety of kernel-perfect (resp. critical kernel-imperfect) digraphs which satisfy the k-Meyniel's condition.
},

author = {H. Galeana-Sánchez, V. Neumann-Lara},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {digraph; kernel; independent set of vertices; absorbing set of vertices; kernel-perfect digraph; critical-kernel-imperfect digraph; τ-system; τ₁-system; indepedent kernel modulo Q; co-rooted tree; τ-construction; τ₁-construction; independent set; absorbing set; independent kernel; kernel-perfect; critical kernel-imperfect},

language = {eng},

number = {1},

pages = {5-16},

title = {KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition},

url = {http://eudml.org/doc/270225},

volume = {16},

year = {1996},

}

TY - JOUR

AU - H. Galeana-Sánchez

AU - V. Neumann-Lara

TI - KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition

JO - Discussiones Mathematicae Graph Theory

PY - 1996

VL - 16

IS - 1

SP - 5

EP - 16

AB -
A digraph D is said to satisfy the k-Meyniel's condition if each odd directed cycle of D has at least k diagonals.
The study of the k-Meyniel's condition has been a source of many interesting problems, questions and results in the development of Kernel Theory.
In this paper we present a method to construct a large variety of kernel-perfect (resp. critical kernel-imperfect) digraphs which satisfy the k-Meyniel's condition.

LA - eng

KW - digraph; kernel; independent set of vertices; absorbing set of vertices; kernel-perfect digraph; critical-kernel-imperfect digraph; τ-system; τ₁-system; indepedent kernel modulo Q; co-rooted tree; τ-construction; τ₁-construction; independent set; absorbing set; independent kernel; kernel-perfect; critical kernel-imperfect

UR - http://eudml.org/doc/270225

ER -

## References

top- [1] C. Berge, Graphs (North-Holland, Amsterdam, 1985).
- [2] P. Duchet and H. Meyniel, A note on kernel-critical digraphs, Discrete Math. 33 (1981) 103-105, doi: 10.1016/0012-365X(81)90264-8. Zbl0456.05032
- [3] P. Duchet and H. Meyniel, Une generalization du theoreme de Richarson sur l'existence de noyoux dans les graphes orientes, Discrete Math. 43 (1983) 21-27, doi: 10.1016/0012-365X(83)90017-1. Zbl0502.05027
- [4] P. Duchet, A suffiecient condition for a digraph to be kernel-perfect, J. Graph Theory 11 (1987) 81-81, doi: 10.1002/jgt.3190110112. Zbl0607.05036
- [5] H. Galeana-Sánchez and V. Neumann-Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984) 67-76, doi: 10.1016/0012-365X(84)90131-6. Zbl0529.05024
- [6] H. Galeana-Sánchez and V. Neumann-Lara, On kernel-perfect critical digraphs, Discrete Math. 59 (1986) 257-265, doi: 10.1016/0012-365X(86)90172-X. Zbl0593.05034
- [7] H. Galeana-Sánchez and V. Neumann-Lara, Extending kernel perfect digraphs to kernel perfect critical digraphs, Discrete Math. 94 (1991) 181-187, doi: 10.1016/0012-365X(91)90023-U. Zbl0748.05060
- [8] H. Jacob, Etude Theorique du Noyau d'un graphe, These, Universite Pierre et Marie Curie, Paris VI, 1979.
- [9] V. Neumann-Lara, Seminúcleos de una digráfica, Anales del Instituto de Matemáticas 11 (1971) UNAM.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.