H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs

Campero-Alonzo, José Manuel ; Sánchez-López, Rocío

Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 391-408.

Résumé

Let H be a digraph (possibly with loops) and D a digraph without loops whose arcs are colored with the vertices of H (D is said to be an H-colored digraph). For an arc (x, y) of D, its color is denoted by c(x, y). A directed path W = (v_0, . . ., v_n) in an H-colored digraph D will be called H-path if and only if (c(v_0, v_1), . . ., c(v_n−1, v_n)) is a directed walk in H. In W, we will say that there is an obstruction on v_i if (c(v_i−1, v_i), c(v_i, v_i+1)) ∉ A(H) (if v_0 = v_n we will take indices modulo n). A subset N of V(D) is said to be an H-kernel in D if for every pair of different vertices in N there is no H-path between them, and for every vertex u in V(D) \ N there exists an H-path in D from u to N. Let D be an arc-colored digraph. The color-class digraph of D,𝒞_C(D), is the digraph such that V(𝒞_C(D)) = {c(a) : a ∈ A(D)} and (i, j) ∈ A(𝒞_C(D)) if and only if there exist two arcs, namely (u, v) and (v, w) in D, such that c(u, v) = i and c(v, w) = j. The main result establishes that if D = D_1 ∪ D_2 is an H-colored digraph which is a union of asymmetric quasi-transitive digraphs and {V_1, . . ., V_k} is a partition of V(𝒞_C(D)) with a property P^∗ such that 1. V_i is a quasi-transitive V_i-class for every i in {1, . . ., k}, 2. either D[{a ∈ A(D) : c(a) ∈ V_i}] is a subdigraph of D_1 or it is a sudigraph of D_2 for every i in {1, . . ., k}, 3. D_i has no infinite outward path for every i in {1, 2}, 4. every cycle of length three in D has at most two obstructions, then D has an H-kernel. Some results with respect to the existence of kernels by monochromatic paths in finite digraphs will be deduced from the main result.

Détail

Keywords: quasi-transitive digraph, kernel by monochromatic paths, alternating kernel, obstruction, H-kernel

Bibliographie

[1] P. Arpin and V. Linek, Reachability problems in edge-colored digraphs, Discrete Math. 307 (2007) 2276–2289. doi:10.1016/j.disc.2006.09.042

[2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2009). doi:10.1007/978-1-84800-998-1

[3] Y. Bai, S. Fujita and S. Zhang, Kernels by properly colored paths in arc-colored digraphs, Discrete Math. 341 (2018) 1523–1533. doi:10.1016/j.disc.2018.02.014

[4] C. Berge, Graphs (North-Holland, Amsterdan, 1989).

[5] 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

[6] P. Delgado-Escalante and H. Galeana-Sánchez, Restricted domination in arc-colored digraphs, AKCE Int. J. Graphs Comb. 11 (2014) 95–104.

[7] P. Delgado-Escalante, H. Galeana-Sánchez and E. O’Reilly-Regueiro, Alternating kernels, Discrete Appl. Math. 236 (2018) 153–164. doi:10.1016/j.dam.2017.10.013

[8] H. Galeana-Sánchez, Kernels by monochromatic paths and the color-class digraph, Discuss. Math. Graph Theory 31 (2011) 273–281. doi:10.7151/dmgt.1544

[9] 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

[10] H. Galeana-Sánchez and R. Rojas-Monroy, Kernels in quasi-transitive digraphs, Discrete Math. 306 (2006) 1969–1974. doi:10.1016/j.disc.2006.02.015

[11] H. Galeana-Sánchez, B. Llano and J.J. Montellano-Ballesteros, Kernels by monochromatic paths in m-colored unions of quasi-transitive digraphs, Discrete Appl. Math. 158 (2010) 461–466. doi:10.1016/j.dam.2009.11.005

[12] A. Ghouilá-Houri, Caractérisation des graphes non orientés dont on peut orienter les arêtes de manière à obtenir le graphe d’une relation d’ordre, C. R. Math. Acad. Sci. Paris 254 (1962) 1370–1371.

[13] V. Linek and B. Sands, A note on paths in edge-colored tournaments, Ars Combin. 44 (1996) 225–228.

[14] K.B. Reid, Monotone reachability in arc-colored tournaments, Congr. Numer. 146 (2000) 131–141.

[15] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs, J. Combin. Theory Ser. B 33 (1982) 271–275. doi:10.1016/0095-8956(82)90047-8