- Tytuł:
- Kernels by monochromatic paths and the color-class digraph
- Autorzy:
- Galeana-Sánchez, Hortensia
- Powiązania:
- https://bibliotekanauki.pl/articles/743879.pdf
- Data publikacji:
- 2011
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
kernel
kernel by monochromatic paths
the color-class digraph - Opis:
-
An m-colored digraph is a digraph whose arcs are colored with m colors. A directed path is monochromatic when its arcs are colored alike.
A set S ⊆ V(D) is a kernel by monochromatic paths whenever the two following conditions hold:
1. For any x,y ∈ S, x ≠ y, there is no monochromatic directed path between them.
2. For each z ∈ (V(D)-S) there exists a zS-monochromatic directed path.
In this paper it is introduced the concept of color-class digraph to prove that if D is an m-colored strongly connected finite digraph such that:
(i) Every closed directed walk has an even number of color changes,
(ii) Every directed walk starting and ending with the same color has an even number of color changes, then D has a kernel by monochromatic paths.
This result generalizes a classical result by Sands, Sauer and Woodrow which asserts that any 2-colored digraph has a kernel by monochromatic paths, in case that the digraph D be a strongly connected digraph. - Źródło:
-
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 273-281
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł