Article ID Journal Published Year Pages File Type
4646531 AKCE International Journal of Graphs and Combinatorics 2015 5 Pages PDF
Abstract

Let DD be a digraph, we say that it is an mm-coloured digraph if the arcs of DD are coloured with at most mm-colours. An (u,v)(u,v) arc is symmetrical if (v,u)(v,u) is also an arc of DD. 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)AN⊂V(D) is an AA-kernel if it satisfies the following conditions: (1)For every pair of vertices x,y∈ANx,y∈AN, there is no arc between them, we say that ANAN is independent.(2)For every x∉ANx∉AN, there exists an xyxy-monochromatic path for some y∈ANy∈AN, it means ANAN is absorbent by monochromatic paths. An infinite sequence of different vertices (x1,x2,x3,…)(x1,x2,x3,…) such that (xi,xi+1)∈A(D)(xi,xi+1)∈A(D) for every i∈Ni∈N will be called an infinite outward path.In this paper we introduce the definitions of AA-kernel and AA-semikernel, but also we prove the following theorem: Let DD be a possibly infinite digraph, if every directed cycle and every infinite outward path has two consecutive vertices, say xixi and xi+1xi+1, such that there exists an xi+1xixi+1xi-monochromatic path, then DD has an AA-kernel.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,