Portal de Periódicos da CAPES

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

2007; Elsevier BV; Volume: 308; Issue: 20 Linguagem: Inglês

10.1016/j.disc.2007.08.078

1872-681X

Waldemar Szumny, Iwona Włoch, Andrzej Włoch,

Advanced Combinatorial Mathematics

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 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. Włoch, I. Włoch, 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,l)-kernels in it. Moreover, we construct formulas which calculate the number of all (k,l)-kernels, k-independent sets and l-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.