γ-cycles and transivity by monochromatic paths in arc-coloured digraphs
Enrique Casas-Bautista, Hortensia Galeana‐Sánchez, Rocı́o Rojas-Monroy · Discussiones Mathematicae Graph Theory · 2013
We call the digraph D an m-coloured digraph if its arcs are coloured with m colours.If D is an m-coloured digraph and a ∈ A(D), colour(a) will denote the colour has been used on a.A path (or a cycle) is called monochromatic if all of its arcs are coloured alike.A γ-cycle in D is a sequence of vertices, say γ = (u 0 , u 1 , . . ., u n ), such that u i = u j if i = j and for every i ∈ {0, 1, . . ., n} there is a u i u i+1 -monochromatic path in D and there is no u i+1 u i -monochromatic path in D (the indices of the vertices will be taken mod n+1).A set N ⊆ V (D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u, v ∈ N there is no monochromatic 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 path.Let D be a finite m-coloured digraph.Suppose that {C 1 , C 2 } is a partition of C, the set of colours of D, and D i will be the spanning subdigraph of D such that A(D i ) = {a ∈ A(D) | colour(a) ∈ C i }.In this paper, we give some sufficient conditions for the existence of a kernel by monochromatic paths in a digraph with the structure mentioned above.In particular 494