ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 16(1) (1996) 5-16 DOI: 10.7151/dmgt.1019
H. Galeana-Sánchez and V. Neumann-Lara
Zona Comercial, Apartado 70-637
04511 México, D.F. MEXICO
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,
Secondary keywords: indepedent kernel modulo Q, co-rooted tree, τ-construction, τ1-construction.
1991 Mathematics Subject Classification: 05C20.