DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 16(1) (1996) 5-16
DOI: 10.7151/dmgt.1019

KP-DIGRAPHS AND CKI-DIGRAPHS SATISFYING THE k-MEYNIEL'S CONDITION

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

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

Abstract

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.

Primary keywords: digraph, kernel, independent set of vertices, absorbing set of vertices, kernel-perfect digraph, critical-kernel-imperfect digraph, τ-system, τ1-system.

Secondary keywords: indepedent kernel modulo Q, co-rooted tree, τ-construction, τ1-construction.

1991 Mathematics Subject Classification: 05C20.

References

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