Some sufficient conditions on odd directed cycles of bounded length for the existence of a kernel

Hortensia Galeana-Sánchez

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 2, page 171-182
  • ISSN: 2083-5892

Abstract

top
A kernel N of a digraph D is an independent set of vertices of D such that for every w ∈ V(D)-N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel-perfect digraph. In this paper I investigate some sufficient conditions for a digraph to have a kernel by asking for the existence of certain diagonals or symmetrical arcs in each odd directed cycle whose length is at most 2α(D)+1, where α(D) is the maximum cardinality of an independent vertex set of D. Previous results are generalized.

How to cite

top

Hortensia Galeana-Sánchez. "Some sufficient conditions on odd directed cycles of bounded length for the existence of a kernel." Discussiones Mathematicae Graph Theory 24.2 (2004): 171-182. <http://eudml.org/doc/270195>.

@article{HortensiaGaleana2004,
abstract = {A kernel N of a digraph D is an independent set of vertices of D such that for every w ∈ V(D)-N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel-perfect digraph. In this paper I investigate some sufficient conditions for a digraph to have a kernel by asking for the existence of certain diagonals or symmetrical arcs in each odd directed cycle whose length is at most 2α(D)+1, where α(D) is the maximum cardinality of an independent vertex set of D. Previous results are generalized.},
author = {Hortensia Galeana-Sánchez},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {kernel; kernel-perfect; critical kernel-imperfect; digraph},
language = {eng},
number = {2},
pages = {171-182},
title = {Some sufficient conditions on odd directed cycles of bounded length for the existence of a kernel},
url = {http://eudml.org/doc/270195},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
TI - Some sufficient conditions on odd directed cycles of bounded length for the existence of a kernel
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 2
SP - 171
EP - 182
AB - A kernel N of a digraph D is an independent set of vertices of D such that for every w ∈ V(D)-N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel-perfect digraph. In this paper I investigate some sufficient conditions for a digraph to have a kernel by asking for the existence of certain diagonals or symmetrical arcs in each odd directed cycle whose length is at most 2α(D)+1, where α(D) is the maximum cardinality of an independent vertex set of D. Previous results are generalized.
LA - eng
KW - kernel; kernel-perfect; critical kernel-imperfect; digraph
UR - http://eudml.org/doc/270195
ER -

References

top
  1. [1] J. Bang-Jensen, J. Huang and E. Prisner, In-Tournament Digraphs, J. Combin. Theory (B) 59 (1993) 267-287, doi: 10.1006/jctb.1993.1069. Zbl0794.05033
  2. [2] C. Berge, Graphs, North-Holland Mathematical Library, Vol. 6 (North-Holland, Amsterdam, 1985). 
  3. [3] C. Berge, Nouvelles extensions du noyau d'un graphe et ses applications en théorie des jeux, Publ. Econométriques 6 (1977). 
  4. [4] P. Duchet, Graphes Noyau-Parfaits, Ann. Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4. 
  5. [5] P. Duchet, A sufficient condition for a digraph to be kernel-perfect, J. Graph Theory 11 (1987) 81-85, doi: 10.1002/jgt.3190110112. Zbl0607.05036
  6. [6] P. Duchet and H. Meyniel, A note on kernel-critical graphs, Discrete Math. 33 (1981) 103-105, doi: 10.1016/0012-365X(81)90264-8. Zbl0456.05032
  7. [7] H. Galeana-Sánchez, Normal fraternally orientable graphs satisfy the strong perfect graph conjecture, Discrete Math. 122 (1993) 167-177, doi: 10.1016/0012-365X(93)90293-3. Zbl0791.05046
  8. [8] 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
  9. [9] H. Galeana-Sánchez, B₁ and B₂-orientable graphs in kernel theory, Discrete Math. 143 (1995) 269-274, doi: 10.1016/0012-365X(94)00021-A. 
  10. [10] F. Gavril, V. Toledano and D. de Werra, Chordless paths, odd holes and kernels in graphs without M-obstructions, preprint. Zbl0807.05035
  11. [11] F. Gavril and J. Urrutia, An Algorithm for fraternal orientation of graphs, Information Processing Letters 41 (1993) 271-279. Zbl0764.68135
  12. [12] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944). Zbl0063.05930
  13. [13] M. Richardson, Solutions of irreflexive relations, Ann. Math. 58 (1953) 573, doi: 10.2307/1969755. Zbl0053.02902
  14. [14] M. Richardson, Extensions theorems for solutions of irreflexive relations, Proc. Nat. Acad. Sci. USA. 39 (1953) 649, doi: 10.1073/pnas.39.7.649. Zbl0053.02903
  15. [15] D.J. Rose, Triangulated graphs and the elimination process, J. Math. Anal. Appl. 32 (1970) 597-609, doi: 10.1016/0022-247X(70)90282-9. Zbl0216.02602
  16. [16] D.J. Skrien, A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular arc graphs, and nested interval graphs, J. Graph Theory 6 (1982) 309-316, doi: 10.1002/jgt.3190060307. Zbl0495.05027

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.