On the existence and on the number of (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. Wloch, Generalized Fibonacci polynomial of graphs, Ars Combinatoria 68 (2003) 49-55] the total number of k-independent sets in the generalized lexicographic product of graphs was given. In this paper we study (k, l)-kernels (i.e. k-independent sets being l-dominating. simultaneously) in this product and we generalize some results from [A. Wloch, I. Wloch, The total number of maximal k-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. I)-kernels in it. Moreover, we construct formulas which calculate the number of all (k, l)-kernels, k-independent sets and I-dominating sets in the lexicographic product of graphs for all parameters k. 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. (C) 2007 Elsevier B.V. All rights reserved.