- Tytuł:
- Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs
- Autorzy:
-
Galeana-Sánchez, Hortensia
Rojas-Monroy, R.
Zavala, B. - Powiązania:
- https://bibliotekanauki.pl/articles/744061.pdf
- Data publikacji:
- 2010
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
m-coloured quasi-transitive digraph
kernel by monochromatic paths - Opis:
- Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. We call the digraph D an m-coloured digraph if each arc of D is coloured by an element of {1,2,...,m} where m ≥ 1. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if there is no monochromatic path between two vertices of N and if for every vertex v not in N there is a monochromatic path from v to some vertex in N. A digraph D is called a quasi-transitive digraph if (u,v) ∈ A(D) and (v,w) ∈ A(D) implies (u,w) ∈ A(D) or (w,u) ∈ A(D). We prove that if D is an m-coloured quasi-transitive digraph such that for every vertex u of D the set of arcs that have u as initial end point is monochromatic and D contains no C₃ (the 3-coloured directed cycle of length 3), then D has a kernel by monochromatic paths.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2010, 30, 4; 545-553
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł