Discussiones Mathematicae Graph Theory 29(2) (2009) 349-360
doi: 10.7151/dmgt.1451

[BIBTex] [PDF] [PS]

MONOCHROMATIC PATHS AND MONOCHROMATIC SETS OF ARCS IN BIPARTITE TOURNAMENTS

Hortensia Galeana-Sánchez1, R. Rojas-Monroy2 and B. Zavala1

1Instituto de Matemáticas
Universidad Nacional Autónoma de México
Ciudad Universitaria, México, D.F. 04510, México

2Facultad 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: m-coloured bipartite tournaments, kernel by monochromatic paths, semikernel of D modulo i by monochromatic paths.

2000 Mathematics Subject Classification: 05C15, 05C20.

References

[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 Pm and Cm, 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.

Received 6 November 2007
Revised 20 March 2009
Accepted 20 March 2009