The Total Number of Generalized Stable Sets and Kernels of Graphs

Abstract

In [8] a graph representation of the Fibonacci numbers $F_n$ and Lucas numbers $F_y^{\ast }$ was presented. It is interesting to know that they are the total numbers of all stable sets of undirected graphs $P_n$ and $C_n$, respectively. In this paper we discuss a more general concept of stable sets and kernels of graphs. Our aim is to determine the total numbers of all $k$-stable sets and $(k,k-1)$-kernels of graphs $P_n$ and $C_n$. The results are given by the second-order linear recurrence relations containing generalized Fibonacci and Lucas numbers. Recent problems were investigated in [9], [10].