$ \gamma $-Cycles In Arc-Colored Digraphs

Galeana-Sánchez, Hortensia ; Gaytán-Gómez, Guadalupe ; Rojas-Monroy, Rocío

Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 103-116

Résumé

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: (i) for every pair of different vertices u, v ∈ N there is no monochromatic path in D between them, and (ii) 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 γ = (u_0, u_1, . . ., u_n, u_0) such that for every i ∈0, 1, . . ., n: (i) there is a u_i u_i+1-monochromatic path, and (ii) there is no u_i+1u_i-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 = C_1 ∪ C_2 of the set of colors of D such that: (1) D[ Ĉ_i ] (the subdigraph spanned by the arcs with colors in C_i) contains no γ-cycles for i ∈1, 2; (2) If ℭ(D) contains a rainbow C_3 = (x_0, z, w, x_0) involving colors of C_1 and C_2, then (x_0, w) ∈ A(ℭ (D)) or (z, x_0) ∈ A( ℭ (D)); (3) If ℭ(D) contains a rainbow P_3 = (u, z, w, x_0) involving colors of C_1 and C_2, then at least one of the following pairs of vertices is an arc in ℭ (D): (u, w), (w, u), (x_0, u), (u, x_0), (x_0, w), (z, u), (z, x_0). 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.

Détail

Keywords: digraph, kernel, kernel by monochromatic paths, γ-cycle