Geodesic
On the existence of (k,l)-kernels in infinite digraphs: A survey
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 431-466.

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

Let D be a digraph, V (D) and A(D) will denote the sets of vertices and arcs of D, respectively. A (k, l)-kernel N of D is a k-independent (if u, v ∈ N, u 6= v, then d(u, v), d(v, u) ≥ k) and l-absorbent (if u ∈ V (D) − N then there exists v ∈ N such that d(u, v) ≤ l) set of vertices. A k-kernel is a (k, k −1)-kernel. This work is a survey of results proving sufficient conditions for the existence of (k, l)-kernels in infinite digraphs. Despite all the previous work in this direction was done for (2, 1)-kernels, we present many original results concerning (k, l)-kernels for distinct values of k and l. The original results are sufficient conditions for the existence of (k, l)- kernels in diverse families of infinite digraphs. Among the families that we study are: transitive digraphs, quasi-transitive digraphs, right/left pretransitive digraphs, cyclically k-partite digraphs, κ-strong digraphs, k-transitive digraphs, k-quasi-transitive digraphs.
Keywords: kernel, k-kernel, infinite digraph, (k, l)-kernel 
@article{DMGT_2014_34_3_a0,
     author = {Galeana-S\'anchez, H. and Hern\'andez-Cruz, C.},
     title = {On the existence of (\protect\emph{k},\protect\emph{l})-kernels in infinite digraphs: {A} survey},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {431--466},
     publisher = {mathdoc},
     volume = {34},
     number = {3},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a0/}
}
TY  - JOUR
AU  - Galeana-Sánchez, H.
AU  - Hernández-Cruz, C.
TI  - On the existence of (k,l)-kernels in infinite digraphs: A survey
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 431
EP  - 466
VL  - 34
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a0/
LA  - en
ID  - DMGT_2014_34_3_a0
ER  - 
%0 Journal Article
%A Galeana-Sánchez, H.
%A Hernández-Cruz, C.
%T On the existence of (k,l)-kernels in infinite digraphs: A survey
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 431-466
%V 34
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a0/
%G en
%F DMGT_2014_34_3_a0
Galeana-Sánchez, H.; Hernández-Cruz, C. On the existence of (k,l)-kernels in infinite digraphs: A survey. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 431-466. http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a0/

[1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag, Berlin Heidelberg New York, 2002).

[2] J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141-161. doi:10.1002/jgt.3190200205

[3] C. Berge, Graphs (North-Holland, Amsterdam New York, 1985).

[4] D. Bród, A. Włoch and I. Włoch, On the existence of (k, k − 1)-kernels in directed graphs, J. Math. Appl. 28 (2006) 7-12.

[5] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The Strong Perfect Graph Theorem, Ann. of Math. 164 (2006) 51-229. doi:10.4007/annals.2006.164.51

[6] V. Chvátal, On the computational complexity of finding a kernel, Report No. CRM-300, Centre de Recherches Mathematiques, Universite de Montreal, 1973.

[7] V. Chvátal and L. Lovász, Every directed graph has a semi-kernel, Lecture Notes in Math. 411 (1974) 175. doi:10.1007/BFb0066192

[8] R. Diestel, Graph Theory 3rd Edition (Springer-Verlag, Berlin Heidelberg New York, 2005).

[9] P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 (1980) 93-101. doi:10.1016/S0167-5060(08)70041-4

[10] P. Duchet and H. Meyniel, Kernels in directed graphs: a poison game, Discrete Math. 115 (1993) 273-276. doi:10.1016/0012-365X(93)90496-G

[11] P.L. Erdös and L. Soukup, Quasi-kernels and quasi-sinks in infinite digraphs, Discrete Math. 309 (2009) 3040-3048. doi:10.1016/j.disc.2008.08.006

[12] A.S. Fraenkel, Combinatorial game theory foundations applied to digraph kernels, Electron. J. Combin. 4 (1997) #R10.

[13] H. Galeana-Sánchez and M. Guevara, Some sufficient conditions for the existence of kernels in infinite digraphs, Discrete Math. 309 (2009) 3680-3693. doi:10.1016/j.disc.2008.01.025

[14] H. Galeana-Sánchez and C. Hernández-Cruz, Cyclically k-partite digraphs and k- kernels, Discuss. Math. Graph Theory 31 (2011) 63-78. doi:10.7151/dmgt.1530

[15] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in generalizations of transitive digraphs, Discuss. Math. Graph Theory 31 (2011) 293-312. doi:10.7151/dmgt.1546

[16] H. Galeana-Sánchez and C. Hernández-Cruz, On the existence of (k, l)-kernels in digraphs with a given circumference, AKCE Int. J. Graphs Combin. (2013), to appear.

[17] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in k-transitive and k-quasi-transitive digraphs, Discrete Math. 312 (2012) 2522-2530. doi:10.1016/j.disc.2012.05.005

[18] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in multipartite tournaments, AKCE Int. J. Graphs Combin. 8 (2011) 181-198.

[19] H. Galeana-Sánchez, C. Hernández-Cruz and M.A. Juárez-Camacho, On the existence and number of (k+1)-kings in k-quasi-transitive digraphs, Discrete Math. 313 (2013) 2582-2591. doi:10.1016/j.disc.2013.08.007

[20] H. Galeana-Sánchez and H.A. Rincón, A sufficient condition for the existence of k-kernels in digraphs, Discuss. Math. Graph Theory 18 (1998) 197-204. doi:10.7151/dmgt.1075

[21] A. Ghouila-Houri, Caractérization des graphes non orientés dont onpeut orienter les arrêtes de manière à obtenir le graphe dune relation dordre, Comptes Rendus de l’Académie des Sciences Paris 254 (1962) 1370-1371.

[22] P. Hell and C. Hernández-Cruz, On the complexity of the 3-kernel problem in some classes of digraphs, Discuss. Math. Graph Theory 34 (2014) 167-201. doi:10.7151/dmgt.1727

[23] P. Hell and J. Nešetřil, Graphs and Homomorphisms (Oxford University Press, 2004). doi:10.1093/acprof:oso/9780198528173.001.0001

[24] M. Kucharska and M. Kwaśnik, On (k, l)-kernels of special superdigraphs of $P_m$ and $C_m$, Discuss. Math. Graph Theory 21 (2001) 95-109. doi:10.7151/dmgt.1135

[25] M. Kwaśnik, On (k, l)-kernels on graphs and their products, Doctoral Dissertation, Technical University of Wrocław, Wrocław, 1980.

[26] M. Kwaśnik, The generalizaton of Richardson’s theorem, Discuss. Math. 4 (1981) 11-14.

[27] M. Kwaśnik, A. Włoch and I. Włoch, Some remarks about (k, l)-kernels in directed and undirected graphs, Discuss. Math. 13 (1993) 29-37.

[28] V. Neumann-Lara, Seminúcleos de una digráfica, Anales del Instituto de Matemáticas II (1971).

[29] M. Richardson, On weakly ordered systems, Bull. Amer. Math. Soc. 52 (1946) 113-116. doi:10.1090/S0002-9904-1946-08518-3

[30] R. Rojas-Monroy and I. Villarreal-Valdés, Kernels in infinite digraphs, AKCE Int. J. Graphs Combin. 7 (2010) 103-111.

[31] W. Szumny, 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

[32] W. Szumny, 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

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