PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1998 | 18 | 1 | 85-89
Tytuł artykułu

New classes of critical kernel-imperfect digraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
18
Numer
1
Strony
85-89
Opis fizyczny
Daty
wydano
1998
otrzymano
1997-04-22
poprawiono
1997-11-03
Twórcy
  • Instituto de Matemáticas, UNAM, Ciudad Universitaria, Circuito Exterior, 04510 México, D.F., México
  • Instituto de Matemáticas, UNAM, Ciudad Universitaria, Circuito Exterior, 04510 México, D.F., México
Bibliografia
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1065
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.