On the Existence and the Number of $(2-d)$-Kernels in Graphs

Abstract

In this paper, we study $(2-d)$-kernels in graphs. We shall show that the problem of the existence of $(2-d)$-kernels is $\mathcal{N}P$-complete for a general graph. We also give some results related to the problem of counting $(2-d)$-kernels in graphs. For special graphs, we show that the number of $(2-d)$-kernels is equal to the Fibonacci numbers.