On the Existence of (k,l)-Kernels in Infinite Digraphs: A Survey
H. Galeana-Sánchez; C. Hernández-Cruz
Discussiones Mathematicae Graph Theory (2014)
- Volume: 34, Issue: 3, page 431-466
- ISSN: 2083-5892
Access Full Article
topAbstract
topHow to cite
topH. Galeana-Sánchez, and C. Hernández-Cruz. "On the Existence of (k,l)-Kernels in Infinite Digraphs: A Survey." Discussiones Mathematicae Graph Theory 34.3 (2014): 431-466. <http://eudml.org/doc/268081>.
@article{H2014,
abstract = {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},
author = {H. Galeana-Sánchez, C. Hernández-Cruz},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {kernel; k-kernel; (k; l)-kernel; infinite digraph; -kernel; -kernel},
language = {eng},
number = {3},
pages = {431-466},
title = {On the Existence of (k,l)-Kernels in Infinite Digraphs: A Survey},
url = {http://eudml.org/doc/268081},
volume = {34},
year = {2014},
}
TY - JOUR
AU - H. Galeana-Sánchez
AU - C. Hernández-Cruz
TI - On the Existence of (k,l)-Kernels in Infinite Digraphs: A Survey
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 3
SP - 431
EP - 466
AB - 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
LA - eng
KW - kernel; k-kernel; (k; l)-kernel; infinite digraph; -kernel; -kernel
UR - http://eudml.org/doc/268081
ER -
References
top- [1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag, Berlin Heidelberg New York, 2002). Zbl1001.05002
- [2] J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141-161. doi:10.1002/jgt.3190200205[Crossref] Zbl0832.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] Zbl1112.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] Zbl0773.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] Zbl1208.05033
- [12] A.S. Fraenkel, Combinatorial game theory foundations applied to digraph kernels, Electron. J. Combin. 4 (1997) #R10. Zbl0884.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] Zbl1225.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] Zbl1284.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. Zbl1304.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] Zbl1246.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] Zbl1281.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] Zbl0928.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. Zbl0105.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] Zbl1062.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] Zbl0060.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). Zbl0053.09303
Citations in EuDML Documents
topNotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.