PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2009 | 29 | 1 | 101-117
Tytuł artykułu

Kernels and cycles' subdivisions in arc-colored tournaments

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let D be a digraph. D is said to be an m-colored digraph if the arcs of D are colored with m colors. A path P in D is called monochromatic if all of its arcs are colored alike. Let D be an m-colored digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following conditions: a) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them; and b) for every vertex x ∈ V(D)-N there is a vertex n ∈ N such that there is an xn-monochromatic directed path in D. In this paper we prove that if T is an arc-colored tournament which does not contain certain subdivisions of cycles then it possesses a kernel by monochromatic paths. These results generalize a well known sufficient condition for the existence of a kernel by monochromatic paths obtained by Shen Minggang in 1988 and another one obtained by Hahn et al. in 2004. Some open problems are proposed.
Słowa kluczowe
Wydawca
Rocznik
Tom
29
Numer
1
Strony
101-117
Opis fizyczny
Daty
wydano
2009
otrzymano
2007-01-30
poprawiono
2008-12-03
zaakceptowano
2008-12-03
Twórcy
  • Instituto de Matemáticas, U.N.A.M. Área de la investigación científica, Circuito Exterior, Ciudad Universitaria, Coyoacán 04510, México, D.F. México
  • Instituto de Matemáticas, U.N.A.M. Área de la investigación científica, Circuito Exterior, Ciudad Universitaria, Coyoacán 04510, México, D.F. México
Bibliografia
  • [1] C. Berge, Graphs (Nort-Holland, Amsterdam, third edition, 1991).
  • [2] C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27-31, doi: 10.1016/0012-365X(90)90346-J.
  • [3] E. Boros and V. Gurvich, A corrected version of the Duchet kernel conjecture, Discrete Math. 179 (1998) 231-233, doi: 10.1016/S0012-365X(97)00094-0.
  • [4] E. Boros and V. Gurvich, Perfect graphs, kernels and cores of cooperative games, 2003, RUTCOR Research Report, 12, Rutgers University, Dedicated to the memory of Claude Berge, New Jersey.
  • [5] V. Chvátal, On the computational complexity of finding a kernel, Report, CRM-300, Centre de Recherches Mathématiques, Université de Montréal (Montréal, 1973).
  • [6] P. Duchet, Représentations, Noyaux en Théorie des Graphes et Hypergraphes (Paris, Univ. Paris 6, 1979) 200.
  • [7] P. Duchet and H. Meyniel, A note on kernel-critical graphs, Discrete Math. 33 (1981) 103-105, doi: 10.1016/0012-365X(81)90264-8.
  • [8] A.S. Fraenkel, Planar kernel and Grundy with d ≤ 3, $d_{out} ≤ 2$, $d_{in} ≤ 2$ are NP-complete, Discrete Appl. Math. 3 (1981) 257-262, doi: 10.1016/0166-218X(81)90003-2.
  • [9] A.S. Fraenkel, Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction, The Electronic Journal of Combinatorics, 14 Dynamic Survey DS2, 2007.
  • [10] H. Galeana-Sánchez, On the existence of kernels and h-kernels in directed graphs, Discrete Math. 110 (1992) 251-255, doi: 10.1016/0012-365X(92)90713-P.
  • [11] H. Galeana-Sánchez, On monochromatic paths and monochromatic cycles in edge colored tournaments, Discrete Math. 156 (1996) 103-112, doi: 10.1016/0012-365X(95)00036-V.
  • [12] H. Galeana-Sánchez and V. Neumann-Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984) 67-76, doi: 10.1016/0012-365X(84)90131-6.
  • [13] H. Galeana-Sánchez and V. Neumann-Lara, On kernel-perfect critical digraphs, Discrete Math. 59 (1986) 257-265, doi: 10.1016/0012-365X(86)90172-X.
  • [14] H. Galeana-Sánchez and H. Rincón-Mejía, A sufficient condition for the existence of k-kernels in digraphs, Discuss. Math. Graph Theory 18 (1998) 197-204, doi: 10.7151/dmgt.1075.
  • [15] H. Galeana-Sánchez and R. Rojas-Monroy, On monochromatic paths and monochromatic 4-cycles in edge-colored bipartite tournaments, Discrete Math. 285 (2004) 313-318, doi: 10.1016/j.disc.2004.03.005.
  • [16] H. Galeana-Sánchez and R. Rojas-Monroy, On monochromatic paths and at most 2-colored arc sets in edge colored tournaments, Graphs and Combinatorics 21 (2005) 307-317, doi: 10.1007/s00373-005-0618-z.
  • [17] H. Galeana-Sánchez and R. Rojas-Monroy, Kernels in edge-coloured orientations of nearly complete graphs, Discrete Math. 308 (2008) 4599-4607, doi: 10.1016/j.disc.2007.08.079.
  • [18] M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combin. 60 (2001) 137-147.
  • [19] M. Kucharska and M. Kwaśnik, On (k,l)-kernels of special superdigraphs of Pₘ and Cₘ, Discuss. Math. Graph Theory 21 (2001) 95-109, doi: 10.7151/dmgt.1135.
  • [20] M. Kwaśnik, The generalization of Richardson theorem, Discuss. Math. IV (1981) 11-14.
  • [21] M. Kwaśnik, On (k,l)-kernels of exclusive disjunction, cartesian sum and normal product of two directed graphs, Discuss. Math. V (1982) 29-34.
  • [22] G. Hahn, P. Ille and R.E. Woodrow, Absorbing sets in arc-coloured tournaments, Discrete Math. 283 (2004) 93-99, doi: 10.1016/j.disc.2003.10.024.
  • [23] J. von Neumann and O. Morgenstern, Theory of games and economic behaviour, (Princeton University Press, Princeton, 2nd edition, 1947).
  • [24] B. Sands, N. Sauer and R.E. Woodrow, On monochromatic paths in edge-colored digraphs, J. Combin. Theory (B) 33 (1982) 271-275, doi: 10.1016/0095-8956(82)90047-8.
  • [25] Shen Minggang, On monochromatic paths in m-colored tournaments, J. Combin. Theory (B) 45 (1988) 108-111, doi: 10.1016/0095-8956(88)90059-7.
  • [26] M. Richardson, Solutions of irreflexive relations, Annals of Mathematics 58 (1953) 573-590, doi: 10.2307/1969755.
  • [27] J. van Leeuwen, Having a Grundy-numbering is NP-complete, Report, 207, Computer Science Dept., Pennsylvania State University, University Park, PA, 1976.
  • [28] V. Neumann-Lara, Seminúcleos y núcleos, Anales del Instituto de Matemáticas UNAM 11 (1971) 55-62.
  • [29] A. Włoch and I. Włoch, On (k,l)-kernels in generalized products, Discrete Math. 164 (1997) 295-301, doi: 10.1016/S0012-365X(96)00064-7.
  • [30] I. Włoch, On imp-sets and kernels by monochromatic paths of the duplication, Ars Combin. 83 (2007) 93-100.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1435
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ć.