Kernels in monochromatic path digraphs

Hortensia Galeana-Sánchez; Laura Pastrana Ramírez; Hugo Alberto Rincón Mejía

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 3, page 407-417
  • ISSN: 2083-5892

Abstract

top
We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. Let D be an m-coloured digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them and (ii) for each vertex x ∈ (V(D)-N) there is a vertex y ∈ N such that there is an xy-monochromatic directed path. In this paper is defined the monochromatic path digraph of D, MP(D), and the inner m-colouration of MP(D). Also it is proved that if D is an m-coloured digraph without monochromatic directed cycles, then the number of kernels by monochromatic paths in D is equal to the number of kernels by monochromatic paths in the inner m-colouration of MP(D). A previous result is generalized.

How to cite

top

Hortensia Galeana-Sánchez, Laura Pastrana Ramírez, and Hugo Alberto Rincón Mejía. "Kernels in monochromatic path digraphs." Discussiones Mathematicae Graph Theory 25.3 (2005): 407-417. <http://eudml.org/doc/270464>.

@article{HortensiaGaleana2005,
abstract = { We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. Let D be an m-coloured digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them and (ii) for each vertex x ∈ (V(D)-N) there is a vertex y ∈ N such that there is an xy-monochromatic directed path. In this paper is defined the monochromatic path digraph of D, MP(D), and the inner m-colouration of MP(D). Also it is proved that if D is an m-coloured digraph without monochromatic directed cycles, then the number of kernels by monochromatic paths in D is equal to the number of kernels by monochromatic paths in the inner m-colouration of MP(D). A previous result is generalized. },
author = {Hortensia Galeana-Sánchez, Laura Pastrana Ramírez, Hugo Alberto Rincón Mejía},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {kernel; line digraph; kernel by monochromatic paths; monochromatic path digraph; edge-coloured digraph; line graph; edge-colored digraph},
language = {eng},
number = {3},
pages = {407-417},
title = {Kernels in monochromatic path digraphs},
url = {http://eudml.org/doc/270464},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
AU - Laura Pastrana Ramírez
AU - Hugo Alberto Rincón Mejía
TI - Kernels in monochromatic path digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 3
SP - 407
EP - 417
AB - We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. Let D be an m-coloured digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them and (ii) for each vertex x ∈ (V(D)-N) there is a vertex y ∈ N such that there is an xy-monochromatic directed path. In this paper is defined the monochromatic path digraph of D, MP(D), and the inner m-colouration of MP(D). Also it is proved that if D is an m-coloured digraph without monochromatic directed cycles, then the number of kernels by monochromatic paths in D is equal to the number of kernels by monochromatic paths in the inner m-colouration of MP(D). A previous result is generalized.
LA - eng
KW - kernel; line digraph; kernel by monochromatic paths; monochromatic path digraph; edge-coloured digraph; line graph; edge-colored digraph
UR - http://eudml.org/doc/270464
ER -

References

top
  1. [1] C. Berge, Graphs (North-Holland, Amsterdam, 1985). 
  2. [2] C. Berge and A. Ramachandra Rao, A combinatorial problem in logic, Discrete Math. 17 (1977) 23-26, doi: 10.1016/0012-365X(77)90018-8. Zbl0352.05047
  3. [3] P. Duchet, A sufficient condition for a digraph to be kernel-perfect, J. Graph Theory 11 (1987) 81-85, doi: 10.1002/jgt.3190110112. Zbl0607.05036
  4. [4] P. Duchet and H. Meyniel, Une généralization du théoréme de Richardson sur l'existence du noyaux dans les graphes orientés, Discrete Math. 43 (1983) 21-27, doi: 10.1016/0012-365X(83)90017-1. Zbl0502.05027
  5. [5] 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. Zbl0529.05024
  6. [6] H. Galeana-Sánchez, L. Pastrana Ramírez and H.A. Rincón-Mejía, Semikernels, quasikernels and Grundy functions in the line digraph, SIAM J. Disc. Math. 1 (1999) 80-83. 
  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 and Xueliang Li, Semikernels and (k,l)-kernels in digraphs, SIAM J. Discrete Math. 11 (1998) 340-346, doi: 10.1137/S0895480195291370. Zbl0907.05025
  9. [9] 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
  10. [10] H. Galeana-Sánchez and L. Pastrana Ramírez, Kernels in edge coloured line digraph, Discuss. Math. Graph Theory 18 (1998) 91-98, doi: 10.7151/dmgt.1066. 
  11. [11] H. Galeana-Sánchez and José de Jesús García-Ruvalcaba, Kernels in the closure of coloured digraphs, Discuss. Math. Graph Theory 20 (2000) 243-254, doi: 10.7151/dmgt.1123. Zbl0990.05059
  12. [12] M. Harminc, Solutions and kernels of a directed graph, Math. Slovaca 32 (1982) 263-267. Zbl0491.05029
  13. [13] J. Von Neumann and O. Morgenstern, Theory of games and economic behavior (Princeton University Press, Princeton, NJ, 1944). Zbl0063.05930
  14. [14] 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
  15. [15] 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

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.