K-semikernels, k-quasikernels, k-kernels in digraphs and their line digraphs

Abstract

Let D = (V, A) be a digraph with minimum indegree at least one and girth at least k, where k ≥ 2 is an integer. In this paper, the following results are proved: a digraph D has a k-semikernel if and only if its line digraph L(D) does, and the number of k-semikernels in D is less than or equal to the number of k-semikernels in L(D); the number of k-quasikernels in D is less than or equal to that in L(D); the number of k-kernels in D is equal to that in L(D); these results generalize previous results on semikernels, quasikernels and kernels in digraph D due to Galeana-Sánchez et al.