Monochromatic paths and monochromatic sets of arcs in bipartite tournaments

Hortensia Galeana-Sánchez; R. Rojas-Monroy; B. Zavala

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 2, page 349-360
  • ISSN: 2083-5892

Abstract

top
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).

How to cite

top

Hortensia Galeana-Sánchez, R. Rojas-Monroy, and B. Zavala. "Monochromatic paths and monochromatic sets of arcs in bipartite tournaments." Discussiones Mathematicae Graph Theory 29.2 (2009): 349-360. <http://eudml.org/doc/270618>.

@article{HortensiaGaleana2009,
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). },
author = {Hortensia Galeana-Sánchez, R. Rojas-Monroy, B. Zavala},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {m-coloured bipartite tournaments; kernel by monochromatic paths; semikernel of D modulo i by monochromatic paths; -coloured bipartite tournaments; semikernel of modulo by monochromatic paths},
language = {eng},
number = {2},
pages = {349-360},
title = {Monochromatic paths and monochromatic sets of arcs in bipartite tournaments},
url = {http://eudml.org/doc/270618},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
AU - R. Rojas-Monroy
AU - B. Zavala
TI - Monochromatic paths and monochromatic sets of arcs in bipartite tournaments
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 2
SP - 349
EP - 360
AB - 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).
LA - eng
KW - m-coloured bipartite tournaments; kernel by monochromatic paths; semikernel of D modulo i by monochromatic paths; -coloured bipartite tournaments; semikernel of modulo by monochromatic paths
UR - http://eudml.org/doc/270618
ER -

References

top
  1. [1] C. Berge, Graphs (North Holland, Amsterdam, New York, 1985). 
  2. [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. Zbl1103.05034
  3. [3] P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4. Zbl0462.05033
  4. [4] P. Duchet, Classical Perfect Graphs, An introduction with emphasis on triangulated and interval graphs, Ann. Discrete Math. 21 (1984) 67-96. Zbl0558.05038
  5. [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. Zbl0456.05032
  6. [6] A.S. Fraenkel, Combinatorial games: selected bibliography with a succinct gourmet introduction, Elec. J. Combin. (surveys) #DS2. Zbl06490917
  7. [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. Zbl0857.05054
  8. [8] H. Galeana-Sánchez, Kernels in edge coloured digraphs, Discrete Math. 184 (1998) 87-99, doi: 10.1016/S0012-365X(97)00162-3. Zbl0958.05061
  9. [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. Zbl0990.05059
  10. [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. Zbl0529.05024
  11. [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. Zbl0593.05034
  12. [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. Zbl1049.05042
  13. [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. Zbl1075.05033
  14. [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. Zbl1042.05049
  15. [15] T.W. Haynes, T. Hedetniemi and P.J. Slater, editors, Domination in Graphs (Advanced Topics, Marcel Dekker Inc., 1998). Zbl0883.00011
  16. [16] T.W. Haynes, T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., 1998). Zbl0890.05002
  17. [17] M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combin. 60 (2001) 137-147. Zbl1068.05504
  18. [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. [19] M. KwaŚnik, The generalization of Richardson's Theorem, Discuss. Math. Graph Theory IV (1981) 11-14. Zbl0509.05048
  20. [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. Zbl0508.05038
  21. [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. Zbl0654.05033
  22. [22] M.V. Neumann-Lara, Seminúcleos de una digráfica, An. Inst. Mat. UNAM 11 (1971) 55-62. 
  23. [23] M. Richardson, Solutions of irreflexive relations, Ann. Math. 58 (1953) 573, doi: 10.2307/1969755. Zbl0053.02902
  24. [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. Zbl0053.02903
  25. [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. Zbl0488.05036
  26. [26] A. Włoch and I. Włoch, On (k,l)-kernels in generalized products, Discrete Math. 164 (1997) 295-301. 
  27. [27] I. Włoch, On imp-sets and kernels by monochromatic paths in duplication, Ars Combin. 83 (2007) 93-99. Zbl1174.05114
  28. [28] I. Włoch, On kernels by monochromatic paths in the corona of digraphs, Cent. Eur. J. Math. 6 (2008) 537-542. Zbl1152.05033

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.