γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs
Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 3, p. 493.
Voir la notice de l'article dans European Digital Mathematics Library
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.
Classification :
05C15, 05C20, 05C38, 05C69
Mots-clés : digraph, kernel, kernel by monochromatic paths, γ-cycle, -cycle
Mots-clés : digraph, kernel, kernel by monochromatic paths, γ-cycle, -cycle
@article{DMGT_2013__33_3_268248, author = {Enrique Casas-Bautista and Hortensia Galeana-S\'anchez and Roc{\'\i}o Rojas-Monroy}, title = {\ensuremath{\gamma}-Cycles {And} {Transitivity} {By} {Monochromatic} {Paths} {In} {Arc-Coloured} {Digraphs}}, journal = {Discussiones Mathematicae Graph Theory}, pages = {493}, publisher = {mathdoc}, volume = {33}, number = {3}, year = {2013}, zbl = {1275.05025}, language = {en}, url = {https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268248/} }
TY - JOUR AU - Enrique Casas-Bautista AU - Hortensia Galeana-Sánchez AU - Rocío Rojas-Monroy TI - γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs JO - Discussiones Mathematicae Graph Theory PY - 2013 SP - 493 VL - 33 IS - 3 PB - mathdoc UR - https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268248/ LA - en ID - DMGT_2013__33_3_268248 ER -
%0 Journal Article %A Enrique Casas-Bautista %A Hortensia Galeana-Sánchez %A Rocío Rojas-Monroy %T γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs %J Discussiones Mathematicae Graph Theory %D 2013 %P 493 %V 33 %N 3 %I mathdoc %U https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268248/ %G en %F DMGT_2013__33_3_268248
Enrique Casas-Bautista; Hortensia Galeana-Sánchez; Rocío Rojas-Monroy. γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 3, p. 493. https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268248/