# New classes of critical kernel-imperfect digraphs

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

Discussiones Mathematicae Graph Theory (1998)

- Volume: 18, Issue: 1, page 85-89
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topHortensia Galeana-Sánchez, and V. Neumann-Lara. "New classes of critical kernel-imperfect digraphs." Discussiones Mathematicae Graph Theory 18.1 (1998): 85-89. <http://eudml.org/doc/270780>.

@article{HortensiaGaleana1998,

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.},

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

journal = {Discussiones Mathematicae Graph Theory},

keywords = {digraphs; kernel; kernel-perfect; critical kernel-imperfect; block-cutpoint tree; critical kernel-imperfect digraphs},

language = {eng},

number = {1},

pages = {85-89},

title = {New classes of critical kernel-imperfect digraphs},

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

volume = {18},

year = {1998},

}

TY - JOUR

AU - Hortensia Galeana-Sánchez

AU - V. Neumann-Lara

TI - New classes of critical kernel-imperfect digraphs

JO - Discussiones Mathematicae Graph Theory

PY - 1998

VL - 18

IS - 1

SP - 85

EP - 89

AB - 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.

LA - eng

KW - digraphs; kernel; kernel-perfect; critical kernel-imperfect; block-cutpoint tree; critical kernel-imperfect digraphs

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

ER -

## References

top- [1] C. Berge, Graphs (North-Holland, Amsterdam, 1985).
- [2] M. Blidia, P. Duchet, F. Maffray, On orientations of perfect graphs, in preparation. Zbl0780.05020
- [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. Zbl0675.05033
- [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. Zbl0593.05034
- [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. Zbl0748.05060
- [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. Zbl0811.05027
- [8] F. Harary, Graph Theory (Addison-Wesley Publishing Company, New York, 1969).

## NotesEmbed ?

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