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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1019,
author = {H. Galeana-S\'anchez and V. Neumann-Lara},
title = {KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition},
journal = {Discussiones Mathematicae Graph Theory},
volume = {16},
year = {1996},
pages = {5-16},
zbl = {0865.05046},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1019}
}
H. Galeana-Sánchez; V. Neumann-Lara. KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition. Discussiones Mathematicae Graph Theory, Tome 16 (1996) pp. 5-16. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1019/
[000] [1] C. Berge, Graphs (North-Holland, Amsterdam, 1985).
[001] [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. | Zbl 0456.05032
[002] [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. | Zbl 0502.05027
[003] [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. | Zbl 0607.05036
[004] [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. | Zbl 0529.05024
[005] [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. | Zbl 0593.05034
[006] [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. | Zbl 0748.05060
[007] [8] H. Jacob, Etude Theorique du Noyau d'un graphe, These, Universite Pierre et Marie Curie, Paris VI, 1979.
[008] [9] V. Neumann-Lara, Seminúcleos de una digráfica, Anales del Instituto de Matemáticas 11 (1971) UNAM.