On (k,l)-kernel perfectness of special classes of digraphs

Magdalena Kucharska

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 1-2, page 103-119
  • ISSN: 2083-5892

Abstract

top
In the first part of this paper we give necessary and sufficient conditions for some special classes of digraphs to have a (k,l)-kernel. One of them is the duplication of a set of vertices in a digraph. This duplication come into being as the generalization of the duplication of a vertex in a graph (see [4]). Another one is the D-join of a digraph D and a sequence α of nonempty pairwise disjoint digraphs. In the second part we prove theorems, which give necessary and sufficient conditions for special digraphs presented in the first part to be (k,l)-kernel-perfect digraphs. The concept of a (k,l)-kernel-perfect digraph is the generalization of the well-know idea of a kernel perfect digraph, which was considered in [1] and [6].

How to cite

top

Magdalena Kucharska. "On (k,l)-kernel perfectness of special classes of digraphs." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 103-119. <http://eudml.org/doc/270648>.

@article{MagdalenaKucharska2005,
abstract = {In the first part of this paper we give necessary and sufficient conditions for some special classes of digraphs to have a (k,l)-kernel. One of them is the duplication of a set of vertices in a digraph. This duplication come into being as the generalization of the duplication of a vertex in a graph (see [4]). Another one is the D-join of a digraph D and a sequence α of nonempty pairwise disjoint digraphs. In the second part we prove theorems, which give necessary and sufficient conditions for special digraphs presented in the first part to be (k,l)-kernel-perfect digraphs. The concept of a (k,l)-kernel-perfect digraph is the generalization of the well-know idea of a kernel perfect digraph, which was considered in [1] and [6].},
author = {Magdalena Kucharska},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {kernel; (k,l)-kernel; kernel-perfect digraph; kernel perfect},
language = {eng},
number = {1-2},
pages = {103-119},
title = {On (k,l)-kernel perfectness of special classes of digraphs},
url = {http://eudml.org/doc/270648},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Magdalena Kucharska
TI - On (k,l)-kernel perfectness of special classes of digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 103
EP - 119
AB - In the first part of this paper we give necessary and sufficient conditions for some special classes of digraphs to have a (k,l)-kernel. One of them is the duplication of a set of vertices in a digraph. This duplication come into being as the generalization of the duplication of a vertex in a graph (see [4]). Another one is the D-join of a digraph D and a sequence α of nonempty pairwise disjoint digraphs. In the second part we prove theorems, which give necessary and sufficient conditions for special digraphs presented in the first part to be (k,l)-kernel-perfect digraphs. The concept of a (k,l)-kernel-perfect digraph is the generalization of the well-know idea of a kernel perfect digraph, which was considered in [1] and [6].
LA - eng
KW - kernel; (k,l)-kernel; kernel-perfect digraph; kernel perfect
UR - http://eudml.org/doc/270648
ER -

References

top
  1. [1] C. Berge and P. Duchet, Perfect graphs and kernels, Bulletin of the Institute of Mathematics Academia Sinica 16 (1988) 263-274. Zbl0669.05037
  2. [2] M. Blidia, P. Duchet, H. Jacob, F. Maffray and H. Meyniel, Some operations preserving the existence of kernels, Discrete Math. 205 (1999) 211-216, doi: 10.1016/S0012-365X(99)00026-6. Zbl0936.05047
  3. [3] M. Borowiecki and A. Szelecka, One-factorizations of the generalized Cartesian product and of the X-join of regular graphs, Discuss. Math. Graph Theory 13 (1993) 15-19. Zbl0794.05099
  4. [4] M. Burlet and J. Uhry, Parity graphs, Annals of Discrete Math. 21 (1984) 253-277 Zbl0558.05036
  5. [5] R. Diestel, Graph Theory (Springer-Verlag New-York, Inc., 1997). 
  6. [6] 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
  7. [7] H. Galeana-Sánchez, On the existence of (k,l)-kernels in digraphs, Discrete Math. 85 (1990) 99-102, doi: 10.1016/0012-365X(90)90167-G. Zbl0729.05020
  8. [8] H. Galeana-Sánchez, On the existence of kernels and h-kernels in directed graphs, Discrete Math. 110 (1992) 251-255, doi: 10.1016/0012-365X(92)90713-P. 
  9. [9] H. Galeana-Sanchez and V. Neumann-Lara, On the dichromatic number in kernel theory, Math. Slovaca 48 (1998) 213-219. Zbl0937.05048
  10. [10] H. Jacob, Etude theórique du noyau d' un graphe (Thèse, Univesitè Pierre et Marie Curie, Paris VI, 1979). 
  11. [11] M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combin. 60 (2001) 137-147. Zbl1068.05504
  12. [12] M. Kucharska and M. Kwaśnik, On (k,l)-kernels of special superdigraphs of Pₘ and Cₘ, Discuss. Math. Graph Theory 21 (2001) 95-109, doi: 10.7151/dmgt.1135. 
  13. [13] M. Kwaśnik, On (k,l)-kernels in graphs and their products (PhD Thesis, Technical University of Wrocław, Wrocław, 1980). 
  14. [14] A. Włoch and I. Włoch, On (k,l)-kernels in generalized products, Discrete Math. 164 (1997) 295-301, doi: 10.1016/S0012-365X(96)00064-7. 

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.