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

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

Discussiones Mathematicae Graph Theory (1996)

  • Volume: 16, Issue: 1, page 5-16
  • ISSN: 2083-5892

Abstract

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

How to cite

top

H. Galeana-Sánchez, and V. Neumann-Lara. "KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition." Discussiones Mathematicae Graph Theory 16.1 (1996): 5-16. <http://eudml.org/doc/270225>.

@article{H1996,
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. },
author = {H. Galeana-Sánchez, V. Neumann-Lara},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {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; independent set; absorbing set; independent kernel; kernel-perfect; critical kernel-imperfect},
language = {eng},
number = {1},
pages = {5-16},
title = {KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition},
url = {http://eudml.org/doc/270225},
volume = {16},
year = {1996},
}

TY - JOUR
AU - H. Galeana-Sánchez
AU - V. Neumann-Lara
TI - KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition
JO - Discussiones Mathematicae Graph Theory
PY - 1996
VL - 16
IS - 1
SP - 5
EP - 16
AB - 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.
LA - eng
KW - 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; independent set; absorbing set; independent kernel; kernel-perfect; critical kernel-imperfect
UR - http://eudml.org/doc/270225
ER -

References

top
  1. [1] C. Berge, Graphs (North-Holland, Amsterdam, 1985). 
  2. [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. Zbl0456.05032
  3. [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. Zbl0502.05027
  4. [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. Zbl0607.05036
  5. [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. Zbl0529.05024
  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. Zbl0593.05034
  7. [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. Zbl0748.05060
  8. [8] H. Jacob, Etude Theorique du Noyau d'un graphe, These, Universite Pierre et Marie Curie, Paris VI, 1979. 
  9. [9] V. Neumann-Lara, Seminúcleos de una digráfica, Anales del Instituto de Matemáticas 11 (1971) UNAM. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.