DMGT

Discussiones Mathematicae Graph Theory 18(1) (1998) 85-89
DOI: https://doi.org/10.7151/dmgt.1065

NEW CLASSES OF CRITICAL KERNEL-IMPERFECT DIGRAPHS

Hortensia Galeana-Sánchez and V. Neumann-Lara

Instituto de Matemáticas, UNAM
Ciudad Universitaria, Circuito Exterior
04510 México, D.F., México

Abstract

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.

Keywords: digraphs, kernel, kernel-perfect, critical kernel-imperfect, block-cutpoint tree.

1991 Mathematics Subject Classification: 05C20.

References

[1]	C. Berge, Graphs (North-Holland, Amsterdam, 1985).
[2]	M. Blidia, P. Duchet, F. Maffray, On orientations of perfect graphs, in preparation.
[3]	P. Duchet, Graphes Noyau-Parfaits, Annals Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4.
[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.
[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.
[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.
[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.
[8]	F. Harary, Graph Theory (Addison-Wesley Publishing Company, New York, 1969).

Received 22 April 1997
Revised 3 November 1997