Kernels and cycles' subdivisions in arc-colored tournaments

Pietra Delgado-Escalante; Hortensia Galeana-Sánchez

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 1, page 101-117
  • ISSN: 2083-5892

Abstract

top
Let D be a digraph. D is said to be an m-colored digraph if the arcs of D are colored with m colors. A path P in D is called monochromatic if all of its arcs are colored alike. Let D be an m-colored digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following conditions: a) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them; and b) for every vertex x ∈ V(D)-N there is a vertex n ∈ N such that there is an xn-monochromatic directed path in D. In this paper we prove that if T is an arc-colored tournament which does not contain certain subdivisions of cycles then it possesses a kernel by monochromatic paths. These results generalize a well known sufficient condition for the existence of a kernel by monochromatic paths obtained by Shen Minggang in 1988 and another one obtained by Hahn et al. in 2004. Some open problems are proposed.

How to cite

top

Pietra Delgado-Escalante, and Hortensia Galeana-Sánchez. "Kernels and cycles' subdivisions in arc-colored tournaments." Discussiones Mathematicae Graph Theory 29.1 (2009): 101-117. <http://eudml.org/doc/270273>.

@article{PietraDelgado2009,
abstract = {Let D be a digraph. D is said to be an m-colored digraph if the arcs of D are colored with m colors. A path P in D is called monochromatic if all of its arcs are colored alike. Let D be an m-colored digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following conditions: a) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them; and b) for every vertex x ∈ V(D)-N there is a vertex n ∈ N such that there is an xn-monochromatic directed path in D. In this paper we prove that if T is an arc-colored tournament which does not contain certain subdivisions of cycles then it possesses a kernel by monochromatic paths. These results generalize a well known sufficient condition for the existence of a kernel by monochromatic paths obtained by Shen Minggang in 1988 and another one obtained by Hahn et al. in 2004. Some open problems are proposed.},
author = {Pietra Delgado-Escalante, Hortensia Galeana-Sánchez},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {kernel; kernel by monochromatic paths; tournament},
language = {eng},
number = {1},
pages = {101-117},
title = {Kernels and cycles' subdivisions in arc-colored tournaments},
url = {http://eudml.org/doc/270273},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Pietra Delgado-Escalante
AU - Hortensia Galeana-Sánchez
TI - Kernels and cycles' subdivisions in arc-colored tournaments
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 1
SP - 101
EP - 117
AB - Let D be a digraph. D is said to be an m-colored digraph if the arcs of D are colored with m colors. A path P in D is called monochromatic if all of its arcs are colored alike. Let D be an m-colored digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following conditions: a) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them; and b) for every vertex x ∈ V(D)-N there is a vertex n ∈ N such that there is an xn-monochromatic directed path in D. In this paper we prove that if T is an arc-colored tournament which does not contain certain subdivisions of cycles then it possesses a kernel by monochromatic paths. These results generalize a well known sufficient condition for the existence of a kernel by monochromatic paths obtained by Shen Minggang in 1988 and another one obtained by Hahn et al. in 2004. Some open problems are proposed.
LA - eng
KW - kernel; kernel by monochromatic paths; tournament
UR - http://eudml.org/doc/270273
ER -

References

top
  1. [1] C. Berge, Graphs (Nort-Holland, Amsterdam, third edition, 1991). 
  2. [2] C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27-31, doi: 10.1016/0012-365X(90)90346-J. Zbl0721.05027
  3. [3] E. Boros and V. Gurvich, A corrected version of the Duchet kernel conjecture, Discrete Math. 179 (1998) 231-233, doi: 10.1016/S0012-365X(97)00094-0. Zbl0886.05089
  4. [4] E. Boros and V. Gurvich, Perfect graphs, kernels and cores of cooperative games, 2003, RUTCOR Research Report, 12, Rutgers University, Dedicated to the memory of Claude Berge, New Jersey. Zbl1103.05034
  5. [5] V. Chvátal, On the computational complexity of finding a kernel, Report, CRM-300, Centre de Recherches Mathématiques, Université de Montréal (Montréal, 1973). 
  6. [6] P. Duchet, Représentations, Noyaux en Théorie des Graphes et Hypergraphes (Paris, Univ. Paris 6, 1979) 200. 
  7. [7] 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
  8. [8] A.S. Fraenkel, Planar kernel and Grundy with d ≤ 3, d o u t ≤ 2 , d i n ≤ 2 are NP-complete, Discrete Appl. Math. 3 (1981) 257-262, doi: 10.1016/0166-218X(81)90003-2. 
  9. [9] A.S. Fraenkel, Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction, The Electronic Journal of Combinatorics, 14 Dynamic Survey DS2, 2007. 
  10. [10] H. Galeana-Sánchez, On the existence of kernels and h-kernels in directed graphs, Discrete Math. 110 (1992) 251-255, doi: 10.1016/0012-365X(92)90713-P. Zbl0770.05050
  11. [11] H. Galeana-Sánchez, On monochromatic paths and monochromatic cycles in edge colored tournaments, Discrete Math. 156 (1996) 103-112, doi: 10.1016/0012-365X(95)00036-V. Zbl0857.05054
  12. [12] 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
  13. [13] 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
  14. [14] H. Galeana-Sánchez and H. Rincón-Mejía, A sufficient condition for the existence of k-kernels in digraphs, Discuss. Math. Graph Theory 18 (1998) 197-204, doi: 10.7151/dmgt.1075. Zbl0928.05032
  15. [15] H. Galeana-Sánchez and R. Rojas-Monroy, On monochromatic paths and monochromatic 4-cycles in edge-colored bipartite tournaments, Discrete Math. 285 (2004) 313-318, doi: 10.1016/j.disc.2004.03.005. Zbl1049.05042
  16. [16] H. Galeana-Sánchez and R. Rojas-Monroy, On monochromatic paths and at most 2-colored arc sets in edge colored tournaments, Graphs and Combinatorics 21 (2005) 307-317, doi: 10.1007/s00373-005-0618-z. Zbl1075.05033
  17. [17] H. Galeana-Sánchez and R. Rojas-Monroy, Kernels in edge-coloured orientations of nearly complete graphs, Discrete Math. 308 (2008) 4599-4607, doi: 10.1016/j.disc.2007.08.079. Zbl1152.05028
  18. [18] M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combin. 60 (2001) 137-147. Zbl1068.05504
  19. [19] M. Kucharska and M. Kwaśnik, On (k,l)-kernels of special superdigraphs of Pₘ and Cₘ, Discuss. Math. Graph Theory 21 (2001) 95-109, doi: 10.7151/dmgt.1135. 
  20. [20] M. Kwaśnik, The generalization of Richardson theorem, Discuss. Math. IV (1981) 11-14. Zbl0509.05048
  21. [21] M. Kwaśnik, On (k,l)-kernels of exclusive disjunction, cartesian sum and normal product of two directed graphs, Discuss. Math. V (1982) 29-34. Zbl0508.05038
  22. [22] G. Hahn, P. Ille and R.E. Woodrow, Absorbing sets in arc-coloured tournaments, Discrete Math. 283 (2004) 93-99, doi: 10.1016/j.disc.2003.10.024. Zbl1042.05049
  23. [23] J. von Neumann and O. Morgenstern, Theory of games and economic behaviour, (Princeton University Press, Princeton, 2nd edition, 1947). Zbl1241.91002
  24. [24] B. Sands, N. Sauer and R.E. Woodrow, On monochromatic paths in edge-colored digraphs, J. Combin. Theory (B) 33 (1982) 271-275, doi: 10.1016/0095-8956(82)90047-8. Zbl0488.05036
  25. [25] Shen Minggang, On monochromatic paths in m-colored tournaments, J. Combin. Theory (B) 45 (1988) 108-111, doi: 10.1016/0095-8956(88)90059-7. Zbl0654.05033
  26. [26] M. Richardson, Solutions of irreflexive relations, Annals of Mathematics 58 (1953) 573-590, doi: 10.2307/1969755. Zbl0053.02902
  27. [27] J. van Leeuwen, Having a Grundy-numbering is NP-complete, Report, 207, Computer Science Dept., Pennsylvania State University, University Park, PA, 1976. 
  28. [28] V. Neumann-Lara, Seminúcleos y núcleos, Anales del Instituto de Matemáticas UNAM 11 (1971) 55-62. 
  29. [29] A. Włoch and I. Włoch, On (k,l)-kernels in generalized products, Discrete Math. 164 (1997) 295-301, doi: 10.1016/S0012-365X(96)00064-7. 
  30. [30] I. Włoch, On imp-sets and kernels by monochromatic paths of the duplication, Ars Combin. 83 (2007) 93-100. Zbl1174.05114

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.