γ-Cycles In Arc-Colored Digraphs

• Autorzy: Hortensia Galeana-Sánchez , Guadalupe Gaytán-Gómez , Rocío Rojas-Monroy
• 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

EN

digraph; kernel; kernel by monochromatic paths; γ-cycle

Kategorie tematyczne

• 05C20: Directed graphs (digraphs), tournaments

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 1
• Strony: 103-116

Daty

wydano

2016-02-01

otrzymano

2014-06-09

poprawiono

2015-05-01

zaakceptowano

2015-05-01

online

2016-01-19

Twórcy

autor

Hortensia Galeana-Sánchez

• Instituto de Matemáticas, Universidad Nacional Autónoma de México, Ciudad Universitaria, México, D.F. 04510, México

autor

Guadalupe Gaytán-Gómez

• Instituto de Matemáticas, Universidad Nacional Autónoma de México, Ciudad Universitaria, México, D.F. 04510, México

autor

Rocío Rojas-Monroy

• Facultad de Ciencias, Universidad Autónoma del Estado de México, Instituto Literario No. 100, Centro 50000, Toluca, Edo. de México, México

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]

Identyfikatory

DOI

10.7151/dmgt.1848