Download PDF - Monochromatic paths and monochromatic sets of arcs in bipartite tournamentsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Monochromatic paths and monochromatic sets of arcs in bipartite tournaments

Authors 1, 2, 1

Affiliations

  1. Instituto de Matemáticas, Universidad Nacional Autónoma de México, Ciudad Universitaria, México, D.F. 04510, México
  2. Facultad de Ciencias, Universidad Autónoma del Estado de México, Instituto Literario, Centro 50000, Toluca, Edo. de México, México

Abstract

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours and all of them are used. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices there is no monochromatic path between them and for every vertex v in V(D)∖N there is a monochromatic path from v to some vertex in N. We denote by A⁺(u) the set of arcs of D that have u as the initial endpoint. In this paper we introduce the concept of semikernel modulo i by monochromatic paths of an m-coloured digraph. This concept allow us to find sufficient conditions for the existence of a kernel by monochromatic paths in an m-coloured digraph. In particular we deal with bipartite tournaments such that A⁺(z) is monochromatic for each z ∈ V(D).

Keywords

ENG
m-coloured bipartite tournaments, kernel by monochromatic paths, semikernel of D modulo i by monochromatic paths

Bibliography

  1. C. Berge, Graphs (North Holland, Amsterdam, New York, 1985).
  2. E. Boros and V. Gurvich, Perfect graphs, kernels, and cores of cooperative games, Discrete Math. 306 (2006) 2336-2354, doi: 10.1016/j.disc.2005.12.031.
  3. P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4.
  4. P. Duchet, Classical Perfect Graphs, An introduction with emphasis on triangulated and interval graphs, Ann. Discrete Math. 21 (1984) 67-96.
  5. 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.
  6. A.S. Fraenkel, Combinatorial games: selected bibliography with a succinct gourmet introduction, Elec. J. Combin. (surveys) #DS2.
  7. H. Galeana-Sánchez, On monochromatic paths and monochromatic cycles in edge coloured tournaments, Discrete Math. 156 (1996) 103-112, doi: 10.1016/0012-365X(95)00036-V.
  8. H. Galeana-Sánchez, Kernels in edge coloured digraphs, Discrete Math. 184 (1998) 87-99, doi: 10.1016/S0012-365X(97)00162-3.
  9. H. Galeana-Sánchez and J.J. García Ruvalcaba, Kernels in the clousure of coloured digraphs, Discuss. Math. Graph Theory 20 (2000) 243-354, doi: 10.7151/dmgt.1123.
  10. H. Galena-Sánchez and V. Neumann-Lara, On kernel and semikernels of digraphs, Discrete Math. 48 (1984) 67-76, doi: 10.1016/0012-365X(84)90131-6.
  11. 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.
  12. H. Galeana-Sánchez and R. Rojas-Monroy, On monochromatic paths and monochromatic 4-cycles in edge coloured bipartite tournaments, Discrete Math. 285 (2004) 313-318, doi: 10.1016/j.disc.2004.03.005.
  13. H. Galeana-Sánchez and R. Rojas-Monroy, Monochromatic paths and most 2-coloured arc sets in edge-coloured tournaments, Graphs and Combin. 21 (2005) 307-317, doi: 10.1007/s00373-005-0618-z.
  14. G. Hahn, P. Ille and R. Woodrow, Absorbing sets in arc-coloured tournaments, Discrete Math. 283 (2004) 93-99, doi: 10.1016/j.disc.2003.10.024.
  15. T.W. Haynes, T. Hedetniemi and P.J. Slater, editors, Domination in Graphs (Advanced Topics, Marcel Dekker Inc., 1998).
  16. T.W. Haynes, T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., 1998).
  17. M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combin. 60 (2001) 137-147.
  18. M. Kucharska and M. Kwaśnik, On (k,l)-kernels of superdigraphs of Pₘ and Cₘ, Discuss. Math. Graph Theory 21 (2001) 95-109, doi: 10.7151/dmgt.1135.
  19. M. KwaŚnik, The generalization of Richardson's Theorem, Discuss. Math. Graph Theory IV (1981) 11-14.
  20. M. KwaŚnik, On (k,l)-kernels of exclusive disjunction, cartesian sum and normal product of two directed graphs, Discuss. Math. Graph Theory V (1982) 29-34.
  21. S. Minggang, On monochromatic paths in m-coloured tournaments, J. Combin. Theory (B) 45 (1988) 108-111, doi: 10.1016/0095-8956(88)90059-7.
  22. M.V. Neumann-Lara, Seminúcleos de una digráfica, An. Inst. Mat. UNAM 11 (1971) 55-62.
  23. M. Richardson, Solutions of irreflexive relations, Ann. Math. 58 (1953) 573, doi: 10.2307/1969755.
  24. M. Richardson, Extensions theorems for solutions of irreflexive relations, Proc. Nat. Acad. Sci. USA 39 (1953) 649, doi: 10.1073/pnas.39.7.649.
  25. B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs, J. Combin. Theory (B) 33 (1982) 271-275, doi: 10.1016/0095-8956(82)90047-8.
  26. A. Włoch and I. Włoch, On (k,l)-kernels in generalized products, Discrete Math. 164 (1997) 295-301.
  27. I. Włoch, On imp-sets and kernels by monochromatic paths in duplication, Ars Combin. 83 (2007) 93-99.
  28. I. Włoch, On kernels by monochromatic paths in the corona of digraphs, Cent. Eur. J. Math. 6 (2008) 537-542.
Discussiones Mathematicae Graph Theory
2009/29/2
Export to PBN, Opens in new tab
Pages:
349-360
Main language of publication
English
Received
2007-11-06
Accepted
2009-03-20
Published
2009

DOI: 10.7151/dmgt.1451

Exact and natural sciences