On the existence and on the number of (k,l)(k,l)-kernels in the lexicographic product of graphs

In [G. Hopkins, W. Staton, Some identities arising from the Fibonacci numbers of certain graphs, Fibonacci Quart. 22 (1984) 225–228.] and [I. Włoch, Generalized Fibonacci polynomial of graphs, Ars Combinatoria 68 (2003) 49–55] the total number of kk-independent sets in the generalized lexicographic product of graphs was given. In this paper we study (k,l)(k,l)-kernels (i.e. kk-independent sets being ll-dominating, simultaneously) in this product and we generalize some results from [A. Włoch, I. Włoch, The total number of maximal kk-independent sets in the generalized lexicographic product of graphs, Ars Combinatoria 75 (2005) 163–170]. We give the necessary and sufficient conditions for the existence of (k,l)(k,l)-kernels in it. Moreover, we construct formulas which calculate the number of all (k,l)(k,l)-kernels, kk-independent sets and ll-dominating sets in the lexicographic product of graphs for all parameters k,lk,l. The result concerning the total number of independent sets generalizes the Fibonacci polynomial of graphs. Also for special graphs we give some recurrence formulas.