Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "γ-cycle" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-2 z 2
    Tytuł:
    γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs
    Autorzy:
    Casas-Bautista, Enrique
    Galeana-Sánchez, Hortensia
    Rojas-Monroy, Rocío
    Powiązania:
    https://bibliotekanauki.pl/articles/30146505.pdf
    Data publikacji:
    2013-07-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    digraph
    kernel
    kernel by monochromatic paths
    γ-cycle
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 3; 493-507
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    $ \gamma $-Cycles In Arc-Colored Digraphs
    Autorzy:
    Galeana-Sánchez, Hortensia
    Gaytán-Gómez, Guadalupe
    Rojas-Monroy, Rocío
    Powiązania:
    https://bibliotekanauki.pl/articles/31341163.pdf
    Data publikacji:
    2016-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    digraph
    kernel
    kernel by monochromatic paths
    γ-cycle
    Opis:
    We call a digraph $D$ an $m$-colored digraph if the arcs of $D$ are colored with $m$ colors. A directed path (or a directed cycle) is called monochromatic if all of its arcs are colored alike. A subdigraph $H$ in $D$ is called rainbow if all of its arcs have different colors. A set $ N \subseteq V (D) $ is said to be a kernel by monochromatic paths of $D$ if it satisfies the two following conditions: (i) for every pair of different vertices $ u, v \in N $ there is no monochromatic path in $D$ between them, and (ii) for every vertex $ x \in V (D) − N $ there is a vertex $ y \in N $ such that there is an $xy$-monochromatic path in $D$. A $\gamma$-cycle in $D$ is a sequence of different vertices $ \gamma = (u_0, u_1, . . ., u_n, u_0)$ such that for every $ i \in {0, 1, . . ., n}$: (i) there is a $u_i u_{i+1}$-monochromatic path, and (ii) there is no $u_{i+1}u_i$-monochromatic path. The addition over the indices of the vertices of $ \gamma $ is taken modulo $(n + 1)$. If $D$ is an $m$-colored digraph, then the closure of $D$, denoted by $ \mathfrak{C}(D)$, is the $m$-colored multidigraph defined as follows: $ V (\mathfrak{C} (D)) = V (D) $, $ A( \mathfrak{C} (D)) = A(D) \cup \{ (u, v) $ with color $i$ | there exists a $uv$-monochromatic path colored $i$ contained in $D \} $. In this work, we prove the following result. Let $D$ be a finite m-colored digraph which satisfies that there is a partition $ C = C_1 \cup C_2 $ of the set of colors of $D$ such that: (1) $ D[ \hat{C}_i ] $ (the subdigraph spanned by the arcs with colors in $ C_i) $ contains no $ \gamma $-cycles for $ i \in {1, 2} $; (2) If $ \mathfrak{C}(D) $ contains a rainbow $ C_3 = (x_0, z, w, x_0) $ involving colors of $ C_1 $ and $ C_2 $, then $ (x_0, w) \in A(\mathfrak{C} (D)) $ or $ (z, x_0) \in A( \mathfrak{C} (D)) $; (3) If $ \mathfrak{C}(D) $ contains a rainbow $ P_3 = (u, z, w, x_0) $ involving colors of $ C_1 $ and $ C_2 $, then at least one of the following pairs of vertices is an arc in $ \mathfrak{C} (D) $: $ (u, w) $, $ (w, u) $, $ (x_0, u) $, $ (u, x_0) $, $ (x_0, w) $, $ (z, u) $, $ (z, x_0) $. Then $D$ has a kernel by monochromatic paths. This theorem can be applied to all those digraphs that contain no $ \gamma $-cycles. Generalizations of many previous results are obtained as a direct consequence of this theorem.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 1; 103-116
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-2 z 2

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies