کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650238 | 1342481 | 2008 | 9 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the existence and on the number of (k,l)(k,l)-kernels in the lexicographic product of graphs On the existence and on the number of (k,l)(k,l)-kernels in the lexicographic product of graphs](/preview/png/4650238.png)
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.
Journal: Discrete Mathematics - Volume 308, Issue 20, 28 October 2008, Pages 4616–4624