About (k, l)-Kernels, Semikernels and Grundy Functions in Partial Line Digraphs

Abstract

Let D be a digraph of minimum in-degree at least 1. We prove that for any two natural numbers k, l such that 1 ≤ l ≤ k, the number of (k, l)-kernels of D is less than or equal to the number of (k, l)-kernels of any partial line digraph ℒD. Moreover, if l < k and the girth of D is at least l +1, then these two numbers are equal. We also prove that the number of semikernels of D is equal to the number of semikernels of ℒD. Furthermore, we introduce the concept of (k, l)-Grundy function as a generalization of the concept of Grundy function and we prove that the number of (k, l)-Grundy functions of D is equal to the number of (k, l)-Grundy functions of any partial line digraph ℒD.

Keywords

• digraphs
• in-domination
• kernel
• grundy function
• 05c20
• 05c69
• 05c76