A sufficient condition for the existence of k-kernels in digraphs

H. Galeana-Sánchez; H.A. Rincón-Mejía

Discussiones Mathematicae Graph Theory (1998)

  • Volume: 18, Issue: 2, page 197-204
  • ISSN: 2083-5892

Abstract

top
In this paper, we prove the following sufficient condition for the existence of k-kernels in digraphs: Let D be a digraph whose asymmetrical part is strongly conneted and such that every directed triangle has at least two symmetrical arcs. If every directed cycle γ of D with l(γ) ≢ 0 (mod k), k ≥ 2 satisfies at least one of the following properties: (a) γ has two symmetrical arcs, (b) γ has four short chords. Then D has a k-kernel. This result generalizes some previous results on the existence of kernels and k-kernels in digraphs. In particular, it generalizes the following Theorem of M. Kwaśnik [5]: Let D be a strongly connected digraph, if every directed cycle of D has length ≡ 0 (mod k), k ≥ 2. Then D has a k-kernel.

How to cite

top

H. Galeana-Sánchez, and H.A. Rincón-Mejía. "A sufficient condition for the existence of k-kernels in digraphs." Discussiones Mathematicae Graph Theory 18.2 (1998): 197-204. <http://eudml.org/doc/270530>.

@article{H1998,
abstract = { In this paper, we prove the following sufficient condition for the existence of k-kernels in digraphs: Let D be a digraph whose asymmetrical part is strongly conneted and such that every directed triangle has at least two symmetrical arcs. If every directed cycle γ of D with l(γ) ≢ 0 (mod k), k ≥ 2 satisfies at least one of the following properties: (a) γ has two symmetrical arcs, (b) γ has four short chords. Then D has a k-kernel. This result generalizes some previous results on the existence of kernels and k-kernels in digraphs. In particular, it generalizes the following Theorem of M. Kwaśnik [5]: Let D be a strongly connected digraph, if every directed cycle of D has length ≡ 0 (mod k), k ≥ 2. Then D has a k-kernel. },
author = {H. Galeana-Sánchez, H.A. Rincón-Mejía},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {digraph; kernel; k-kernel; -kernel},
language = {eng},
number = {2},
pages = {197-204},
title = {A sufficient condition for the existence of k-kernels in digraphs},
url = {http://eudml.org/doc/270530},
volume = {18},
year = {1998},
}

TY - JOUR
AU - H. Galeana-Sánchez
AU - H.A. Rincón-Mejía
TI - A sufficient condition for the existence of k-kernels in digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 1998
VL - 18
IS - 2
SP - 197
EP - 204
AB - In this paper, we prove the following sufficient condition for the existence of k-kernels in digraphs: Let D be a digraph whose asymmetrical part is strongly conneted and such that every directed triangle has at least two symmetrical arcs. If every directed cycle γ of D with l(γ) ≢ 0 (mod k), k ≥ 2 satisfies at least one of the following properties: (a) γ has two symmetrical arcs, (b) γ has four short chords. Then D has a k-kernel. This result generalizes some previous results on the existence of kernels and k-kernels in digraphs. In particular, it generalizes the following Theorem of M. Kwaśnik [5]: Let D be a strongly connected digraph, if every directed cycle of D has length ≡ 0 (mod k), k ≥ 2. Then D has a k-kernel.
LA - eng
KW - digraph; kernel; k-kernel; -kernel
UR - http://eudml.org/doc/270530
ER -

References

top
  1. [1] C. Berge, Graphs and hypergraphs (North-Holland, Amsterdan, 1973). 
  2. [2] P. Duchet, Graphes Noyau-Porfaits, Ann. Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4. 
  3. [3] 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
  4. [4] H. Galeana-Sánchez, On the existence of kernels and k-kernels in directed graphs, Discrete Math. 110 (1992) 251-255, doi: 10.1016/0012-365X(92)90713-P. 
  5. [5] M. Kwaśnik, The generalization of Richardson theorem, Discussiones Math. IV (1981) 11-14. Zbl0509.05048
  6. [6] M. Kwaśnik, On (k,l)-kernels of exclusive disjunction, cartesian sum and normal product of two directed graphs, Discussiones Math. V (1982) 29-34. Zbl0508.05038

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.