H-kernels by walks in H-colored digraphs and the color-class digraph

Abstract

Let H be a digraph possibly with loops and D a finite digraph without loops whose arcs are colored with the vertices of H (D is an H-colored digraph). V(D) and A(D) will denote the sets of vertices and arcs of D respectively. For an arc (z1,z2) of D we will denote by cD(z1,z2) its color. A directed walk (respectively directed path) (v1, v2,…,vn) in D is an H-walk (respectively H-path) if and only if (cD(v1,v2), cD(v2,v3),…,cD(vn−1,vn)) is a directed walk in H. A set K⊆V(D) is an H-kernel by walks (respectively H-kernel) if for every pair of different vertices in K there is no H-walk (respectively H-path) between them, and for every vertex u∈V(D)∖K there exists v∈K such that there exists an H-walk (respectively H-path) from u to v in D. Let D be an arc-colored digraph. The color-class digraph of D, denoted by CC(D), is defined as follows: the vertices of the color-class digraph are the colors represented in the arcs of D and (i,j) ∈ A(CC(D)) if and only if there exist two arcs namely (u,v) ∈ A(D) colored i and (v,w) ∈ A(D) colored j. In this paper we relate the concepts discussed above, the color-class digraph and the H-coloration of D, in order to prove the existence of an H-kernel by walks (respectively H-kernel).

Keywords

• H-kernel
• Kernel
• Kernel by monochromatic paths
• Color-class digraph