PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 1 | 103-116
Tytuł artykułu

γ-Cycles In Arc-Colored Digraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We call a digraph D an m-colored digraph if the arcs of D are colored with m colors. A directed path (or a directed cycle) is called monochromatic if all of its arcs are colored alike. A subdigraph H in D is called rainbow if all of its arcs have different colors. A set N ⊆ V (D) is said to be a kernel by monochromatic paths of D if it satisfies the two following conditions: for every pair of different vertices u, v ∈ N there is no monochromatic path in D between them, and for every vertex x ∈ V (D) − N there is a vertex y ∈ N such that there is an xy-monochromatic path in D. A γ-cycle in D is a sequence of different vertices γ = (u0, u1, . . . , un, u0) such that for every i ∈ {0, 1, . . . , n}: there is a uiui+1-monochromatic path, and there is no ui+1ui-monochromatic path. The addition over the indices of the vertices of γ is taken modulo (n + 1). If D is an m-colored digraph, then the closure of D, denoted by ℭ(D), is the m-colored multidigraph defined as follows: V (ℭ (D)) = V (D), A(ℭ (D)) = A(D) ∪ {(u, v) with color i | there exists a uv-monochromatic path colored i contained in D}. In this work, we prove the following result. Let D be a finite m-colored digraph which satisfies that there is a partition C = C1 ∪ C2 of the set of colors of D such that: D[Ĉi] (the subdigraph spanned by the arcs with colors in Ci) contains no γ-cycles for i ∈ {1, 2}; If ℭ (D) contains a rainbow C3 = (x0, z, w, x0) involving colors of C1 and C2, then (x0, w) ∈ A(ℭ (D)) or (z, x0) ∈ A(ℭ (D)); If ℭ (D) contains a rainbow P3 = (u, z, w, x0) involving colors of C1 and C2, then at least one of the following pairs of vertices is an arc in ℭ (D): (u, w), (w, u), (x0, u), (u, x0), (x0, w), (z, u), (z, x0). Then D has a kernel by monochromatic paths. This theorem can be applied to all those digraphs that contain no γ-cycles. Generalizations of many previous results are obtained as a direct consequence of this theorem.
Słowa kluczowe
Wydawca
Rocznik
Tom
36
Numer
1
Strony
103-116
Opis fizyczny
Daty
wydano
2016-02-01
otrzymano
2014-06-09
poprawiono
2015-05-01
zaakceptowano
2015-05-01
online
2016-01-19
Twórcy
  • Instituto de Matemáticas, Universidad Nacional Autónoma de México, Ciudad Universitaria, México, D.F. 04510, México, hgaleana@matem.unam.mx
  • Instituto de Matemáticas, Universidad Nacional Autónoma de México, Ciudad Universitaria, México, D.F. 04510, México, ggg_19808@hotmail.comand
  • Facultad de Ciencias, Universidad Autónoma del Estado de México, Instituto Literario No. 100, Centro 50000, Toluca, Edo. de México, México, mrrm@uaemex.mx
Bibliografia
  • [1] C. Berge, Graphs (North-Holland, Amsterdam, 1985).
  • [2] P. Duchet, Graphes Noyau-Parfaits, Ann. Discrete Math. 9 (1980) 93–101. doi:10.1016/S0167-5060(08)70041-4[Crossref]
  • [3] P. Duchet, Classical perfect graphs: An introduction with emphasis on triangulated and interval graphs, Ann. Discrete Math. 21 (1984) 67–96.
  • [4] 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[Crossref]
  • [5] H. Galeana-Sánchez, On monochromatic paths and monochromatics cycles in edge colored tournaments, Discrete Math. 156 (1996) 103–112. doi:10.1016/0012-365X(95)00036-V[Crossref]
  • [6] H. Galeana-Sánchez, Kernels in edge-coloured digraphs, Discrete Math. 184 (1998) 87–99. doi:10.1016/S0012-365X(97)00162-3[Crossref][WoS]
  • [7] H. Galeana-Sánchez and J.J. García-Ruvalcaba, Kernels in the closure of coloured digraphs, Discuss. Math. Graph Theory 20 (2000) 243–254. doi:10.7151/dmgt.1123[Crossref]
  • [8] H. Galeana-Sánchez, G. Gaytán-Gómez and R. Rojas-Monroy, Monochromatic cycles and monochromatic paths in arc-colored digraphs, Discuss. Math. Graph Theory 31 (2011) 283–292. doi:10.7151/dmgt.1545[Crossref][WoS]
  • [9] 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[Crossref]
  • [10] 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[Crossref]
  • [11] 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[Crossref]
  • [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[Crossref]
  • [13] H. Galeana-Sánchez and R. Rojas-Monroy, Monochromatic paths and at most 2-coloured arc sets in edge-coloured tournaments, Graphs Combin. 21 (2005) 307–317. doi:10.1007/s00373-005-0618-z[Crossref]
  • [14] H. Galeana-Sánchez and R. Rojas-Monroy, Monochromatic paths and quasi-monochromatic cycles in edge-coloured bipartite tournaments, Discuss. Math. Graph Theory 28 (2008) 285–306. doi:10.7151/dmgt.1406[Crossref]
  • [15] H. Galeana-Sánchez and R. Rojas-Monroy, Independent domination by monochromatic paths in arc coloured bipartite tournaments, AKCE Int. J. Graphs Comb. 6 (2009) 267–285.
  • [16] H. Galeana-Sánchez, R. Rojas-Monroy and B. Zavala, Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs, Discuss. Math. Graph Theory 29 (2009) 337–347. doi:10.7151/dmgt.1450[Crossref]
  • [17] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944).
  • [18] M. Richardson, Solutions of irreflexive relations, Ann. of Math. 58 (1953) 573–590. doi:10.2307/1969755[Crossref]
  • [19] M. Richardson, Extension theorems for solutions of irreflexive relations, Proc. Natl. Acad. Sci. USA 39 (1953) 649–655. doi:10.1073/pnas.39.7.649[Crossref]
  • [20] R. Rojas-Monroy and J.I. Villarreal-Valdés, Kernels in infinite diraphs, AKCE Int. J. Graphs Comb. 7 (2010) 103–111.
  • [21] Shen Minggang, On monochromatic paths in m-coloured tournaments, J. Combin. Theory Ser. B 45 (1988) 108–111. doi:10.1016/0095-8956(88)90059-7[Crossref]
  • [22] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths edge-coloured digraphs, J. Combin. Theory Ser. B 33 (1982) 271–275. doi:10.1016/0095-8956(82)90047-8[Crossref]
  • [23] I. Włoch, On imp-sets and kernels by monochromatic paths of the duplication, Ars Combin. 83 (2007) 93–99.
  • [24] I. Włoch, On kernels by monochromatic paths in the corona of digraphs, Cent. Eur. J. Math. 6 (2008) 537–542. doi:10.2478/s11533-008-0044-6[Crossref][WoS]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1848
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.