Download PDF - Kernels and cycles' subdivisions in arc-colored tournamentsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Kernels and cycles' subdivisions in arc-colored tournaments

Authors 1, 1

Affiliations

  1. 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

Abstract

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.

Keywords

ENG
kernel, kernel by monochromatic paths, tournament

Bibliography

  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, dout≤2, d∈≤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.
Discussiones Mathematicae Graph Theory
2009/29/1
Export to PBN, Opens in new tab
Pages:
101-117
Main language of publication
English
Received
2007-01-30
Accepted
2008-12-03
Published
2009

DOI: 10.7151/dmgt.1435

Exact and natural sciences