On the Existence of (k,l)-Kernels in Infinite Digraphs: A Survey

H. Galeana-Sánchez ; C. Hernández-Cruz

Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 431-466 / Harvested from The Polish Digital Mathematics Library

Résumé

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

Détail

Publié le : 2014-01-01

Zbl 1292.05123

EUDML-ID : urn:eudml:doc:268081

Bibliographie

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

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

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

[4] D. Bród, A. W loch and I. W loch, 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[Crossref] | Zbl 1112.05042

[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´asz, Every directed graph has a semi-kernel , Lecture Notes in Math. 411 (1974) 175. doi:10.1007/BFb0066192[Crossref]

[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[Crossref]

[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[Crossref] | Zbl 0773.05052

[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[Crossref][WoS] | Zbl 1208.05033

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

[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[WoS][Crossref] | Zbl 1225.05110

[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[Crossref] | Zbl 1284.05114

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

[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. | Zbl 1304.05058

[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[WoS][Crossref] | Zbl 1246.05067

[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´arez-Camacho, On the exis- tence 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[WoS][Crossref] | Zbl 1281.05068

[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[Crossref] | Zbl 0928.05032

[21] A. Ghouila-Houri, Caractérization des graphes non orient´es dont onpeut orienter les arrˆetes de mani`ere `a obtenir le graphe dune relation dordre, Comptes Rendus de l’Acad´emie des Sciences Paris 254 (1962) 1370-1371. | Zbl 0105.35503

[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 [Crossref]

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

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

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

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

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

[28] V. Neumann-Lara, Semin´ucleos de una digr´afica, Anales del Instituto de Matem´aticas 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[Crossref] | Zbl 0060.06506

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

[31] W. Szumny, A.W loch and I.W loch, On (k, l)-kernels in D-join of digraphs, Discuss.

Math. Graph Theory 27 (2007) 457-470. doi:10.7151/dmgt.1373[Crossref]

[32] W. Szumny, A. W loch and I. W loch, 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[Crossref][WoS]

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