PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 3 | 431-466
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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
Słowa kluczowe
Wydawca
Rocznik
Tom
34
Numer
3
Strony
431-466
Opis fizyczny
Daty
wydano
2014-08-01
otrzymano
2010-12-08
poprawiono
2013-05-16
zaakceptowano
2013-05-16
online
2014-07-16
Twórcy
  • Instituto de Matemáticas Universidad Nacional Autónoma de México Ciudad Universitaria, México, D.F., C.P. 04510, México, hgaleana@matem.unam.mx
  • Instituto de Matemáticas Universidad Nacional Autónoma de México Ciudad Universitaria, México, D.F., C.P. 04510, México, cesar@matem.unam.mx
Bibliografia
  • [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[Crossref]
  • [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]
  • [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]
  • [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]
  • [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[WoS][Crossref]
  • [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]
  • [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.
  • [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]
  • [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]
  • [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]
  • [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.
  • [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]
  • [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]
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1747
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.