Geodesic
About (k, l)-Kernels, Semikernels and Grundy Functions in Partial Line Digraphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 855-856.

Voir la notice de l'article provenant de la source Library of Science

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 lt; 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 
@article{DMGT_2019_39_4_a6,
     author = {Balbuena, C. and Galeana-S\'anchez, H. and Guevara, M.},
     title = {About (k, {l)-Kernels,} {Semikernels} and {Grundy} {Functions} in {Partial} {Line} {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {855--856},
     publisher = {mathdoc},
     volume = {39},
     number = {4},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a6/}
}
TY  - JOUR
AU  - Balbuena, C.
AU  - Galeana-Sánchez, H.
AU  - Guevara, M.
TI  - About (k, l)-Kernels, Semikernels and Grundy Functions in Partial Line Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 855
EP  - 856
VL  - 39
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a6/
LA  - en
ID  - DMGT_2019_39_4_a6
ER  - 
%0 Journal Article
%A Balbuena, C.
%A Galeana-Sánchez, H.
%A Guevara, M.
%T About (k, l)-Kernels, Semikernels and Grundy Functions in Partial Line Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 855-856
%V 39
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a6/
%G en
%F DMGT_2019_39_4_a6
Balbuena, C.; Galeana-Sánchez, H.; Guevara, M. About (k, l)-Kernels, Semikernels and Grundy Functions in Partial Line Digraphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 855-856. http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a6/

[1] M. Aigner, On the linegraph of a directed graph, Math. Z. 102 (1967) 56–61. doi:10.1007/BF01110285

[2] C. Balbuena and M. Guevara, Kernels and partial line digraphs, Appl. Math. Lett. 23 (2010) 1218–1220. doi:10.1016/j.aml.2010.06.001

[3] C. Berge, Graphs, (North Holland, 1985) Chapter 14.

[4] E. Boros and V. Gurvich, Perfect Graphs, Kernels and Cores of Cooperative Games (RUTCOR Research Report 12, Rutgers University, 2003).

[5] M.A. Fiol, J.L.A. Yebra and I. Alegre, Line digraph iterations and the ( d, k ) problem, IEEE Trans. Comput. 33 (1984) 400–403. doi:10.1109/TC.1984.1676455

[6] M.A. Fiol and A.S. Lladó, The partial line digraph technique in the design of large interconnection networks, IEEE Trans. Comput. 41 (1992) 848–857. doi:10.1109/12.256453

[7] A.S. Fraenkel, Combinatorial games: selected bibliography with a succinct gourmet introduction, Electron. J. Combin. (2012) #DS2.

[8] H. Galeana-Sánchez and C. Herńandez-Cruz, On the existence of ( k, l ) -kernels in infinite digraphs: a survey, Discuss. Math. Graph Theory 34 (2014) 431–466. doi:10.7151/dmgt.1747

[9] H. Galeana-Sánchez and X. Li, Semikernels and ( k, l ) -kernels in digraphs, SIAM J. Discrete Math. 11 (1998) 340–346. doi:10.1137/S0895480195291370

[10] H. Galeana-Sánchez, L. Pastrana-Ramírez and H.A. Rincón-Mejía, Semikernels, quasi kernels, and Grundy function in the line digraph, SIAM J. Discrete Math. 4 (1991) 80–83. doi:10.1137/0404008

[11] M. Harminc, Solutions and kernels of a directed graph, Math. Slovaca 32 (1982) 263–267.

[12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced topics (Marcel Dekker, New York, 1998).

[13] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944).

[14] V. Neumann-Lara, Seminúcleos de una digráfica, Anales del Instituto de Matemáticas de la Universidad Nacional Autónoma de México II (1971) 55–62.

[15] H. Prodinger and R.F. Tichy, Fibonacci numbers of graphs, Fibonacci Quart. 20 (1982) 16–21.

[16] L. Qin, S. Er-fang and Z. Min, ( k, l ) -kernels in line digraphs, J. Shanghai Univ. 10 (2006) 484–486. doi:10.1007/s11741-006-0042-5

[17] S.M. Reddy, J.G. Kuhl, S.H. Hosseini and H. Lee, On digraphs with minimum diam- eter and maximum connectivity, in: Proc. 20th Annual Allerton Conference (1982) 1018–1026.

[18] W. Szummy, A. Włoch and I. Włoch, On ( k, l ) -kernels in D-join of digraphs, Discuss. Math. Graph Theory. 27 (2007) 457–470. doi:10.7151/dmgt.1373

[19] W. Szummy, A. Włoch and I. Włoch, On the existence and on the number of ( k, l ) - kernels in the lexicographic product of graphs, Discrete Math. 308 (2008) 4616–4624. doi:10.1016/j.disc.2007.08.078

[20] A. Włoch and I. Włoch, On ( k, l ) -kernels in the corona of digraphs, Int. J. Pure Appl. Math. 53 (2009) 571–581.