(H, k)-reachability in H-arc-colored digraphs

Abstract

Let H be a digraph possibly with loops, D be a digraph, and k be an integer, $k\ge 3$. An H-coloring $\zeta$ is a map $\zeta : A(D)\rightarrow V(H)$. An (H, k)-walk W in D is a walk $W = (x_0,\dots , x_n)$ with length at most k such that $(\zeta (x_0, x_1), \dots , \zeta (x_{n-1}, x_n))$ is a walk in H. An (H, k)-path in D is an (H, k)-walk which is a path in D. In this work, we introduce the reachability by (H, k)-paths as follows, for $u, v\in V(D)$, we say that u reaches v by (H, k)-paths if there exists an (H, k)-path from u to v in D. Naturally, this new reachability concept can be used to model several connectivity problems. We focus on one of the many aspects of the reachability by (H, k)-paths, the (H, k)-kernels. A subset N of V(D) is an (H, k)-kernel if N is an (H, k)-independent (a subset S of V(D) such that no vertex in S can reach another (different) vertex in S by $(H,k-1)$-paths) and $(H,k-1)$-absorbent (a subset S of V(D) such that every vertex in $V(D)-S$ reaches some vertex in S by $(H,k-1)$-paths). A digraph D is (H, k)-path-quasi-transitive, if for every three vertices x, y and w of D such that there are an (H, k)-path from x to y and an (H, k)-path from y to w in D, then there is an (H, k)-path from x to w or an (H, k)-path from w to x in D. We give sufficient conditions for a $(H,k-1)$-path-quasi-transitive digraph that has an (H, k)-kernel. As a main result, we give sufficient conditions for a partition $\xi$ of V(H) such that the arc set colored with the colors for every part of $\xi$ induces an $(H,k-1)$-path-quasi-transitive digraph in D, to imply the existence of an (H, k)-kernel in D. This result generalizes the results of Casas-Bautista et al. (2015), and Hernández-Lorenzana and Sánchez-López (2022). Finally, we show two applications of (H, k)-kernels.

1 Introduction

Undoubtedly, connectivity is a central topic both theoretically and in graph theory applications. In this paper, we present a new concept of reachability, which allows modeling a wide variety of connectivity problems in a natural way.

In this work, we will consider digraphs without multiple arcs and loops. For general concepts, we refer the reader to [2, 3]. For a nonempty subset F of A(D), the subdigraph of D induced by F, denoted by D[F], is the digraph where V(D[F]) is the set of vertices in V(D) which are incident with at least one arc from F, and $A(D[F])=F$.

A k-path (k-cycle) is a path (cycle) of length k. The path (cycle) with n vertices will be denoted by $\overrightarrow{P}_{n}$ ($\overrightarrow{C}_n$). If $W=(v_0, v_1,\ldots , v_n)$ is a walk, then $(v_i,W,v_j)$ will denote the walk $(v_i,v_{i+1},\ldots ,v_j)$ contained in W. Let $W_1$ be a walk from u to v and $W_2$ be a walk from v to w, the union or the concatenation of $W_1$ with $W_2$ will be denoted by $W_1\cup W_2$. A sink of a digraph D is a vertex with out-degree zero.

A subset I of V(D) is independent if $A(D[I]) = \emptyset$. A kernel N of D is an independent set of vertices which is absorbent, that is, for each $x\in V (D)-N$ there is $y\in N$ such that $(x,y)\in A(D)$. The concept of kernel has its origins in game theory [21]. The problem of verifying whether a given digraph has a kernel is NP-complete [7]. Furthermore, the kernel problem remains NP-complete when the underlying graph is 3-colorable [16]. A subset S of V(D) is a semikernel of D if S is independent, and for every vertex y in $V(D)-S$, if there is $x\in S$ such that $(x,y)\in A(D)$, then there exists a vertex $w\in S$ such that $(y,w)\in A(D)$. In [12], Galeana-Sánchez and Neumann-Lara, using the notion of semikernel, gave suficient conditions for a digraph to be a kernel-perfect¹ digraph.

A digraph is called quasi-transitive if whenever $(u, v)\in A(D)$ and $(v, w)\in A(D)$, then $(u, w)\in A(D)$ or $(w, u)\in A(D)$. The properties of quasi-transitive digraphs have been studied by several authors. In [11], there is an excellent compendium dedicated to quasi-transitive digraphs and their extensions. On the other hand, in [9], Meyniel observed that if D is a digraph such that every 3-cycle has at least two symmetrical arcs, then each complete subdigraph of D has a kernel. Hence, in [13] Galeana-Sánchez and Rojas-Monroy concluded the following result.

Theorem 1

[13] If D is a quasi-transitive digraph such that every 3-cycle of D has at least two symmetrical arcs, then D is a kernel-perfect digraph.

In [19], Kwaśnik and Borowiecki introduced the concept of (k, l)-kernel. This concept generalizes the independence distance at least 1, and absorption distance at most 1 of a kernel, in the following way. Let D be a digraph. A subset S of V(D) is k-independent if there is no path of length strictly less than k from u to v for every pair of distinct vertices $u, v\in S$, and we call S an l-absorbent set if for every $x\in V(D)-S$, there is $y\in S$ such that there exists a path of length less than or equal to l from x to y in D. A (k, l)-kernel of D is a subset N of V(D) that is k-independent and l-absorbent. A k-kernel is a $(k,k-1)$-kernel, and thus a 2-kernel is a kernel. In [17], Galeana-Sánchez and Hernández-Cruz introduced the family of k-path-transitive digraphs, as the digraphs such that whenever there are paths of length less than or equal to k from u to v and from v to w, then there exists a path of length less than or equal to k from u to w. With the help of this family, they proved that if D is a k-transitive digraph, then D has an n-kernel for every $n\ge k\ge 2$, where D is a k-transitive if whenever $(x_0, x_1,\ldots , x_k)$ is a path of length k in D, then $(x_0, x_k)\in A(D)$.

Some generalizations of transitive digraphs are the quasi-transitive, right-pretransitive and left-pretransitive digraphs². Galeana-Sánchez and Hernández-Cruz proved that if D is a right-pretransitive digraph such that every directed triangle of D is symmetrical, then D has a k-kernel for every integer $k\ge 3$, the result is also valid for strong digraphs in the left-pretransitive case [10]. Also, an alternative proof of the fact that every quasi-transitive digraph has a (k, l)-kernel for every integers $k > l\ge 3$ or $k = 3$ and $l = 2$ is showed. In [15], a generalization of the classical result that states that if every directed cycle in a digraph D has at least one symmetrical arc, then D has a kernel, due to Duchet [8], is conjetured for k-kernels and it is proved to be true for $k = 3$ and $k = 4$.

Let H be a digraph, possibly with loops, and D be an irreflexive digraph. An H-arc-coloring, or just an H-coloring, $\zeta$, is a map $\zeta : A(D)\rightarrow V(H)$. These types of colorings were proposed by Linek and Sands with the idea that the arcs of H could be used to codify permitted color changes in the walks of D to define a reachability [20]. A walk $W = (x_0,\dots , x_n)$ in D is an H-walk if $(\zeta (x_0, x_1), \dots , \zeta (x_{n-1}, x_n))$ is a walk in H. An H-path in D is an H-walk which is a path in D. Notice that an H-path in D is a path whose sequence of colors induces a walk in H, not a path. For $u,v \in V(D)$, we say that u reaches v by H-paths if there exists an H-path from u to v in D. Naturally, with this notion of reachability we define independence by H-paths and absorbance by H-paths, as follows. A subset S of V(D) is independent by H-paths, or H-independent, if no vertex in S can reach by H-paths another vertex in S, and it is absorbent by H-paths, or H-absorbent, if every vertex in $V(D) - S$ can reach by H-paths some vertex in S. A kernel by H-paths, or H-kernel, is a subset N of V(D) that is both H-independent and H-absorbent.

Observe that an H-walk does not necessarily contain an H-path; hence, the notions of independence by H-walks and absorbence by H-walks can be analogously defined. A deeper study of the differences and similarities of these types of reachability can be found in [4].

Notice that if the only arcs of H are loops, then the only possible H-paths are the paths in which all of the arcs are colored alike. This is known as the monochromatic case, which has been widely studied. In particular, Sands, Sauer and Woodrow proved that every digraph whose arc set is colored with two colors has a kernel by monochromatic paths [22].

Let D be an arc-colored digraph. The color-class digraph of D, ${\mathscr {C}}_C(D)$ has vertex set the colors represented in the arcs of D,  and (i, j) is an arc of ${\mathscr {C}}_C(D)$ if and only if there are two arcs in D, say (u, v) and (v, w), such that (u, v) is colored with i and (v, w) is colored with j.

Consider a partition of V(H). In [6, 14] and in [5, 18], sufficient conditions for the arc set colored with colors for every part, to guarantee the existence of a kernel by monochromatic paths and an H-kernel, respectively, are given. We will show that the main result of this work has as a consequence the results in [6] and [18].

The reachability by (H, k)-paths concept arises from combining the concepts of reachability by H-paths and reachability by k-paths, which are of great interest by themselves, both theoretically and for their applications. Therefore, the new reachability concept naturally opens the doors to new theoretical possibilities as well as to model problems, in particular connectivity problems.

The rest of the paper is organized as follows. In Sect. 2, we introduce the concept of reachability by (H, k)-paths, and with it the concept of (H, k)-kernel and present some of their properties. In Sect. 3 we give some definitions and prove some technical results that are helpful for the main result proof. In Sect. 4 the main result is proved, and in Sect. 5 we prove some of its consequences. Finally, in Sect. 6 we propose some applications of this new concept of reachability.

2 (H, k)-kernels

In this section, we present a new concept of reachability, which incorporates the idea of reachability by k-paths in H-arc-colored digraphs.

Let H be a digraph possibly with loops, D be a loopless H-arc-colored digraph and $k\ge 2$. For $u, v\in V(D)$, we say that u reaches v by (H, k)-paths if there exists an H-path, with length at most k, from u to v in D. A subset $S \subseteq V(D)$ is (H, l)-absorbent by paths, or (H, l)-absorbent, of D if every vertex in $V_D-S$ reaches some vertex in S by (H, l)-paths, and it is (H, k)-independent by paths, or (H, k)-independent, if there is no H-path of length strictly less than k from u to v for every pair of distinct vertices $u,v\in S$, that is, no vertex in S can reach another (different) vertex in S by $(H,k-1)$-paths. An (H, k, l)-kernel by paths, or just (H, k, l)-kernel, is a subset of V(D) which is (H, k)-independent by paths and (H, l)-absorbent by paths. An (H, k)-kernel by paths, or (H, k)-kernel, is an $(H,k,k-1)$-kernel by paths.

It is important to note that, if $k=2$, then, for any H, an (H, k)-kernel is a kernel, which has been extensively studied. Therefore, we will focus on the case $k\ge 3$. From now on, H is a digraph possibly with loops, D is a loopless H-arc-colored digraph and $k\ge 3$.

Note that, by definition, if $k\ge k'$, then every $(H,k')$-path is an (H, k)-path. Hence, we have the following proposition.

Proposition 2

Let H be a digraph, possibly with loops, D an H-arc-colored digraph, and $k\ge k'$. The following properties hold.

• 1. If S is (H, k)-independent in D, then S is $(H,k')$-independent in D.

• 2. If S is $(H,k')$-absorbent in D, then S is (H, k)-absorbent in D.

Clearly, if a vertex u reaches v by (H, k)-paths, then u reaches v by H-paths, but not necessarily if a vertex u reaches v by H-paths, then u reaches v by (H, k)-paths. Furthermore, to show that this new reachability concept is different from reachability by H-paths, for every $k\ge 3$, we provide an example of a digraph H, and an H-arc-colored digraph $D_k$ such that $D_k$ has an (H, k)-kernel, but $D_k$ has no H-kernel, see Fig. 1, and we provide a digraph H, and an H-arc-colored digraph $D'_k$ such that $D'_k$ has an H-kernel, but $D'_k$ has no (H, k)-kernel, see Fig.  2.

Fig. 1

$D_4$ has no $\overset{\leftrightarrow }{P}_3$-kernel and $\{ z,x_{00},x_{10},x_{20}\}$ is a $(\overset{\leftrightarrow }{P}_3,4)$-kernel of $D_4$

Proposition 3

Let $k\ge 3$ and $\overleftrightarrow {P}_3$ be the reflexive, symmetrical path with three vertices. There is a $\overleftrightarrow {P}_3$-arc-colored digraph $D_k$ such that $D_k$ has a $(\overleftrightarrow {P}_3,k)$-kernel, but $D_k$ has no $\overleftrightarrow {P}_3$-kernel.

Proof

Consider $\overleftrightarrow {P}_3$ such that $V(\overleftrightarrow {P}_3)=\{ g,r,b\}$ and $A(\overleftrightarrow {P}_3)= (V(\overleftrightarrow {P}_3)\times V(\overleftrightarrow {P}_3))-\{ (b,g),(g,b)\}$. Let

$$\begin{aligned} V(D_k)= & {} \{ x_{ij}:\ i\in \mathbb {Z}_3, \ j\in \mathbb {Z}_k\} \cup \{ z\},\\ G= & {} \{ (x_{i0},x_{i1}):\ i\in \mathbb {Z}_3\},\\ B_1= & {} \{ (x_{i(k-1)},x_{(i+1)0}):\ i\in \mathbb {Z}_3\},\\ B_2= & {} \{ (x_{i1},z):\ i\in \mathbb {Z}_3\},\\ R_1= & {} \{ (x_{ij},x_{i(j+1)}):\ i\in \mathbb {Z}_3\text { and }j\in \{ 1,\ldots ,k-2\} \},\\ R_2= & {} \{ (x_{ij},x_{i(j-1)}):\ i\in \mathbb {Z}_3\text { and }j\in \{ 2,\ldots ,k-1\} \}, and \\ A(D_k)= & {} G\cup B_1\cup B_2\cup R_1\cup R_2. \end{aligned}$$

Color the arcs of $D_k$ as follows: the arcs in G with color g, the arcs in $B_1\cup B_2$ with color b and the arcs of $R_1\cup R_2$ with color r.

Claim 1

$D_k$ has a $(\overleftrightarrow {P}_3,k)$-kernel.

Consider $N=\{ z,x_{00},x_{10},x_{20}\}$. We will prove that N is a $(\overleftrightarrow {P}_3,k)$-kernel of $D_k$. Since z is a sink of $D_k,$ there is no $(\overleftrightarrow {P}_3,k)$-path from z to any other vertex of N. By definition, for each $i\in \mathbb {Z}_3$, the only path from $x_{i0}$ to z with length less than k is $(x_{i0},x_{i1},z)$, but (g, b) is not an arc of $\overleftrightarrow {P}_3$. Thus, there is no $(\overleftrightarrow {P}_3,k-1)$-path from $x_{i0}$ to z. Consider $x_{i0}$ and $x_{j0}$, with $i,j\in \mathbb {Z}_3$. Note that $j=i+1$ or $j=i-1$, and suppose without loss of generality that $j=i+1$. By definition of $D_k$, the only path from $x_{i0}$ to $x_{(i+1)0}$ is $(x_{i0},x_{i1},\ldots ,x_{i(k-1)},x_{(i+1)0})$ and its length is k. Hence, there is no $(\overleftrightarrow {P}_3,k-1)$-path from $x_{i0}$ to $x_{(i+1)0}$ in $D_k$. Therefore, N is $(\overleftrightarrow {P}_3,k)$-independent in $D_k$. On the other hand, for every $x_{ij}\in V(D_k)-N$, $(x_{ij},x_{i(j+1)}, \ldots ,x_{i(k-1)},x_{(i+1)0})$ is a $(\overleftrightarrow {P}_3,k-1)$-path from $x_{ij}$ to $x_{(i+1)0}$. Thus, N is $(\overleftrightarrow {P}_3,k-1)$-absorbent and therefore, N is a $(\overleftrightarrow {P}_3,k)$-kernel.

Claim 2

$D_k$ has no $\overleftrightarrow {P}_3$-kernel.

Fig. 2

$D'_3$ has no $(\overset{\rightarrow }{C}_3,3)$-kernel and $\{x_0\}$ is a $\overset{\rightarrow }{C}_3$-kernel of $D'_3$

Note that z must belong to any $\overleftrightarrow {P}_3$-kernel of $D_k$. Moreover, for every $i\in \mathbb {Z}_3$ and $j\in \{ 1,\ldots ,k-1\}$, $(x_{ij},x_{i(j-1)},\ldots ,x_{i1},z)$ is a $\overleftrightarrow {P}_3$-path of $D_k$, it follows that $x_{ij}$ is not in any $\overleftrightarrow {P}_3$-kernel of $D_k$. On the other hand, since (g, b) and (b, g) are not arcs of $\overleftrightarrow {P}_3$, then there is no $\overleftrightarrow {P}_3$-path from $x_{i0}$ to z, with $i\in \mathbb {Z}_3$. From above, a $\overleftrightarrow {P}_3$-kernel cannot be completed. Therefore, there is no $\overleftrightarrow {P}_3$-kernel in $D_k$. $\square$

Proposition 4

Let $k\ge 3$ and $\overrightarrow{C}_k$ be the reflexive, asymmetrical cycle with k vertices. There is a $\overrightarrow{C}_k$-arc-colored digraph $D'_k$ such that $D'_k$ has a $\overrightarrow{C}_k$-kernel, but $D'_k$ has no $(\overrightarrow{C}_k,k)$-kernel.

Proof

Consider $V(\overrightarrow{C}_k)=\{ 0,1,\ldots , k-1\}$ and $A(\overrightarrow{C}_k)= \{ (i,i):\ i\in \mathbb {Z}_k\}\cup \{ (i,i+1):\ i\in \mathbb {Z}_k\}$. Let $V(D'_k)=\{ x_i:\ i\in \mathbb {Z}_{k+1}\}$, and $A(D'_k)=\{ (x_i,x_{i+1}):\ i\in \mathbb {Z}_{k+1}\}$. Color the arcs of $D'_k$ as follows: for each $i\in \{ 0, 1,\ldots , k \}$ color the arc $(x_i,x_{i+1})$ with color i, and color the arc $(x_{k},x_{0})$ with color 0.

Claim 1

$D'_k$ has a $\overrightarrow{C}_k$-kernel.

Consider $N=\{ x_0\}$. We will prove that N is a $\overrightarrow{C}_k$-kernel of $D'_k$. Clearly, N is $\overrightarrow{C}_k$-independent. Moreover, $(x_{1},x_2,\ldots ,x_{k-1},x_{k},x_0)$ is a spanning $\overrightarrow{C}_k$-path which ends in $x_0$; thus, N is $\overrightarrow{C}_k$-absorbent, and therefore N is an $\overrightarrow{C}_k$-kernel of $D'_k$.

Claim 2

$D'_k$ has no $(\overrightarrow{C}_k,k)$-kernel.

Observe that $D'_k$ is an $(k+1)$-cycle; even more, every path of $D'_k$ is a $\overrightarrow{C}_k$-path. It follows that every $(\overrightarrow{C}_k,k)$-independent set of $D'_k$ has only one vertex; this implies that every $(\overrightarrow{C}_k,k)$-kernel has only one vertex. Note that $(x_{i+1},x_{i+2},\ldots ,x_k,x_0,x_1,\ldots ,x_i)$ is the only path from $x_{i+1}$ to $x_i$ in $D'_k,$ but it is not a $(\overrightarrow{C}_k,k-1)$-path because its length is k. Therefore, $D'_k$ has no $(\overrightarrow{C}_k,k)$-kernel. $\square$

By Propositions 3 and 4, we can conclude that the concept of (H, k)-kernel by paths is indeed different from that of H-kernel and, in particular, their associated decision problems are also different.

Nonetheless, the similarities between these concepts allow us to obtain the following result.

Proposition 5

Let H be a digraph, possibly with loops, and D an H-arc-colored digraph. If $k-1\ge diam (D)$, then N is an H-kernel of D if and only if N is an (H, k)-kernel on D.

Proof

Let k such that $k-1\ge diam (D)$. Observe that every $(H,k-1)$-path is an H-path. Even more, since $diam(D)\le k-1$, it follows that every H-path is an $(H,k-1)$-path in D. We can conclude the desired result. $\square$

The next definition generalizes (in the context of H-arc-colored digraphs) the definition of k-path-transitive digraphs. We say that D is (H, k)-path-quasi-transitive digraph if for every three vertices x, y and w of D such that there are (H, k)-paths from x to y and from y to w in D, then there is an (H, k)-path from x to w or an (H, k)-path from w to x in D.

In the literature, different types of digraphs associated with the digraph to be studied have been used, to obtain different types of information. Naturally, for an H-arc-colored digraph D, it is common to use the reachability digraph of D, as in [1]. We define the $(H,k-1)$-closure of D, as the digraph $R_{(H,k-1)}(D)$ such that $V(R_{(H,k-1)}(D))=V(D)$ and $A(R_{(H,k-1)}(D))=\{ (x,y):\ \text {there is an }(H,k-1)\text {-path from }x\text { to }y\}$. Thus, an H-arc-colored digraph D has an (H, k)-kernel if and only if $R_{(H,k-1)}(D)$ has a kernel.

Lemma 6

If D is an $(H,k-1)$-path-quasi-transitive digraph, then $R_{(H,k-1)}(D)$ is a quasi-transitive digraph.

With the previous result, we proved the following theorem, which is a generalization of Theorem 1, in the context of H-arc-colored digraphs.

Theorem 7

Let D be an $(H,k-1)$-path-quasi-transitive digraph such that for every three vertices x, y and w of D, whenever there are $(H,k-1)$-paths from x to y, from y to w and from w to x in D, two of the following three assertions hold:

• 1. There is an $(H,k-1)$-path from y to x in D.

• 2. There is an $(H,k-1)$-path from w to y in D.

• 3. There is an $(H,k-1)$-path from x to w in D.

Then, D has an (H, k)-kernel.

The proof of Theorem 7 follows from the definitions of the $(H,k-1)$-path-quasi-transitive digraph and the $(H,k-1)$-closure of a digraph, as well as applying Lemma  6 and Theorem 1.

3 Auxiliary results

In this section, we present auxiliary lemmas and definitions which will be useful in the proof of our main result.

From now on, H is a digraph possibly with loops, D is a loopless H-arc-colored digraph, with H-coloring $\zeta$ and $\xi =\{C_1, C_2,\ldots , C_t\}$ $(t\ge 2)$ is a partition of V(H) such that $\{a\in A(D):\ \zeta (a)\in C_i\}\ne \emptyset$ and $G_i=D[\{ a\in A(D):\ \zeta (a)\in C_i\} ]$ is an $(H,k-1)$-path-quasi-transitive subdigraph of D, for every $i\in \{ 1, 2,\ldots ,t\}$. Notice that $\{\{ a\in A(D):\ \zeta (a)\in C_i\}:\ i\in \{1, 2,\ldots ,t\}$ is a partition of A(D).

Let $W=(v_0, v_1,\ldots , v_n)$ be a walk in D, we say that $v_i$ is an H-obstruction to W if $(\zeta (v_{i-1},v_i),\zeta (v_i,v_{i+1})) \notin A(H)$ (if $v_0 = v_n$ we take subscripts mod n).

Let H be a digraph possibly with loops, D be an H-arc-colored digraph and S be a subset of V(D). We say that S is an (H, k)-semikernel of D if and only if S is semikernel of $R_{(H,k-1)}(D)$.

In [13], Galeana-Sánchez and Rojas-Monroy worked with quasi-transitive subdigraphs such that every 3-cycle has at least two symmetric arcs, to guarantee the existence of a kernel. In particular, Lemmas 2.1 and 2.2 of [13] describe some properties of quasi-transitive digraphs. With these Lemmas, the definition of the $(H,k-1)$-closure and the Lemma  6, the proof of Lemma 8 is immediate.

Lemma 8

Let H be a digraph, possibly with loops, and D be an H-arc-colored digraph such that every 3-cycle of $R_{(H,k-1)}(G_r)$ has at least two symmetrical arcs, for every $r\in \{ 1,\ldots ,t\}$. The following assertions hold.

• 1. If $(x_0, x_1,\ldots , x_{n})$ is an asymmetrical path, $n\ge 1$, in $R_{(H,k-1)}(G_r)$, then $(x_0,x_s)$ is an arc of $R_{(H,k-1)}(G_r)$ and there is no arc from $x_{s}$ to $x_0$ in $R_{(H,k-1)}(G_r)$, for each $s\in \{ 1,\ldots ,n\}$.

• 2. There is no asymmetrical cycle in $R_{(H,k-1)}(G_r)$, for every $r\in \{ 1,\ldots ,t\}$.

• 3. There is no sequence of vertices $(x_0, x_1,\ldots )$ such that $(x_i,x_{i+1})$ is an arc of $R_{(H,k-1)}(G_r)$ and there is no arc from $x_{i+1}$ to $x_i$ in $R_{(H,k-1)}(G_r)$, for every $i \in \{ 0,1,\ldots \}$.

• 4. There exists $x\in V(G_r)$ such that $\{x\}$ is an (H, k)-semikernel of $G_r$, for every $r\in \{ 1,\ldots ,t\}$.

Let H be a digraph, possibly with loops, and D be an H-arc-colored digraph. We say that D is closed by $(H,k-1)$-walks in $\xi$, if every $(H,k-1)$-walk of D is contained in $G_s$, for some $s\in \{ 1,\ldots ,t\}$, and D is closed by cycles in $\xi$, if every cycle of D is contained in $G_r$, for some $r\in \{ 1,\ldots ,t\}$.

Remark 1

Let H be a digraph, possibly with loops and D be an H-arc-colored digraph. Suppose that D is closed by $(H,k-1)$-walks in $\xi$. If $T_1$ and $T_2$ are $(H,k-1)$-paths in D, from u to v and from v to w, respectively, and v is not an H-obstruction to $T_1\cup T_2$, then there is $C_j\in \xi$ such that $T_1$, $T_2$ and $T_1\cup T_2$ are contained in $G_j$, for some $j\in \{ 1,\ldots ,t\}$.

Remark 2

Let H be a digraph, possibly with loops and D be an H-arc-colored digraph. Suppose that D is closed by cycles in $\xi$ and closed by $(H,k-1)$-walks in $\xi$. If $T_1$ and $T_2$ are $(H,k-1)$-paths in D, from u to v and from v to u, respectively, then there is $C_j\in \xi$ such that $T_1$, $T_2$ and $T_1\cup T_2$ are contained in $G_j$, for some $j\in \{ 1,\ldots ,t\}$.

The proofs of Remarks 1 and 2 are as follows, straightforward from the definition of a digraph which is closed by $(H,k-1)$-walks in $\xi$ and closed by cycles in $\xi$.

Lemma 9

Let H be a digraph, possibly with loops and D be an H-arc-colored digraph, such that every 3-cycle of $R_{(H,k-1)}(G_r)$ has at least two symmetrical arcs, for every $r\in \{ 1,\ldots ,t\}$, and D is closed by cycles in $\xi$ and closed by $(H,k-1)$-walks in $\xi$.

Then, there is no asymmetrical cycle in $R_{(H,k-1)}(D)$.

Proof

Let D a digraph as in the hypothesis. First, we will show that there is no asymmetrical 3-cycle in $R_{(H,k-1)}(D)$. Proceeding by contradiction, suppose that $(x_0,x_1,x_2,x_0)$ is an asymmetrical 3-cycle of $R_{(H,k-1)}(D)$. By definition of $(H,k-1)$-closure, there are $T_0$, $T_1$ and $T_2$ $(H,k-1)$-paths from $x_0$ to $x_1$, from $x_1$ to $x_2$ and from $x_2$ to $x_0$, respectively. We have the following cases.

Case 1. There is $i\in \mathbb {Z}_3$ such that $x_i$ is not an H-obstruction to $T_{i-1}\cup T_i$.

Suppose without loss of generality that $x_1$ is not an H-obstruction to $T_{0}\cup T_1$. By Remark 1, it follows that $T_{0}$ and $T_{1}$ are contained in $G_s$, for some $s\in \{ 1,\ldots ,t\}$. Since $G_s$ is $(H,k-1)$-path-quasi-transitive and by Lemma 8.1, then there is an $(H,k-1)$-path from $x_{0}$ to $x_{2}$ in $G_s$, contradicting that $(x_0,x_1,x_2,x_0)$ is asymmetrical in $R_{(H,k-1)}(D)$.

Case 2. For every $i\in \mathbb {Z}_3$, $x_i$ is an H-obstruction to $T_{i-1}\cup T_i$.

If $(V(T_i)-\{x_{i+1}\})\cap V(T_{i+1})=\emptyset$, for every $i\in \mathbb {Z}_3$, then $T_0\cup T_1\cup T_2$ is a cycle in D. Since D is closed by cycles in $\xi$, then there is $r\in \{1,\ldots ,t\}$ such that $T_0\cup T_1\cup T_2$ is contained in $G_r$. It follows that $(x_0,x_1,x_2,x_0)$ is an asymmetrical 3-cycle in $R_{(H,k-1)}(G_s)$, which is impossible. Assume, for the sake of a contradiction that $(V(T_0)-\{x_{1}\})\cap V(T_{1})\ne \emptyset$. Let u be the first vertex of $T_{1}$ in $T_0$. Note that $u\ne x_{0}$ because there is no $(H,k-1)$-path from $x_{1}$ to $x_{0}$ in D. Consider $\gamma =(u,T_0,x_{1})\cup (x_{1},T_{1},u)$ is a cycle of D with arcs of $T_0$ and $T_{1}$. Since D is closed by cycles in $\xi$, then $T_0$ and $T_{1}$ are contained in $G_s$ for some $s\in \{1,\ldots ,t\}$. Moreover, as $G_s$ is an $(H,k-1)$-path-quasi-transitive digraph and by Lemma  8.1, there is an $(H,k-1)$-path from $x_{0}$ to $x_{2}$, contradicting the hypothesis.

Therefore, there is no asymmetrical 3-cycle in $R_{(H,k-1)}(D)$.

Now, we will prove that there is no asymmetrical n-cycle in $R_{(H,k-1)}(D)$. Proceeding by contradiction, suppose that $(x_0,x_1,\ldots ,x_{n-1},x_n)$ is an asymmetrical n-cycle in $R_{(H,k-1)}(D)$ with minimum length. Observe that $n\ge 4$. We will analyze two cases.

Case 1. There is $i\in \{0,\ldots ,n-1\}$ such that $x_i$ is not an H-obstruction to $T_{i-1}\cup T_i$.

By Remark 1, $T_{i-1}\cup T_i$ is contained in $G_s$, for some $s\in \{ 1,\ldots ,t\}$. Since $G_{s}$ is an $(H,k-1)$-path-quasi-transitive digraph, and by Lemma 8.1, $(x_{i-1},x_{i+1})$ is an arc of $R_{(H,k-1)}(G_s)$ and there is no arc from $x_{i+1}$ to $x_{i-1}$ in $R_{(H,k-1)}(G_s)$. Even more, by Remark 2, every $(H,k-1)$-path from $x_{i+1}$ to $x_{i-1}$ in D is contained in $G_s$. Thus, there is no $(H,k-1)$-path from $x_{i+1}$ to $x_{i-1}$ in D. From the above, $(x_0,\ldots x_{i-1},x_{i+1},\ldots ,x_{n-1},x_0)$ is an asymmetrical $(n-1)$-cycle in $R_{(H,k-1)}(D)$, which is a contradiction.

Case 2. For every $i\in \{0,\ldots ,n-1\}$, $x_i$ is an H-obstruction to $T_{i-1}\cup T_i$. Consider the following two subcases.

Case 2.1. For some $i\in \{0,1,\ldots , n-1\}$, $(V(T_i)-\{x_{i+1} \})\cap V(T_{i+1})\ne \emptyset$.

Notice that $T_i\cup T_{i+1}$ contains a cycle $\gamma$. By hypothesis, $\gamma$ is contained in $G_l$ for some $l\in \{ 1,\ldots , t\}$; moreover, $\gamma$ has arcs from $T_i$ and $T_{i+1}$, it follows that $G_l=G_{i'}=G_{(i+1)'}$. Since $G_l$ is $(H,k-1)$-path-quasi-transitive, by Lemma 8.1, then there is an $(H,k-1)$-path T from $x_i$ to $x_{i+2}$ in $G_l$ and there is no $(H,k-1)$-path from $x_{i+2}$ to $x_i$ in $G_l$. Even more, by Remark  2, every $(H,k-1)$-path from $x_{i+1}$ to $x_{i-1}$ in D is contained in $G_l$. Thus, there is no $(H,k-1)$-path from $x_{i+1}$ to $x_{i-1}$ in D. From above, $(x_0,x_1\ldots x_i,x_{i+2},\ldots ,x_{n-1},x_0)$ is an asymmetrical $(n-1)$-cycle in $R_{(H,k-1)}(D)$, which is a contradiction.

Case 2.2. For every $i\in \{0,1,\ldots , n-1\}$, $(V(T_i)-\{x_{i+1} \})\cap V(T_{i+1})= \emptyset$.

If $V(T_i)\cap V(T_j)=\emptyset$, for every $i,j\in \{0, 1,\ldots ,n-1\}$ such that $\vert i-j\vert \ge 2$, then $\displaystyle \bigcup ^{n-1}_{j=0}T_j$ is a cycle of D. By hypothesis, $\displaystyle \bigcup ^{n-1}_{j=0}T_j$ is contained in $G_l$, for some $l\in \{1,\ldots ,t\}$. It follows that $(x_0,x_1,\ldots ,x_{n-1},x_0)$ is an asymmetrical cycle in $R_{(H,k-1)}(G_l)$, but by Lemma 8.2, this is impossible.

Assume that $V(T_i)\cap V(T_j)\ne \emptyset$, for some $i,j\in \{ 1,\ldots ,t\}$ such that $\vert i-j\vert \ge 2$ and it is minimum. Suppose that $i<j$ and let u be the first vertex of $V(T_j)$ which is in $V(T_i)$.

If $u=x_i$, then $\gamma =T_i\cup \cdots \cup T_{j-1}\cup (x_j,T_j,u=x_i)$ is cycle of D. Hence, $T_i\cup \cdots \cup T_j$ is contained in $G_l$, for some $l\in \{ 1,\ldots ,t\}$. Thus, $(x_{i+1},\ldots ,x_j)$ is an asymmetrical path in $R_{(H,k-1)}(G_l)$. By Lemma 8.1, $(x_{i+1},x_r)$ is an arc of $R_{(H,k-1)}(G_l)$ and there is no arc from $x_r$ to $x_{i+1}$ in $R_{(H,k-1)}(G_l)$, for each $r\in \{ i+1,\ldots ,j\}$. It follows that $C=(x_i,x_{i+1},x_j,x_i)$ is a 3-cycle in $R_{(H,k-1)}(G_l)$, then C has at least two symmetrical arcs, which is a contradiction.

If $u=x_{i+1}$, then this subcase is analogous to the previous subcase, exchanging i for $i+1$.

If $u=x_j$, then $\gamma =(x_j,T_i,x_{i+1})\cup T_{i+1}\cup \cdots \cup T_{j-1}$ is a cycle of D. Hence, $T_i\cup \cdots \cup T_{j-1}$ is contained in $G_l$, for some $l\in \{ 1,\ldots ,t\}$. Thus, $(x_{i+1},\ldots ,x_{j-1})$ is an asymmetrical path in $R_{(H,k-1)}(G_l)$. By Lemma 8.1, $(x_{i+1},x_r)$ is an arc of $R_{(H,k-1)}(G_l)$ and there is no arc from $x_r$ to $x_{i+1}$ in $R_{(H,k-1)}(G_l)$, for each $r\in \{ i+2,\ldots ,j-1\}$. It follows that $C=(x_{j-1},x_j,x_{i+1},x_{j-1})$ is a 3-cycle in $R_{(H,k-1)}(G_l)$, then C has at least two symmetrical arcs, which is a contradiction.

If $u=x_{j+1}$, then this subcase is analogous to the previous subcase, exchanging j for $j+1$.

Finally, if $u\notin \{ x_i,x_{i+1},x_j,x_{j+1}\}$, then $\gamma =(u,T_i,x_{i+1})\cup T_{i+1}\cup \cdots \cup T_{j-1}\cup (x_j,T_j,u)$ is cycle of D. Hence, $T_i\cup \cdots \cup T_j$ is contained in $G_l$, for some $l\in \{ 1,\ldots ,t\}$. Thus, $(x_{i+1},\ldots ,x_{j-1},x_j,x_{j+1})$ is an asymmetrical path in $R_{(H,k-1)}(G_l)$. By Lemma 8.1, $(x_{i+1},x_r)$ is an arc of $R_{(H,k-1)}(G_l)$ and there is no arc from $x_r$ to $x_{i+1}$ in $R_{(H,k-1)}(G_l)$, for each $r\in \{ i+2,\ldots ,j,j+1\}$. Note that $(x_i,x_{i+1},x_{j+1})$ is an asymmetrical path in $R_{(H,k-1)}(G_l)$, by Lemma 8.1, $(x_{i},x_{j+1})$ is an arc of $R_{(H,k-1)}(G_l)$ and there is no arc from $x_{j+1}$ to $x_i$ in $R_{(H,k-1)}(G_l)$. Moreover, by Remark  2, every $(H,k-1)$-path from $x_{j+1}$ to $x_i$ in D is contained in $G_l$. Thus there is no $(H,k-1)$-path from $x_{j+1}$ to $x_i$ in D. It follows that $(x_0,x_1,\ldots ,x_i,x_{j+1},\ldots ,x_{n-1},x_0)$ is an asymmetrical cycle in $R_{(H,k-1)}(D)$ with less vertices than n, which is a contradiction.

Therefore, $R_{(H,k-1)}(D)$ has no asymmetrical cycles. $\square$

Lemma 10

Let H be a digraph, possibly with loops and D be an H-arc-colored digraph, such that every 3-cycle of $R_{(H,k-1)}(G_r)$ has at least two symmetrical arcs, for every $r\in \{ 1,\ldots ,t\}$. If D is closed by cycles in $\xi$ and closed by $(H,k-1)$-walks in $\xi$, then the following assertions hold.

• 1. There is no sequence of vertices $(x_0,x_1,x_2,\ldots )$ such that for every $i\in \{0,1,2,\ldots \}$, $(x_i,x_{i+1})$ is an arc of $R_{(H,k-1)}(D)$ and there is no arc from $x_{i+1}$ to $x_i$ in $R_{(H,k-1)}(D)$.

• 2. There is x in V(D) such that $\{x\}$ is a (H, k)-semikernel of D.

Proof

The proof of the first assertion follows immediately from the finiteness of D and Lemma 9.

For the second assertion, proceeding by contradiction, a vertex sequence can be constructed that contradicts the first assertion. $\square$

Let H be a digraph possible with loops and D be an H-arc-colored digraph. From now, $\{\xi _1,\xi _2\}$ is a partition of $\xi$ and $D_i$ denotes the spanning subdigraph of D such that $A(D_i)=\{ a\in A(D):\ \zeta (a)\in C_r\text { with }C_r\in \xi _i\}$, for every $i\in \{1,2\}$. Notice that every $G_r$ is a subdigraph of either $D_1$ or $D_2$, with $r\in \{ 1,\ldots ,t\}$.

Let H be a digraph possible with loops and D be an H-arc-colored digraph. We will say that a subset S of V(D) is an (H, k)-semikernel modulo $D_2$ of D if and only if S is an independent set in $R_{(H,k-1)}(D)$ such that if (x, y) is an arc of $R_{(H,k-1)}(D_1)$, with $x\in S$ and $y\in V(D)-S$, then (y, w) is an arc of $R_{(H,k-1)}(D)$, with $w\in S$. (Notice that w and x can be the same vertex.)

Lemma 11

Let H be a digraph, possibly with loops and D be an H-arc-colored digraph, such that every 3-cycle of $R_{(H,k-1)}(G_r)$ has at least two symmetrical arcs for every $r\in \{ 1,\ldots ,t\}$.

If $D_i$ is closed by cycles in $\xi _i$ and closed by $(H,k-1)$-walks in $\xi _i$, then there is $x_0$ in V(D) such that $\{x_0\}$ is an (H, k)-semikernel modulo $D_2$ of D.

Proof

If $\{\xi _1\}=C_r$ for some $r\in \{ 1,\ldots ,t\}$, then $A(D_1)=A(G_r)$. By Lemma 8.4 there is $x\in V(G_r),$ which is an (H, k)-semikernel of $G_r$. Thus, from the definition, $\{ x\}$ of (H, k)-semikernel modulo $D_2$ of D. Now, assume that $\vert \xi _1\vert \ge 2$. Let $H'$ be the subdigraph of H induced by $\displaystyle \bigcup _{r\in \xi _1} C_r$. By definition, $D_1$ is an $H'$-arc-colored digraph and $\xi _1$ is a partition of $V(H')$, where $G_i=D_1[\{ a\in A(D):\ \zeta (a)\in C_i\}]$. Moreover, $G_i$ is $(H',k-1)$-path-quasi-transitive. Hence, the hypotheses of Lemma  10 hold. Thus there is a vertex x of $V(D_1)=V(D)$ such that $\{x\}$ is a $(H',k)$-semikernel of $D_1$. Therefore, from the definition of (H, k)-semikernel modulo $D_2$, $\{ x\}$ is an (H, k)-semikernel modulo $D_2$ of D. $\square$

Let $\mathcal {S}$ be the set $\{ S \subseteq V(D):\ S$ is a nonempty (H, k)-semikernel modulo $D_2$ of $D\}$. When $\mathcal {S}\ne \emptyset$, we can define the digraph $D_{\mathcal {S}}$ as follows: $V(D_{\mathcal {S}})=\mathcal {S}$ and $(S_1,S_2)\in A(D_{\mathcal {S}})$ if and only if for every $s_1\in S_1$ there is $s_2\in S_2,$ such that either $s_1=s_2$, or $(s_1,s_2)$ is an arc of $R_{(H,k-1)}(D_2)$ and there is no arc from $s_2$ to $s_1$ in $R_{(H,k-1)}(D)$.

Lemma 12

Let H be a digraph, possibly with loops and D be an H-arc-colored digraph, such that every 3-cycle of $R_{(H,k-1)}(G_r)$ has at least two symmetrical arcs for every $r\in \{ 1,\ldots ,t\}$.

If $D_i$ is closed by cycles in $\xi _i$ and closed by $(H,k-1)$-walks in $\xi _i$, then $D_{\mathcal {S}}$ can be defined and it is an acyclic digraph.

Proof

By Lemma 11, D has a nonempty (H, k)-semikernel modulo $D_2$, hence $\mathcal {S}\ne \emptyset$. We can consider $D_{\mathcal {S}}$. Proceeding by contradiction, suppose that $D_{\mathcal {S}}$ contains a cycle $\gamma =(S_0,S_1,\ldots ,S_{n-1},S_0)$, with $n\ge 2$.

Claim 1

There is z in $S_{i_0}$ such that $z\notin S_{i_0+1}$ for some $i_0\in \{ 0,1, \ldots , n -1\}$ (the subscripts are taken modulo n).

If the Claim 1 is not true, then, by definition of $D_{\mathcal {S}}$, $S_i \subseteq S_ {i+1}$, it follows that $S_i = S_j$ with $i,j\in \{ 0,1,\ldots ,n-1\}$, $i\ne j$, contradicting that the length of $\gamma$ is at least two. This ends the proof of Claim 1.

Claim 2

Let $l_0\in \{ 0,1,\ldots ,n-1\}$. If there are $z\in S_{l_0}$ and $w\in S_{l_0+1}$ such that (z, w) is an arc of $R_{(H,k-1)}(D)$, then there exists $j_0\in \{ 0,1,\ldots ,n-1\}$, $j_0\ne l_0$ such that $w\in S_{j_0}$ and $w\notin S_{j_0+1}$ (the subscripts are taken modulo n).

Let z and w be two vertices as in the hypothesis of Claim 2. Suppose without loss of generality that $l_0 = 0$, this implies that $w\in S_1$. On the other hand, since $S_{0}$ is an (H, k)-semikernel modulo $D_2$ of D, then $w\notin S_0$. Let $j_0=\text {max}\{ i\in \{1,\ldots ,n-1\}:\ w\in S_i\}$. By choice of $j_0$, we have that $w\in S_{j_0}$ and $w\notin S_{j_0+1}$ (subscripts modulo n). This ends the proof of Claim 2.

By Claim 1, there exists $x_0 \in S_{i_0}$ with $x_0\notin S_{i_0+1}$ for some $i_0\in \{ 0,1,\ldots ,n-1\}$. Since $(S_{i_0}, S_{i_0+1})\in A(D_{\mathcal {S}}),$ and by definition of $D_{\mathcal {S}}$, there is $x_1\in S_{i_0+1}$ such that $(x_0,x_1)$ is an arc of $R_{(H,k-1)}(D_2)$ and there is no arc from $x_1$ to $x_0$ in $R_{(H,k-1)}(D)$. Now, by Claim 2, there is $i_1\in \{ 0,1,\ldots ,n-1\}$ such that $x_1\in S_{i_1}$ and $x_1\notin S_{i_1+1}$. Since $(S_{i_1},S_{i_1+1})$ is an arc of $D_{\mathcal {S}}$, there is $x_2\in S_{i_1+1}$ such that $(x_1,x_2)$ is an arc of $R_{(H,k-1)}(D_2)$ and there is no arc from $x_2$ to $x_1$ in $R_{(H,k-1)}(D)$.

Recursively, we can construct a sequence of vertices $(x_0,x_1,\ldots )$ such that $(x_i,x_{i+1})$ is an arc of $R_{(H,k-1)}(D_2)$ and there is no arc from $x_{i+1}$ to $x_i$ in $R_{(H,k-1)}(D)$ (and in consequence in $R_{(H,k-1)}(D_2)$). If $\vert \xi _2\vert \ge 2$, then we have a contradiction to Lemma  10. When $\vert \xi _2\vert =1$, suppose that $\xi _2=\{C_r\}$. It follows that $A(D_2)=A(G_r)$ and $(x_0,x_1,x_2,\ldots )$ is a sequence of vertices of $G_r$ such that $(x_i,x_{i+1})$ is an arc of $R_{(H,k-1)}(G_r)$ and there is no arc from $x_{i+1}$ to $x_i$ in $R_{(H,k-1)}(G_r)$, contradicting Lemma 8.3.

Therefore, $D_{\mathcal {S}}$ is an acyclic digraph. $\square$

Lemma 13

Let H be a digraph, possibly with loops and D be an H-arc-colored digraph, such that every 3-cycle of $R_{(H,k-1)}(G_r)$ has at least two symmetrical arcs for every $r\in \{ 1,\ldots ,t\}$.

If $D_i$ is closed by $(H,k-1)$-walks in $\xi _i$, and every $\xi _1\xi _2$-arc and every $\xi _2\xi _1$-arc in $A({\mathscr {C}}_C(D))$ is not an arc of H, then every $(H,k-1)$-walk of D is contained either $D_1$ or in $D_2$. Moreover, every $(H,k-1)$-walk of D is contained in $G_l$ for some $l\in \{1,\ldots ,t\}$.

Proof

Let $W= (x_0,x_1,\ldots ,x_n)$ be an $(H,k-1)$-walk in D. Proceeding by contradiction, suppose that W is not contained in neither $D_1$ nor $D_2$. It follows that there is $i\in \{0,1,\ldots ,n-1\}$ such that $(x_i,x_{i+1})$ is an arc of $D_1$ and $(x_{i+1},x_{i+2})$ is an arc of $D_{2}$, or $(x_i,x_{i+1})$ is an arc of $D_2$ and $(x_{i+1},x_{i+2})$ is an arc of $D_{1}$, it follows that $(\zeta ((x_i,x_{i+1})),\zeta ((x_{i+1},x_{i+2})))$ is a $\xi _1\xi _2$-arc or a $\xi _2\xi _1$-arc in $A({\mathscr {C}}_C(D))$, moreover, since W is an $(H,k-1)$-walk in D, then $(\zeta ((x_i,x_{i+1})),\zeta ((x_{i+1},x_{i+2})))\in A(H)$, which is a contradiction. In addition, from above and by hypothesis, every $(H,k-1)$-walk of D is contained in $G_l$ for some $l\in \{1,\ldots ,t\}$. $\square$

Let $W = (u_0,\ldots ,u_l= v_0,\ldots , v_m=w_0,\ldots w_n=u_0)$ be a cycle in D. We say that W is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$ if $W_1 = (u_0,W, u_l)$ is an $(H,k-1)$-path contained in $D_1$, $W_2 = (v_0,W, v_m)$ is an $(H,k-1)$-path contained in D and $W_3 = (w_0,W, w_n)$ is an $(H,k-1)$-path contained in $D_2$, where $v_0$, $w_0$ and $u_0$ are H-obstructions to $W_1\cup W_2$, $W_2\cup W_3$ and $W_3\cup W_1$, respectively.

Let $T = (u_0,\ldots ,u_l= v_0,\ldots , v_m=w_0,\ldots w_n)$ be a path in D. We say that T is an $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$ if $T_1 = (u_0,T, u_l)$ is an $(H,k-1)$-path contained in $D_1$, $T_2 = (v_0,T, v_m)$ is an $(H,k-1)$-path contained in D and $T_3 = (w_0,T, w_n)$ is an $(H,k-1)$-path contained in $D_2$, where $v_0$ and $w_0$ are H-obstructions to $T_1\cup T_2$ and $T_2\cup T_3$, respectively.

Let $W=(u_0,\ldots ,u_l= v_0,\ldots , v_m=w_0,\ldots w_n=u_0)$ and $T=(u'_0,\ldots ,u'_l= v'_0,\ldots , v'_m=w'_0,\ldots w'_n)$ be a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$ and a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$, respectively. By the previous definitions and the definition of $(H,k-1)$-closure, it follows that $(u_0,v_0,w_0,u_0)$ is a 3-cycle of $R_{(H,k-1)}(D)$ such that $(u_0,v_0)$ is also an arc of $R_{(H,k-1)}(D_1)$ and $(w_0,u_0)$ is also an arc of $R_{(H,k-1)}(D_2)$. In the same way, $(u'_0,v'_0,w'_0,w'_n)$ is a 4-path of $R_{(H,k-1)}(D)$ such that $(u'_0,v'_0)$ is also an arc of $R_{(H,k-1)}(D_1)$ and $(w'_0,w'_n)$ is also an arc of $R_{(H,k-1)}(D_2)$.

Lemma 14

Let H be a digraph, possibly with loops and D be an H-arc-colored digraph, such that every 3-cycle of $R_{(H,k-1)}(G_r)$ has at least two symmetrical arcs for every $r\in \{ 1,\ldots ,t\}$, $D_i$ is closed by cycles in $\xi _i$ and closed by $(H,k-1)$-walks in $\xi _i$, for each $i\in \{ 1,2\}$, every $\xi _1\xi _2$-arc and every $\xi _2\xi _1$-arc in $A({\mathscr {C}}_C(D))$ is not an arc of H.

Let $\{ u, v, w, z\}$ be a subset of V(D), such that (u, w), (v, z), (v, u) and (z, w) are not arcs in $R_{(H,k-1)}(D)$. If there are $(H,k-1)$-paths from u to v, from v to w and from w to z, $\alpha _1$, $\alpha _2$ and $\alpha _3$, respectively, such that $\alpha _1$ is contained in $D_1$ and $\alpha _3$ contained in $D_2$, where v and w are H-obstructions to $\alpha _1\cup \alpha _2$ and $\alpha _2\cup \alpha _3$, respectively (u can be z), then either there is an path from u to z which is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$ or there is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$.

Proof

Consider the following assertions:

• 1. $u\notin V(\alpha _2)$.

• 2. $v\notin V(\alpha _3)$.

• 3. $w\notin V(\alpha _1)$.

• 4. $z\notin V(\alpha _2)$.

• 5. If $\beta _1$ is an $(H,k-1)$-walk from a to b in $D_i$ and $\beta _2$ is an $(H,k-1)$-walk from b to c contained in $D_j$, with $\{ i, j\}\subseteq \{1, 2\}$, $i\ne j$, then b is an H-obstruction to $\beta _1\cup \beta _2$.

• 6. u, v and w are three different vertices and $z\notin \{ v,w\}$.

The first four assertions follow immediately from the hypotheses. Assertion 5 follows from Lemma  13, and the last assertion follows from the first four assertions and the hypothesis.

To proceed with the proof of the Lemma 14, we consider two possible cases.

Case 1. $\alpha _2$ is contained in $D_1$.

If $((V(\alpha _1)\cap V(\alpha _2))-\{ v\} )\ne \emptyset$, then $\alpha _1\cup \alpha _2$ contains a cycle $\gamma$, which has arcs of both $\alpha _1$ and $\alpha _2$. Since $\alpha _1$ and $\alpha _2$ are contained in $D_1$, then $\gamma$ is contained in $D_1$. By hypothesis, $\gamma$ is contained in $G_l$, with $l\in \{1,\ldots ,t\}$. It follows that $\alpha _1$ and $\alpha _2$ are contained in $G_l$. Since $G_l$ is $(H,k-1)$-path-quasi-transitive, then there is an $(H,k-1)$-path from u to w or there is an $(H,k-1)$-path from w to u in $G_l$; even more, by hypothesis there is no $(H,k-1)$-path from u to w in D. Thus there is an $(H,k-1)$-path from w to u in $G_l$. By hypothesis, $C=(u,v,w,u)$ is a 3-cycle in $R_{(H,k-1)}(G_l),$ it follows that C has two symmetrical arcs, contradicting the hypothesis. So we may assume that $V(\alpha _1)\cap V(\alpha _2)=\{ v\}$.

Observation 1

$\alpha _1\cup \alpha _2$ is not an H-walk. Otherwise, by Remark 1, $\alpha _1$ and $\alpha _2$ are contained in $G_l$, for some $l\in \{ 1,\ldots ,t\}$. Proceeding as in the previous paragraph, there is an $(H,k-1)$-path from w to u in $G_l$. By hypothesis, $C=(u,v,w,u)$ is a 3-cycle in $R_{(H,k-1)}(G_l),$ and it follows that C has two symmetrical arcs, which is impossible.

If $V(\alpha _2)\cap V(\alpha _3)=\{ w\}$, then we have the following cases.

Case 1.1 $V(\alpha _1)\cap V(\alpha _3)=\emptyset$.

In this case, $\alpha _1\cup \alpha _2\cup \alpha _3$ is a path; moreover, by Observation 1 and Assertion 5, $\alpha _1\cup \alpha _2\cup \alpha _3$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$.

Case 1.2 $V(\alpha _1)\cap V(\alpha _3)\ne \emptyset$.

Let x be the last vertex in $\alpha _1$ that is in $\alpha _3$. By Assertions 2 and 3, $x \notin \{ v,w\}$. From Assertion 5, we have that x is an H-obstruction to $(w,\alpha _3,x)\cup (x,\alpha _1,v)$ and w is an H-obstruction to $\alpha _2\cup (w,\alpha _3,x)$, and, by Observation 1, v is an H-obstruction to $(x,\alpha _1,v)\cup \alpha _2$. It follows that $(x,\alpha _1,v)\cup \alpha _2\cup (w,\alpha _3,x)$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$.

If $(V(\alpha _2)\cap V(\alpha _3)-\{w\})\ne \emptyset$, then we have the following cases.

Case 1.3 $V(\alpha _1)\cap V(\alpha _3)=\emptyset$.

Notice that $u\ne z$. Let x be the first vertex in $\alpha _2$ that is in $\alpha _3$. By Assertions 2 and 4, $x\notin \{v,z\}$. By Assertion 5, x is an H-obstruction to $(v,\alpha _2,x)\cup (x,\alpha _3,z)$ and, by Observation 1, v is an H-obstruction to $\alpha _1\cup (v,\alpha _2,x)$. It follows that $\alpha _1\cup (v,\alpha _2,x)\cup (x,\alpha _3,z)$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$.

Case 1.4 $V(\alpha _1)\cap V(\alpha _3)\ne \emptyset$.

Let x and y be the first and the last vertex of $\alpha _3$, respectively, that are in $\alpha _1\cup \alpha _2$.

If $x\in V(\alpha _1)$, then, by Assertions 2 and 3, $x\notin \{v,w\}$. By Observation 1, v is an H-obstruction to $(x,\alpha _1,v)\cup \alpha _2$, and, by Assertion 5, x is an H-obstruction to $(w,\alpha _3,x)\cup (x,\alpha _1,v)$ and w is an H-obstruction to $\alpha _2\cup (w,\alpha _3,x)$. Thus, $(x,\alpha _1,v)\cup \alpha _2\cup (w,\alpha _3,x)$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$.

If $x\in V(\alpha _2)$ and $y\in V(\alpha _1)$, then $x\ne y$. Let a be the last vertex of $\alpha _3$ that is in $\alpha _2$, a exists because $x\in V(\alpha _2)$, and let b the first vertex in $(a,\alpha _3,z)$ that is in $\alpha _1$, b exists because $y\in V(\alpha _1)$ and $y\in V((a,\alpha _3,z))$. By Assertions 1, 2 and 4, then $a\notin \{ u,v,z\}$. Also, by Assertions 2 and 3, $b\notin \{ v,w\}$. Since $V(\alpha _1)\cap V(\alpha _2)=\{ v\}$ and $v\notin \{a,b\}$, then $a\ne b$. By Observation 1 and Assertion 5, v, a and b are H-obstructions to $(b,\alpha _1,v)\cup (v,\alpha _2,a)$, $(v,\alpha _2,a)\cup (a,\alpha _3,b)$ and $(a,\alpha _3,b)\cup (b,\alpha _1,v)$, respectively. Thus, $(b,\alpha _1,v)\cup (v,\alpha _2,a)\cup (a,\alpha _3,b)$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$.

If $x\in V(\alpha _2)$ and $y\in V(\alpha _2)$, then, by Assertions 2 and 4, $y\notin \{ v,z\}$. It follows that $V(\alpha _1)\cap V((y,\alpha _3, z))=\emptyset$. By Observation 1, v is an H-obstruction to $\alpha _1\cup (v,\alpha _2,y)$, and by Assertion 5, y is an H-obstruction to $(v,\alpha _2,y)\cup (y,\alpha _3,z)$. Thus $\alpha _1\cup (v,\alpha _2,y)\cup (y,\alpha _3,z)$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$.

Case 2. $\alpha _2$ is contained in $D_2$.

If $((V(\alpha _2)\cap V(\alpha _3))-\{ v\} )\ne \emptyset$, then $\alpha _2\cup \alpha _3$ contains a cycle, $\gamma$, which has arcs from both $\alpha _2$ and $\alpha _3$. Since $\alpha _2$ and $\alpha _3$ are contained in $D_2$, then $\gamma$ is contained in $D_2$. By hypothesis, $\gamma$ is contained in $G_l$, with $l\in \{1,\ldots ,t\}$. It follows that $\alpha _2$ and $\alpha _3$ are contained in $G_l$. Since $G_l$ is $(H,k-1)$-path-quasi-transitive, then there is an $(H,k-1)$-path from v to z in $G_l$ or there is an $(H,k-1)$-path from z to v in $G_l$, even more, by hypothesis, there is no $(H,k-1)$-path from v to z in D. Thus, there is an $(H,k-1)$-path from z to v. By hypothesis, $C=(v,w,z,v)$ is a 3-cycle in $R_{(H,k-1)}(G_l)$, it follows that C has two symmetrical arcs, contradicting the hypothesis. So we may assume that $V(\alpha _2)\cap V(\alpha _3)=\{w\}$.

Observation 2

$\alpha _2\cup \alpha _3$ is not an H-walk. Otherwise, by Remark  1$\alpha _2$ and $\alpha _3$ are contained in $G_l$, for some $l\in \{ 1,\ldots ,t\}$. Proceeding as in the previous paragraph, there is an $(H,k-1)$-path from z to v in $G_l$. By hypothesis, $C=(v,w,z,v)$ is a 3-cycle in $R_{(H,k-1)}(G_l)$, it follows that C has two symmetrical arcs, which is impossible.

If $V(\alpha _1)\cap V(\alpha _2)=\{ v\}$, then we have the following cases.

Case 2.1 $V(\alpha _1)\cap V(\alpha _3)=\emptyset$.

In this case, $\alpha _1\cup \alpha _2\cup \alpha _3$ is a path, moreover, by Observation 2 and Assertion 5, $\alpha _1\cup \alpha _2\cup \alpha _3$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$.

Case 2.2 $V(\alpha _1)\cap V(\alpha _3)\ne \emptyset$.

Let x be the last vertex in $\alpha _1$ which is also in $\alpha _3$. By Assertions 2 and 3, $x \notin \{ v,w\}$. By Assertions 5, x is an H-obstruction to $(w,\alpha _3,x)\cup (x,\alpha _1,v)$ and v is an H-obstruction to $(x,\alpha _1,v)\cup \alpha _2$, and by Observation 2, w is an H-obstruction to $\alpha _2\cup (w,\alpha _3,x)$. It follows that $(x,\alpha _1,v)\cup \alpha _2\cup (w,\alpha _3,x)$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$.

If $(V(\alpha _1)\cap V(\alpha _2)-\{ v\})\ne \emptyset$, then we have the following cases.

Case 2.3 $V(\alpha _1)\cap V(\alpha _3)=\emptyset$.

Notice that $u\ne z$. Let x be the first vertex in $\alpha _1$ which is also in $\alpha _2$. By Assertions 1 and 3, $x\notin \{u,w\}$. By Assertions 5, x is an H-obstruction to $(u,\alpha _1,x)\cup (x,\alpha _2,w)$, and, by Observation 2, w is an H-obstruction to $(x,\alpha _2,w)\cup \alpha _3$. It follows that $(u,\alpha _1,x)\cup (x,\alpha _2,w)\cup \alpha _3$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$.

Case 2.4 $V(\alpha _1) \cap V(\alpha _3)\ne \emptyset$.

Let x be the first vertex in $\alpha _1$ which is also in $\alpha _3$. By Assertions 2 and 3, $x\notin \{ v,w\}$. Let y be the first vertex in $(x,\alpha _1,v)$ which is also in $\alpha _2$ (y can be v). By Assertion 3, $y\ne w$, moreover, since $V(\alpha _2)\cap V(\alpha _3)=\{ w\}$ and $x\ne w$, we have that $x\ne y$. By Assertion 5, y is an H-obstruction to $(x,\alpha _1,y)\cup (y,\alpha _2,w)$ and x is an H-obstruction to $(w,\alpha _3,x)\cup (x,\alpha _1,y)$, and, by Observation 2, w is an H-obstruction to $(y,\alpha _2,w)\cup (w,\alpha _3,x)$. Thus $(x,\alpha _1,y)\cup (y,\alpha _2,w)\cup (w,\alpha _3,x)$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$. $\square$

4 Main Result

Theorem 15

Let H be a digraph, possibly with loops and D be an H-arc-colored digraph, such that every 3-cycle of $R_{(H,k-1)}(G_r)$ has at least two symmetrical arcs for every $r\in \{ 1,\ldots ,t\}$, $D_i$ is closed by cycles in $\xi _i$ and closed by $(H,k-1)$-walks in $\xi _i$, for each $i\in \{ 1,2\}$, every $\xi _1\xi _2$-arc and every $\xi _2\xi _1$-arc in $A({\mathscr {C}}_C(D))$ is not an arc of H, D has no $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$ and whenever there is a path from u to z which is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$, for some $u,z\in V(D)$, then there is an $(H,k-1)$-path from u to z.

Then, D has an (H, k)-kernel.

Proof

Let D as in the hypotheses. By Lema 12, $D_{\mathcal {S}}$ is an acyclic digraph, it follows that there is a sink S in $D_{\mathcal {S}}$. We will prove that S is an (H, k)-kernel of D.

By definition of $D_{\mathcal {S}}$, S is an (H, k)-semikernel modulo $D_2$ of D. It follows that S is an (H, k)-independent set in D. We will prove that S is $(H,k-1)$-absorbent in D.

Let $X=\{ x\in V(D)-S:\ x\text { cannot reach any vertex in }S\text { by }(H,k-1)\text {-paths in }D\}$. Proceeding by contradiction, suppose that X is non-empty.

Observe that $D_1$ is an $H[\xi _1]$-arc-colored digraph. If $\vert \xi _1\vert \ge 2$, then $\xi _1$ is a partition of $V(H[\xi _1])$. By hypotheses, $D_1$ is an $H[\xi _1]$-arc-colored digraph which the hypotheses of Lemma 10 hold. On the other hand, if $\xi _1=\{C_r \}$, then $A(D_1)=A(G_r)$ and the hypotheses of Lemma 8.2 hold. It follows that, there is $x_0\in X$ such that for every $y\in X$, $y\ne x_0$, if there exists an $(H,k-1)$-path from $x_0$ to y contained in $D_1$, then there is an $(H,k-1)$-path from y to $x_0$ contained in $D_1$.

Let T be the subset of S such that $\{ z\in S\ :$ there is no $(H,k-1)$-path from z to $x_0$ in $D_2\}$. Observe that, by definition of T, there is an $(H,k-1)$-path from y to $x_0$ in $D_2$, for every $y\in S-T$. We will prove that $T\cup \{ x_0\}$ is an (H, k)-semikernel modulo $D_2$ in D.

Claim 1

$T\cup \{ x_0\}$ is an (H, k)-independent set in D.

Since S is an (H, k)-independent set in D and T is a subset of S, then T is an (H, k)-independent set in D. By definition of X, $x_0$ cannot reach any vertex of T by $(H,k-1)$-paths in D. Since S is an (H, k)-semikernel modulo $D_2$, $T\subseteq S$, and by definition of X, it follows that there is no $(H,k-1)$-path from any vertex of T to $x_0$ in $D_1$. By definition of T, there is no $(H,k-1)$-path from any vertex of T to $x_0$ in $D_2$. In addition, by Lemma  13, every $(H,k-1)$-walk of D is contained in either $D_1$ or $D_2$, we can conclude that $T\cup \{ x_0\}$ is an (H, k)-independent set in D.

Claim 2

For every $v\in V(D)-(T\cup \{ x_0\})$ if there is $u\in T\cup \{ x_0\}$ such that there exists an $(H,k-1)$-path from u to v contained in $D_1$, then there is $w\in T\cup \{ x_0\}$ such that there exists an $(H,k-1)$-path from v to w in D.

Let $v\in V(D)-(T\cup \{ x_0\})$ and $u\in T\cup \{ x_0\}$ such that there is there exists an $(H,k-1)$-path, $\alpha _1$ from u to v contained in $D_1$. Suppose, for the sake of contradiction, that there is no $y\in T\cup \{ x_0\}$ such that there exists an $(H,k-1)$-path from v to y in D. Consider the following two cases.

Case 1. $u\in T$.

Since S is an (H, k)-semikernel modulo $D_2$ in D and $T\subseteq S$, then there is $w\in S$ such that there is $\alpha _2$ an $(H,k-1)$-path from v to w contained in D. From above, the definition of X and by assumption, we have that $v\notin S\cup X$ and $w\in S-T$. By definition of T, there is $\alpha _3$ an $(H,k-1)$-path from w to $x_0$ in $D_2$. Since S is (H, k)-independent, there is no $(H,k-1)$-path from u to w in D, in addition, by assumption there is no $(H,k-1)$-path from v to $x_0$ nor from v to u in D, and by definition of X, there is no $(H,k-1)$-path from $x_0$ to w in D.

Note that $\alpha _1\cup \alpha _2$ is not an H-walk, otherwise, by Lemma  13, $\alpha _1\cup \alpha _2$ is contained in $D_i$, with $i\in \{ 1,2\}$. Moreover, by Remark  1, $\alpha _1$ and $\alpha _2$ are contained in $G_l$, for some $l\in \{ 1,\ldots ,t\}$. Since $G_l$ is an $(H,k-1)$-path-quasi-transitive digraph and there is no $(H,k-1)$-path from u to w in D, it follows that, there is $(H,k-1)$-path from w to u in $G_l$. Thus, $C=(u,v,w,u)$ is a 3-cycle in $G_l$, by hypothesis C has at least two symmetrical arcs, which is impossible. Hence, v is an H-obstruction to $\alpha _1\cup \alpha _2$. Verifying that $\alpha _2\cup \alpha _3$ is not an H-walk can be carried in an analogous way.

It follows that the hypotheses of Lemma 14 holds. Moreover, since D has no $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$, we have that $\alpha _1\cup \alpha _2\cup \alpha _3$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$. By hypothesis there is an $(H,k-1)$-path from u to $x_0$, contradicting Claim 1.

Case 2. $u=x_0$.

Since there is no $(H,k-1)$-path from v to $x_0$ and by choice of $x_0$, then $v\notin X$. By assumption, $v\in V(D)-(T\cup \{ x_0\})$ and there is no $(H,k-1)$-path from v to $x_0$ in D. This implies that $v\notin S-T$, even more, $v\notin S$. By definition of X and since $v\notin S$ and $v\notin X$, we have the existence of w in S such that there is $\alpha _2$ an $(H,k-1)$-path from v to w in D. It follows that $w\in S-T$. Therefore, there is $\alpha _3$ an $(H,k-1)$-path from w to $x_0$ in $D_2$. Since there is no $(H,k-1)$-path from $x_0$ to any vertex of S in D, in particular, there is no $(H,k-1)$-path from $x_0$ to w in D. In addition, by choice of v,  there is no $(H,k-1)$-path from v to $x_0$ in D.

On the other hand, as in the previous case $\alpha _1\cup \alpha _2$ and $\alpha _2\cup \alpha _3$ are not H-walks. It follows that, v is an H-obstruction to $\alpha _1\cup \alpha _2$ and w is an H-obstruction to $\alpha _2\cup \alpha _3$. Moreover, since $\alpha _3$ is contained in $D_2$ and $\alpha _1$ is contained in $D_1$, and there exist no $\xi _1\xi _2$-arc or $\xi _2\xi _1$-arc, it follows that $x_0$ is an H-obstruction to $\alpha _3\cup \alpha _1$. Thus, the hypotheses of Lemma 14 hold. Hence, $\alpha _1\cup \alpha _2 \cup \alpha _3$ is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$, which is a contradiction. This concludes the proof of Claim 2.

Therefore, $T\cup \{ x_0\}$ is an (H, k)-semikernel modulo $D_2$ in D. Thus $T\cup \{x_0\}\in V(D_{\mathcal {S}})$, even more, since $T\subseteq S$, $x_0\in X$ and for each $s\in S-T$ there is an $(H,k-1)$-path from s to $x_0$ in $D_2$ and there is no $(H,k-1)$-path from $x_0$ to s in D, then $(S,T\cup \{ x_0\})\in A(D_{\mathcal {S}})$. We obtain a contradiction to the choice of S.

We conclude that S is an (H, k)-kernel of D. $\square$

5 Some consequences

Corollary 16

Let H be a digraph, possibly with loops and D be an H-arc-colored digraph, such that every 3-cycle of $R_{(H,k-1)}(G_r)$ has at least two symmetrical arcs for every $r\in \{ 1,\ldots ,t\}$, $D_i$ is closed by cycles in $\xi _i$ and closed by $(H,k-1)$-walks in $\xi _i$, for each $i\in \{ 1,2\}$, every $\xi _1\xi _2$-arc and every $\xi _2\xi _1$-arc in $A({\mathscr {C}}_C(D))$ is not an arc of H, D has no $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$, and whenever there is a path from u to z which is a $(\xi _1,\xi ,\xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$, for some $u,z\in V(D)$, then there is an $(H,k-1)$-path from u to z.

If $k-1\ge diam(D)$, then D has an H-kernel.

Proof

By Theorem 15, D has an (H, k)-kernel, say N. By Proposition 5 it follows that N is an H-kernel of D. $\square$

In a m-colored digraph, a path is called properly colored whenever consecutive arcs have different color. Naturally, the reachability by properly colored paths can be defined, and with it the kernels by properly colored paths. Let H be the complete loopless digraph, and D be an H-colored digraph, with H-coloring $\zeta$. Observe that the H-paths in D are exactly the properly colored paths of D. Thus, if the hypotheses of Theorem 15 hold, then D has a kernel by properly colored paths with length at most k. Moreover, if $k-1\ge diam(D)$, then, by Corollary 16, D has kernel by properly colored paths.

Let H be a digraph possibly with loops, and D be an H-colored digraph without loops, with H coloring $\zeta$. We say that D is transitive by H-paths if whenever there are H-paths from u to v and from v to w in D, then there exists an H-path from u to w in D.

Let H be a digraph possibly with loops, D be an H-arc-colored digraph without loops, with H-coloring $\zeta$ and $\xi =\{C_1, C_2,\ldots , C_t\}$ $(t\ge 2)$ is a partition of V(H) such that $\{a\in A(D):\ \zeta (a)\in C_i\}\ne \emptyset$ and $G_i=D[\{ a\in A(D):\ \zeta (a)\in C_i\} ]$ is a subdigraph of D which is transitive by H-paths, for every $i\in \{ 1, 2,\ldots t\}$. Let $\{\xi _1,\xi _2\}$ be a partition of $\xi$, and $D_i$ be the spanning subdigraph of D such that $A(D_i) = \{ a \in A(D):\ \zeta (a)\in C_j\text { for some }C_j \in \xi _i\}$ for every $i \in \{1, 2\}$ .

Let $W = (u_0,\ldots ,u_l= v_0,\ldots , v_m=w_0,\ldots w_n=u_0)$ be a cycle. We say that W is a $(\xi _1,\xi ,\xi _2)$-H-subdivision of $\overrightarrow{C}_3$ if $W_1 = (u_0,W, u_l)$ is an H-path contained in $D_1$, $W_2 = (v_0,W, v_m)$ is an H-path and $W_3 = (w_0,W, w_n)$ is an H-path contained in $D_2$, where $v_0$, $w_0$ and $u_0$ are H-obstructions to $W_1\cup W_2$, $W_2\cup W_3$ and $W_3\cup W_1$, respectively. Analogously, let $T = (u_0,\ldots ,u_l= v_0,\ldots , v_m=w_0,\ldots w_n)$ be a path. We say that T is an $(\xi _1,\xi ,\xi _2)$-H-subdivision of $\overrightarrow{P}_4$ if $T_1 = (u_0,T, u_l)$ is an H-path contained in $D_1$, $T_2 = (v_0,T, v_m)$ is an H-path and $T_3 = (w_0,T, w_n)$ is an H-path contained in $D_2$, where $v_0$ and $w_0$ are H-obstructions to $T_1\cup T_2$ and $T_2\cup T_3$, respectively.

The following is the main result in [18], and we will prove it using Theorem 15.

Theorem 17

[18] Let H be a digraph and D an H-arc-colored digraph. Suppose that

• 1. For every $i \in \{ 1, 2\}$ and for every cycle $\gamma$ contained in $D_i$ there exists $C_m \in \xi _i$ such that $\gamma$ is contained in $G_m$.

• 2. For every $i \in \{1, 2\}$ and for every H-walk P contained in $D_i$ there exists $C_m \in \xi _i$ such that P is contained in $G_m$.

• 3. If either there exists a $\xi _1\xi _2$-arc or there exists a $\xi _2\xi _1$-arc in $A({\mathscr {C}}_C(D))$, say (a, b), then $(a, b)\notin A(H)$.

• 4. D does not contain a $(\xi _1, \xi , \xi _2)$-H-subdivision of $\overrightarrow{C}_3$.

• 5. If there exists a path from u to x which is a $(\xi _1, \xi , \xi _2)$-H-subdivision of $\overrightarrow{P}_4$, for some subset $\{ u, x\}$ of V(D), then there exists an H-path from u to x in D.

Then D has an H-kernel.

Proof

Let k, such that $diam (D)\le k-1$. By Proposition  5, every H-path of D is an $(H,k-1)$-path in D.

Since every subdigraph $G_i$ of D is transitive by H-paths, for every $i\in \{ 1,\ldots ,t\}$, then every $G_i$ is an $(H,k-1)$-path-quasi-transitive digraph. Moreover, if $C=(x,y,w,x)$ is a 3-cycle in $R_{(H,k-1)}(G_r)$, then C is symmetrical, for every $r\in \{ 1,\ldots ,t\}$.

It follows that every $(\xi _1, \xi , \xi _2)$-H-subdivision of $\overrightarrow{C}_3$ is a $(\xi _1, \xi , \xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{C}_3$, and every $(\xi _1, \xi , \xi _2)$-H-subdivision of $\overrightarrow{P}_4$ is a $(\xi _1, \xi , \xi _2)$-$(H,k-1)$-subdivision of $\overrightarrow{P}_4$. Note that all hypotheses of Theorem  15 hold. It follows that D has an (H, k)-kernel, say N, and by Proposition 5, N is an H-kernel of D. $\square$

In the particular case in which the arcs of H are all the loops of its vertices and $k-1\ge diam (D)$, we obtain the following Theorem, which is the main result in [6].

Theorem 18

[6] Suppose that for each $i\in \{1, 2\}$ and each cycle Z of D contained in $D_i$ there exists $C_j\in \xi _i$ such that $\zeta ( f )\in C_j$ for every $f\in A(Z)$. If D does not contain 3-colored $(\xi _1, \xi , \xi _2)$-subdivision of $\overrightarrow{C}_3$ and if (u, v, w, x) is a 3-colored $(\xi _1, \xi , \xi _2)$-subdivision of $\overrightarrow{P}_4$, now there is a monochromatic path between u and x in D, then D has a kernel by monochromatic paths.

6 Conclusions

In this work, we introduce the new concept of reachability by (H, k)-paths in H-arc-colored digraphs, which joins the reachability by H-paths and the reachability by k-paths. Both concepts have been extensively studied and are of great interest for many investigations and applications.

We focus on one of the many aspects of the reachability by (H, k)-paths, the (H, k)-kernels, for which we show that it is different from the concept of H-kernel. Following with the (H, k)-kernels, in Theorem 15, we give sufficient conditions for a partition $\xi$ of V(H) such that the arc set colored with the colors for every part of $\xi$ induces an $(H,k-1)$-path-quasi-transitive digraph in D, to imply the existence of an (H, k)-kernel in D. The proof of the main result of this work is based on the proof of Sands Sauer and Woodrow in [22], using this new concept of reachability, in the context of the H-arc-colored digraphs.

On the other hand, Fig. 3 shows an H-arc-colored digraph D, which is a quasi-transitive digraph but is not an (H, 2)-path-quasi-transitive digraph. Moreover, if we consider $D'_3$, the $\overrightarrow{C}_3$-arc-colored in Fig.  2, is an (H, 2)-path-quasi-transitive digraph which is not a quasi-transitive digraph. Observe that Theorem 15 requires a partition of the vertices of H such that the arcs colored with the colors of each class induce an $(H,k-1)$-path-quasi-transitive digraph, while the results in [14] and [5] require color partitions where the arcs colored with the colors of each class induce a quasi-transitive digraph. Therefore, the results in [14] and [5] cannot be deduced directly from Theorem 15 and vice versa.

Fig. 3

D is a quasi-transitive digraph but D is no (H, 2)-path-quasi-transitive digraph

Finally, we offer some applications to the concept of (H, k)-kernels. Let $\Sigma$ be an alphabet, $L \subset \Sigma ^*$ be a language, D a digraph and $\zeta : A(D)\rightarrow \Sigma$ be an arc-coloring of D with the letters of $\Sigma$. A path $(x_0,x_1,\ldots ,x_n)$ in D is an (L, k)-path if $(\zeta ((x_0,x_1)),\zeta ((x_1,x_2)),\ldots ,\zeta ((x_{n-1},x_n))$ is a word with length at most k in L. Hence, with this notion, an (L, k)-kernel of D is a subset of vertices of D such that, there is independent by (L, k)-paths and absorbent by $(L,k-1)$-paths. For example, if $L=\{ 0^n,1^n:\ n\ge 0\}$ and $k\ge 3$, then every (L, k)-path is a sequence of 0’s or 1’s with length at most k. Thus, an (L, k)-kernel is subset of vertices N such that there is no sequence of 0’s or 1’s with length at least k between two vertices of N and for every vertex not in N there is a sequence of 0s or 1s with length at most $k-1$ to one vertex in N.

On the other hand, let D be an H-arc-colored digraph where D is a directed network of computers, each color of H is a way to encrypt messages and H encodes the allowed changes to forward encrypted messages. Notice that an (H, k)-path is a sequence with at most $k+1$ computers in which a message can travel, from the first computer to the last, respecting the allowed changes in H. Thus, an (H, k, l)-kernel N of D is a set of computers on the network such that they cannot send messages to each other, using at most $k-2$ intermediaries but every computer not in N can send messages to one in N with at most $l-1$ intermediaries.

To conclude, it seems relevant to note that this new reachability can be used to model several classic connectivity problems.