Kernels by monochromatic paths and the color-class digraph

Hortensia Galeana-Sánchez

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 2, page 273-281
  • ISSN: 2083-5892

Abstract

top
An m-colored digraph is a digraph whose arcs are colored with m colors. A directed path is monochromatic when its arcs are colored alike. A set S ⊆ V(D) is a kernel by monochromatic paths whenever the two following conditions hold: 1. For any x,y ∈ S, x ≠ y, there is no monochromatic directed path between them. 2. For each z ∈ (V(D)-S) there exists a zS-monochromatic directed path. In this paper it is introduced the concept of color-class digraph to prove that if D is an m-colored strongly connected finite digraph such that: (i) Every closed directed walk has an even number of color changes, (ii) Every directed walk starting and ending with the same color has an even number of color changes, then D has a kernel by monochromatic paths. This result generalizes a classical result by Sands, Sauer and Woodrow which asserts that any 2-colored digraph has a kernel by monochromatic paths, in case that the digraph D be a strongly connected digraph.

How to cite

top

Hortensia Galeana-Sánchez. "Kernels by monochromatic paths and the color-class digraph." Discussiones Mathematicae Graph Theory 31.2 (2011): 273-281. <http://eudml.org/doc/271051>.

@article{HortensiaGaleana2011,
abstract = { An m-colored digraph is a digraph whose arcs are colored with m colors. A directed path is monochromatic when its arcs are colored alike. A set S ⊆ V(D) is a kernel by monochromatic paths whenever the two following conditions hold: 1. For any x,y ∈ S, x ≠ y, there is no monochromatic directed path between them. 2. For each z ∈ (V(D)-S) there exists a zS-monochromatic directed path. In this paper it is introduced the concept of color-class digraph to prove that if D is an m-colored strongly connected finite digraph such that: (i) Every closed directed walk has an even number of color changes, (ii) Every directed walk starting and ending with the same color has an even number of color changes, then D has a kernel by monochromatic paths. This result generalizes a classical result by Sands, Sauer and Woodrow which asserts that any 2-colored digraph has a kernel by monochromatic paths, in case that the digraph D be a strongly connected digraph. },
author = {Hortensia Galeana-Sánchez},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {kernel; kernel by monochromatic paths; the color-class digraph; monochromatic paths; color-class digraph},
language = {eng},
number = {2},
pages = {273-281},
title = {Kernels by monochromatic paths and the color-class digraph},
url = {http://eudml.org/doc/271051},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
TI - Kernels by monochromatic paths and the color-class digraph
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 2
SP - 273
EP - 281
AB - An m-colored digraph is a digraph whose arcs are colored with m colors. A directed path is monochromatic when its arcs are colored alike. A set S ⊆ V(D) is a kernel by monochromatic paths whenever the two following conditions hold: 1. For any x,y ∈ S, x ≠ y, there is no monochromatic directed path between them. 2. For each z ∈ (V(D)-S) there exists a zS-monochromatic directed path. In this paper it is introduced the concept of color-class digraph to prove that if D is an m-colored strongly connected finite digraph such that: (i) Every closed directed walk has an even number of color changes, (ii) Every directed walk starting and ending with the same color has an even number of color changes, then D has a kernel by monochromatic paths. This result generalizes a classical result by Sands, Sauer and Woodrow which asserts that any 2-colored digraph has a kernel by monochromatic paths, in case that the digraph D be a strongly connected digraph.
LA - eng
KW - kernel; kernel by monochromatic paths; the color-class digraph; monochromatic paths; color-class digraph
UR - http://eudml.org/doc/271051
ER -

References

top
  1. [1] J.M. Le Bars, Counterexample of the 0-1 law for fragments of existential second-order logic; an overview, Bull. Symbolic Logic 9 (2000) 67-82, doi: 10.2307/421076. Zbl0958.03022
  2. [2] J.M. Le Bars, The 0-1 law fails for frame satisfiability of propositional model logic, Proceedings of the 17th Symposium on Logic in Computer Science (2002) 225-234, doi: 10.1109/LICS.2002.1029831. 
  3. [3] C. Berge, Graphs (North-Holland, Amsterdam, 1985). 
  4. [4] 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
  5. [5] A.S. Fraenkel, Combinatorial game theory foundations applied to digraph kernels, Electronic J. Combin. 4 (2) (1997) #R10. Zbl0884.05045
  6. [6] A.S. Fraenkel, Combinatorial games: selected bibliography with a succint gourmet introduction, Electronic J. Combin. 14 (2007) #DS2. 
  7. [7] 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
  8. [8] 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
  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 R. Rojas-Monroy, A counterexample to a conjecture on edge-coloured tournaments, Discrete Math. 282 (2004) 275-276, doi: 10.1016/j.disc.2003.11.015. Zbl1042.05039
  11. [11] 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
  12. [12] G. Gutin and J. Bang-Jensen, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, London, 2001). Zbl0958.05002
  13. [13] T.W. Haynes, T. Hedetniemi and P.J. Slater, Domination in Graphs (Advanced Topics, Marcel Dekker Inc., 1998). Zbl0883.00011
  14. [14] T.W. Haynes, T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., 1998). Zbl0890.05002
  15. [15] J. von Leeuwen, Having a Grundy Numbering is NP-complete, Report 207 Computer Science Department, University Park, PA, 1976, Pennsylvania State University. 
  16. [16] 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
  17. [17] I. Włoch, On imp-sets and kernels by monochromatic paths in duplication, Ars Combin. 83 (2007) 93-99. Zbl1174.05114
  18. [18] 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.