Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650236 | Discrete Mathematics | 2008 | 9 Pages |
We call the digraph D an orientation of a graph G if D is obtained from G by the orientation of each edge of G in exactly one of the two possible directions. The digraph D is an m-coloured digraph if the arcs of D are coloured with m-colours.Let D be an m-coloured digraph. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike.A set N⊆V(D)N⊆V(D) is said to be a kernel by monochromatic paths if it satisfies the two following conditions: (i) for every pair of different vertices u,v∈Nu,v∈N there is no monochromatic directed path between them and (ii) for every vertex x∈V(D)-Nx∈V(D)-N there is a vertex y∈Ny∈N such that there is an xy-monochromatic directed path.In this paper we obtain sufficient conditions for an m -coloured orientation of a graph obtained from KnKn by deletion of the arcs of K1,rK1,r(0⩽r⩽n-1)(0⩽r⩽n-1) to have a kernel by monochromatic.