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
Close