Find in Library

Let D be a digraph, we say that it is an m-coloured digraph if the arcs of D are coloured with at most m-colours. An (u,v) arc is symmetrical if (v,u) is also an arc of D. A directed path (resp. directed cycle) is monochromatic if all of its arcs are coloured with the same colour, and it is quasi-monochromatic if at most one of its arcs is coloured with different colour. A set AN⊂V(D) is an A-kernel if it satisfies the following conditions: (1) For every pair of vertices x,y∈AN, there is no arc between them, we say that AN is independent. (2) For every x∉AN, there exists an xy-monochromatic path for some y∈AN, it means AN is absorbent by monochromatic paths. An infinite sequence of different vertices (x1,x2,x3,…) such that (xi,xi+1)∈A(D) for every i∈N will be called an infinite outward path. In this paper we introduce the definitions of A-kernel and A-semikernel, but also we prove the following theorem: Let D be a possibly infinite digraph, if every directed cycle and every infinite outward path has two consecutive vertices, say xi and xi+1, such that there exists an xi+1xi-monochromatic path, then D has an A-kernel.