کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650236 1342481 2008 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Kernels in edge-coloured orientations of nearly complete graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Kernels in edge-coloured orientations of nearly complete graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 20, 28 October 2008, Pages 4599–4607
نویسندگان
,