PDF
awloch@prz.edu.pl
e-mail: iwloch@prz.edu.pl
Close
Discussiones Mathematicae Graph Theory 27(3) (2007)
457-470
DOI: https://doi.org/10.7151/dmgt.1373
ON (k,l)-KERNELS IN D-JOIN OF DIGRAPHS
Waldemar Szumny, Andrzej Włoch and Iwona Włoch
Faculty of Mathematics and Applied Physics
Rzeszów University of Technology
W. Pola 2, 35-959 Rzeszów, Poland
e-mail:
e-mail:
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.Keywords: (k,l)-kernel, k-independent set, l-dominating set, D-join, counting.
2000 Mathematics Subject Classification: 05C20.
References
[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. |
[2] | R. Diestel, Graph Theory (Springer-Verlag, Heidelberg, New-York, Inc., 2005). |
[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. |
[4] | M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combin. 60 (2001) 137-147. |
[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. |
[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] | 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] | I. Włoch, Generalized Fibonacci polynomial of graphs, Ars Combin. 68 (2003) 49-55. |
Received 29 April 2006
Revised 18 May 2007
Accepted 18 May 2007
Close