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