Restricted domination in Quasi-transitive and 3-Quasi-transitive digraphs

Let H be a digraph possibly with loops and D a digraph without loops with a coloring of its arcs c : A ( D ) → V ( H ) ( D is said to be an H -colored digraph). A directed path W in D is said to be an H -path if and only if the consecutive colors encountered on W form a directed walk in H . A subset N of vertices of D is said to be an H -kernel if (1) for every pair of different vertices in N there is no H -path between them and (2) for every vertex u in V ( D ) ∖ N there exists an H -path in D from u to N . Under this definition an H -kernel is a kernel whenever A ( H ) = 0 ; an H -kernel is a kernel by monochromatic paths whenever A ( H ) = { ( u , u ) : u ∈ V ( H ) } ; an H -kernel is a properly colored kernel whenever H has no loops and an H -kernel is a kernel by rainbow paths whenever H has no directed cycles. Let k be an integer, with k ≥ 2 . D is k -quasi-transitive if for every pair of vertices u and v of D , the existence of a directed path of length k from u to v implies that { ( u , v ) , ( v , u ) } ∩ A ( D ) ≠ 0 . In Galeana-Sanchez and O’Reilly-Regueiro (2013), in Delgado-Escalante et al. (2018) and in Galeana-Sanchez and Rojas-Monroy (2006) the authors establish sufficient conditions to guarantee the existence of kernels by monochromatic paths in 3-quasi-transitive digraphs, the existence of properly colored kernels in 2-quasi-transitive digraphs and the existence of kernels in 2-quasi-transitive digraphs, respectively. In this paper we investigate the problem of the existence of H -kernels in quasi-transitive and in 3-quasi-transitive digraphs by means of a partition of V ( H ) . We give some examples which show that each hypothesis in the main result for quasi-transitive digraphs is tight.