Kernels in edge-coloured orientations of nearly complete graphs |
| |
Authors: | H Galeana-Sánchez |
| |
Institution: | Instituto de Matemáticas, Universidad Nacional Autónoma de México, Ciudad Universitaria, México D.F. 04510, México |
| |
Abstract: | 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) 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∈N there is no monochromatic directed path between them and (ii) for every vertex x∈V(D)-N there is a vertex y∈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 Kn by deletion of the arcs of K1,r(0?r?n-1) to have a kernel by monochromatic. |
| |
Keywords: | 05C20 |
本文献已被 ScienceDirect 等数据库收录! |
|