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 ( z 1 , z 2 ) of D we will denote by c D ( z 1 , z 2 ) its color. A directed walk (respectively directed path) ( v 1 , v 2 , … , v n ) in D is an H -walk (respectively H -path) if and only if ( c D ( v 1 , v 2 ), c D ( v 2 , v 3 ) , … , c D ( v n ? 1 , v n ) ) 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 C C ( 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( C C ( 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).
展开▼
