On (k,l)-kernels in D-join of digraphs

Waldemar Szumny; Andrzej Włoch; Iwona Włoch

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 3, page 457-470
  • ISSN: 2083-5892

Abstract

top
In [5] the necessary and sufficient conditions for the existence of (k,l)-kernels in a D-join of digraphs were given if the digraph D is without circuits of length less than k. In this paper we generalize these results for an arbitrary digraph D. Moreover, we give the total number of (k,l)-kernels, k-independent sets and l-dominating sets in a D-join of digraphs.

How to cite

top

Waldemar Szumny, Andrzej Włoch, and Iwona Włoch. "On (k,l)-kernels in D-join of digraphs." Discussiones Mathematicae Graph Theory 27.3 (2007): 457-470. <http://eudml.org/doc/270343>.

@article{WaldemarSzumny2007,
abstract = {In [5] the necessary and sufficient conditions for the existence of (k,l)-kernels in a D-join of digraphs were given if the digraph D is without circuits of length less than k. In this paper we generalize these results for an arbitrary digraph D. Moreover, we give the total number of (k,l)-kernels, k-independent sets and l-dominating sets in a D-join of digraphs.},
author = {Waldemar Szumny, Andrzej Włoch, Iwona Włoch},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {(k,l)-kernel; k-independent set; l-dominating set; D-join; counting; -kernel; -independent set, -dominating set; -join},
language = {eng},
number = {3},
pages = {457-470},
title = {On (k,l)-kernels in D-join of digraphs},
url = {http://eudml.org/doc/270343},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Waldemar Szumny
AU - Andrzej Włoch
AU - Iwona Włoch
TI - On (k,l)-kernels in D-join of digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 3
SP - 457
EP - 470
AB - In [5] the necessary and sufficient conditions for the existence of (k,l)-kernels in a D-join of digraphs were given if the digraph D is without circuits of length less than k. In this paper we generalize these results for an arbitrary digraph D. Moreover, we give the total number of (k,l)-kernels, k-independent sets and l-dominating sets in a D-join of digraphs.
LA - eng
KW - (k,l)-kernel; k-independent set; l-dominating set; D-join; counting; -kernel; -independent set, -dominating set; -join
UR - http://eudml.org/doc/270343
ER -

References

top
  1. [1] M. Blidia, P. Duchet, H. Jacob and F. Maffray, Some operations preserving the existence of kernels, Discrete Math. 205 (1999) 211-216, doi: 10.1016/S0012-365X(99)00026-6. Zbl0936.05047
  2. [2] R. Diestel, Graph Theory (Springer-Verlag, Heidelberg, New-York, Inc., 2005). 
  3. [3] H. Galeana-Sanchez, On the existence of kernels and h-kernels in directed graphs, Discrete Math. 110 (1992) 251-225, doi: 10.1016/0012-365X(92)90713-P. Zbl0770.05050
  4. [4] M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combin. 60 (2001) 137-147. Zbl1068.05504
  5. [5] M. Kucharska, On (k,l)-kernel perfectness of special classes of digraphs, Discuss. Math. Graph Theory 25 (2005) 103-119, doi: 10.7151/dmgt.1265. Zbl1074.05043
  6. [6] M. Kwaśnik and I. Włoch, The total number of generalized stable sets and kernels of graphs, Ars Combin. 55 (2000) 139-146. 
  7. [7] 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. 
  8. [8] I. Włoch, Generalized Fibonacci polynomial of graphs, Ars Combin. 68 (2003) 49-55. Zbl1071.05556

NotesEmbed ?

top

You must be logged in to post comments.