Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs

100%

Casas-Bautista E., Galeana-Sánchez H., Rojas-Monroy R.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 3

493-507

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 γ = (u0, u1, . . . , un), such that ui ≠ uj if i ≠ j and for every i ∈ {0, 1, . . . , n} there is a uiui+1-monochromatic path in D and there is no ui+1ui-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 {C1,C2} is a partition of C, the set of colours of D, and Di will be the spanning subdigraph of D such that A(Di) = {a ∈ A(D) | colour(a) ∈ Ci}. 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 we obtain an extension of the original result by B. Sands, N. Sauer and R. Woodrow that asserts: Every 2-coloured digraph has a kernel by monochromatic paths. Also, we extend other results obtained before where it is proved that under some conditions an m-coloured digraph has no γ-cycles.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Casas-Bautista E.

1 Galeana-Sánchez H.

1 Rojas-Monroy R.

1 2013

Wyniki wyszukiwania

γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs