KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition

• Autorzy: H. Galeana-Sánchez , V. Neumann-Lara
• Języki publikacji: EN

Abstrakty

EN

A digraph D is said to satisfy the k-Meyniel's condition if each odd directed cycle of D has at least k diagonals.
The study of the k-Meyniel's condition has been a source of many interesting problems, questions and results in the development of Kernel Theory.
In this paper we present a method to construct a large variety of kernel-perfect (resp. critical kernel-imperfect) digraphs which satisfy the k-Meyniel's condition.

Słowa kluczowe

EN

digraph; kernel; independent set of vertices; absorbing set of vertices; kernel-perfect digraph; critical-kernel-imperfect digraph; τ-system; τ₁-system; indepedent kernel modulo Q; co-rooted tree; τ-construction; τ₁-construction

Kategorie tematyczne

• 05C20: Directed graphs (digraphs), tournaments

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1996
• Tom: 16
• Numer: 1
• Strony: 5-16

Daty

wydano

1996

otrzymano

1994-06-13

poprawiono

1996-04-30

Twórcy

autor

H. Galeana-Sánchez

• Zona Comercial, Apartado 70-637, 04511 México, D.F. MEXICO

autor

V. Neumann-Lara

• Zona Comercial, Apartado 70-637, 04511 México, D.F. MEXICO

Bibliografia

• [1] C. Berge, Graphs (North-Holland, Amsterdam, 1985).
• [2] P. Duchet and H. Meyniel, A note on kernel-critical digraphs, Discrete Math. 33 (1981) 103-105, doi: 10.1016/0012-365X(81)90264-8.
• [3] P. Duchet and H. Meyniel, Une generalization du theoreme de Richarson sur l'existence de noyoux dans les graphes orientes, Discrete Math. 43 (1983) 21-27, doi: 10.1016/0012-365X(83)90017-1.
• [4] P. Duchet, A suffiecient condition for a digraph to be kernel-perfect, J. Graph Theory 11 (1987) 81-81, doi: 10.1002/jgt.3190110112.
• [5] H. Galeana-Sánchez and V. Neumann-Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984) 67-76, doi: 10.1016/0012-365X(84)90131-6.
• [6] H. Galeana-Sánchez and V. Neumann-Lara, On kernel-perfect critical digraphs, Discrete Math. 59 (1986) 257-265, doi: 10.1016/0012-365X(86)90172-X.
• [7] 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.
• [8] H. Jacob, Etude Theorique du Noyau d'un graphe, These, Universite Pierre et Marie Curie, Paris VI, 1979.
• [9] V. Neumann-Lara, Seminúcleos de una digráfica, Anales del Instituto de Matemáticas 11 (1971) UNAM.

Identyfikatory

DOI

10.7151/dmgt.1019