A kernel of a digraph D is a subset N ⊆ V(D) which is both independent and absorbing. When every induced subdigraph of D has a kernel, the digraph D is said to be kernel-perfect. We say that D is a critical kernel-imperfect digraph if D does not have a kernel but every proper induced subdigraph of D does have at least one. Although many classes of critical kernel-imperfect-digraphs have been constructed, all of them are digraphs such that the block-cutpoint tree of its asymmetrical part is a path. The aim of the paper is to construct critical kernel-imperfect digraphs of a special structure, a general method is developed which permits to build critical kernel-imperfect-digraphs whose asymmetrical part has a prescribed block-cutpoint tree. Specially, any directed cactus (an asymmetrical digraph all of whose blocks are directed cycles) whose blocks are directed cycles of length at least 5 is the asymmetrical part of some critical kernel-imperfect-digraph.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1065,
author = {Hortensia Galeana-S\'anchez and V. Neumann-Lara},
title = {New classes of critical kernel-imperfect digraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {18},
year = {1998},
pages = {85-89},
zbl = {0913.05047},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1065}
}
Hortensia Galeana-Sánchez; V. Neumann-Lara. New classes of critical kernel-imperfect digraphs. Discussiones Mathematicae Graph Theory, Tome 18 (1998) pp. 85-89. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1065/
[000] [1] C. Berge, Graphs (North-Holland, Amsterdam, 1985).
[001] [2] M. Blidia, P. Duchet, F. Maffray, On orientations of perfect graphs, in preparation. | Zbl 0780.05020
[002] [3] P. Duchet, Graphes Noyau-Parfaits, Annals Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4.
[003] [4] H. Galeana-Sánchez, A new method to extend kernel-perfect graphs to kernel-perfect critical graphs, Discrete Math. 69 (1988) 207-209, doi: 10.1016/0012-365X(88)90022-2. | Zbl 0675.05033
[004] [5] H. Galeana-Sánchez and V. Neumann-Lara, On kernel-perfect critical digraphs, Dicrete Math. 59 (1986) 257-265, doi: 10.1016/0012-365X(86)90172-X. | Zbl 0593.05034
[005] [6] 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
[006] [7] H. Galeana-Sánchez and V. Neumann-Lara, New extensions of kernel-perfect digraphs to critical kernel-imperfect digraphs, Graphs & Combinatorics 10 (1994) 329-336, doi: 10.1007/BF02986683. | Zbl 0811.05027
[007] [8] F. Harary, Graph Theory (Addison-Wesley Publishing Company, New York, 1969).