Authors:
C. Balbuena, H. Galeana-Sánchez, M.-k. Guevara
Title:
About (k,l)-kernels, semikernels and Grundy functions in partial line digraphs
Source:
Discussiones Mathematicae Graph Theory
Received 28.06.2016, Revised 09.12.2017, Accepted 11.12.2017, doi: 10.7151/dmgt.2104

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\le l \le 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 \mathcal{L} 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 \mathcal{L} 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 \mathcal{L} D.
Keywords:
44696772617068732C20696E2D646F6D696E6174696F6E2C206B65726E656C2C204772756E64792066756E6374696F6E

Links:
PDF