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ę "monochromatic paths" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-15 z 15
    Tytuł:
    Monochromatic cycles and monochromatic paths in arc-colored digraphs
    Autorzy:
    Galeana-Sánchez, Hortensia
    Gaytán-Gómez, Guadalupe
    Rojas-Monroy, Rocío
    Powiązania:
    https://bibliotekanauki.pl/articles/743875.pdf
    Data publikacji:
    2011
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    kernel
    kernel by monochromatic paths
    monochromatic cycles
    Opis:
    We call the digraph D an m-colored digraph if the arcs of D are colored with m colors. A path (or a cycle) is called monochromatic if all of its arcs are colored alike. A cycle is called a quasi-monochromatic cycle if with at most one exception all of its arcs are colored alike. A subdigraph H in D is called rainbow if all its arcs have different colors. 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. The closure of D, denoted by ℭ(D), is the m-colored multidigraph defined as follows: V(ℭ(D)) = V(D), A(ℭ(D)) = A(D)∪{(u,v) with color i | there exists a uv-monochromatic path colored i contained in D}. Notice that for any digraph D, ℭ (ℭ(D)) ≅ ℭ(D) and D has a kernel by monochromatic paths if and only if ℭ(D) has a kernel.
    Let D be a finite m-colored digraph. Suppose that there is a partition C = C₁ ∪ C₂ of the set of colors of D such that every cycle in the subdigraph $D[C_i]$ spanned by the arcs with colors in $C_i$ is monochromatic. We show that if ℭ(D) does not contain neither rainbow triangles nor rainbow P₃ involving colors of both C₁ and C₂, then D has a kernel by monochromatic paths.
    This result is a wide extension of the original result by Sands, Sauer and Woodrow that asserts: Every 2-colored digraph has a kernel by monochromatic paths (since in this case there are no rainbow triangles in ℭ(D)).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2011, 31, 2; 283-292
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On monochromatic paths and bicolored subdigraphs in arc-colored tournaments
    Autorzy:
    Delgado-Escalante, Pietra
    Galeana-Sánchez, Hortensia
    Powiązania:
    https://bibliotekanauki.pl/articles/743637.pdf
    Data publikacji:
    2011
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    kernel
    kernel by monochromatic paths
    tournament
    Opis:
    Consider an arc-colored digraph. A set of vertices N is a kernel by monochromatic paths if all pairs of distinct vertices of N have no monochromatic directed path between them and if for every vertex v not in N there exists n ∈ N such that there is a monochromatic directed path from v to n. In this paper we prove different sufficient conditions which imply that an arc-colored tournament has a kernel by monochromatic paths. Our conditions concerns to some subdigraphs of T and its quasimonochromatic and bicolor coloration. We also prove that our conditions are not mutually implied and that they are not implied by those known previously. Besides some open problems are proposed.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2011, 31, 4; 791-820
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Monochromatic paths and monochromatic sets of arcs in bipartite tournaments
    Autorzy:
    Galeana-Sánchez, Hortensia
    Rojas-Monroy, R.
    Zavala, B.
    Powiązania:
    https://bibliotekanauki.pl/articles/744396.pdf
    Data publikacji:
    2009
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    m-coloured bipartite tournaments
    kernel by monochromatic paths
    semikernel of D modulo i by monochromatic paths
    Opis:
    We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours and all of them are used. 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 for every pair of vertices there is no monochromatic path between them and for every vertex v in V(D)∖N there is a monochromatic path from v to some vertex in N. We denote by A⁺(u) the set of arcs of D that have u as the initial endpoint.
    In this paper we introduce the concept of semikernel modulo i by monochromatic paths of an m-coloured digraph. This concept allow us to find sufficient conditions for the existence of a kernel by monochromatic paths in an m-coloured digraph. In particular we deal with bipartite tournaments such that A⁺(z) is monochromatic for each z ∈ V(D).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2009, 29, 2; 349-360
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Kernels and cycles subdivisions in arc-colored tournaments
    Autorzy:
    Delgado-Escalante, Pietra
    Galeana-Sánchez, Hortensia
    Powiązania:
    https://bibliotekanauki.pl/articles/743117.pdf
    Data publikacji:
    2009
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    kernel
    kernel by monochromatic paths
    tournament
    Opis:
    Let D be a digraph. D is said to be an m-colored digraph if the arcs of D are colored with m colors. A path P in D is called monochromatic if all of its arcs are colored alike. Let D be an m-colored digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following conditions: a) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them; and b) for every vertex x ∈ V(D)-N there is a vertex n ∈ N such that there is an xn-monochromatic directed path in D. In this paper we prove that if T is an arc-colored tournament which does not contain certain subdivisions of cycles then it possesses a kernel by monochromatic paths. These results generalize a well known sufficient condition for the existence of a kernel by monochromatic paths obtained by Shen Minggang in 1988 and another one obtained by Hahn et al. in 2004. Some open problems are proposed.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2009, 29, 1; 101-117
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Monochromatic paths and quasi-monochromatic cycles in edge-coloured bipartite tournaments
    Autorzy:
    Galeana-Sanchez, Hortensia
    Rojas-Monroy, Rocío
    Powiązania:
    https://bibliotekanauki.pl/articles/743320.pdf
    Data publikacji:
    2008
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    kernel
    kernel by monochromatic paths
    bipartite tournament
    Opis:
    We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. A directed cycle is called quasi-monochromatic if with at most one exception all of its arcs are coloured alike. 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 directed 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 directed path.
    In this paper it is proved that if D is an m-coloured bipartite tournament such that: every directed cycle of length 4 is quasi-monochromatic, every directed cycle of length 6 is monochromatic, and D has no induced particular 6-element bipartite tournament T̃₆, then D has a kernel by monochromatic paths.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2008, 28, 2; 285-306
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Monochromatic kernel-perfectness of special classes of digraphs
    Autorzy:
    Galeana-Sánchez, Hortensia
    Ramírez, Luis
    Powiązania:
    https://bibliotekanauki.pl/articles/743807.pdf
    Data publikacji:
    2007
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    kernel
    kernel by monochromatic paths
    composition
    duplication
    Opis:
    In this paper, we introduce the concept of monochromatic kernel-perfect digraph, and we prove the following two results:
    (1) If D is a digraph without monochromatic directed cycles, then D and each $α_v,v ∈ V(D)$ are monochromatic kernel-perfect digraphs if and only if the composition over D of $(α_v)_{v ∈ V(D)}$ is a monochromatic kernel-perfect digraph.
    (2) D is a monochromatic kernel-perfect digraph if and only if for any B ⊆ V(D), the duplication of D over B, $D^B$, is a monochromatic kernel-perfect digraph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2007, 27, 3; 389-400
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    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ł
    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ł
    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ł
    Tytuł:
    Kernels in edge coloured line digraph
    Autorzy:
    Galeana-Sánchez, H.
    Pastrana Ramírez, L.
    Powiązania:
    https://bibliotekanauki.pl/articles/744205.pdf
    Data publikacji:
    1998
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    kernel
    kernel by monochromatic paths
    line digraph
    edge coloured digraph
    Opis:
    We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the two following conditions (i) for every pair of different vertices u, v ∈ N there is no monochromatic directed 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 directed path.
    Let D be an m-coloured digraph and L(D) its line digraph. The inner m-coloration of L(D) is the edge coloration of L(D) defined as follows: If h is an arc of D of colour c, then any arc of the form (x,h) in L(D) also has colour c.
    In this paper it is proved that if D is an m-coloured digraph without monochromatic directed cycles, then the number of kernels by monochromatic paths in D is equal to the number of kernels by monochromatic paths in the inner edge coloration of L(D).
    Źródło:
    Discussiones Mathematicae Graph Theory; 1998, 18, 1; 91-98
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Kernels in monochromatic path digraphs
    Autorzy:
    Galeana-Sánchez, Hortensia
    Ramírez, Laura
    Mejía, Hugo
    Powiązania:
    https://bibliotekanauki.pl/articles/744174.pdf
    Data publikacji:
    2005
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    kernel
    line digraph
    kernel by monochromatic paths
    monochromatic path digraph
    edge-coloured digraph
    Opis:
    We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. Let D be an m-coloured digraph. 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 directed path between them and
    (ii) for each vertex x ∈ (V(D)-N) there is a vertex y ∈ N such that there is an xy-monochromatic directed path.
    In this paper is defined the monochromatic path digraph of D, MP(D), and the inner m-colouration of MP(D). Also it is proved that if D is an m-coloured digraph without monochromatic directed cycles, then the number of kernels by monochromatic paths in D is equal to the number of kernels by monochromatic paths in the inner m-colouration of MP(D). A previous result is generalized.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2005, 25, 3; 407-417
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs
    Autorzy:
    Galeana-Sánchez, Hortensia
    Rojas-Monroy, R.
    Zavala, B.
    Powiązania:
    https://bibliotekanauki.pl/articles/744398.pdf
    Data publikacji:
    2009
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    m-coloured digraph
    3-quasitransitive digraph
    kernel by monochromatic paths
    γ-cycle
    quasi-monochromatic digraph
    Opis:
    We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. 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 for every pair of vertices of N there is no monochromatic path between them and for every vertex v ∉ N there is a monochromatic path from v to N. We denote by A⁺(u) the set of arcs of D that have u as the initial vertex. We prove that if D is an m-coloured 3-quasitransitive digraph such that for every vertex u of D, A⁺(u) is monochromatic and D satisfies some colouring conditions over one subdigraph of D of order 3 and two subdigraphs of D of order 4, then D has a kernel by monochromatic paths.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2009, 29, 2; 337-347
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs
    Autorzy:
    Campero-Alonzo, José Manuel
    Sánchez-López, Rocío
    Powiązania:
    https://bibliotekanauki.pl/articles/32083861.pdf
    Data publikacji:
    2021-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    quasi-transitive digraph
    kernel by monochromatic paths
    alternating kernel
    obstruction
    H-kernel
    Opis:
    Let $H$ be a digraph (possibly with loops) and $D$ a digraph without loops whose arcs are colored with the vertices of $H$ ($D$ is said to be an $H$-colored digraph). For an arc $(x, y)$ of $D$, its color is denoted by $c(x, y)$. A directed path $W = (v_0, . . ., v_n)$ in an $H$-colored digraph $D$ will be called $H$-path if and only if $(c(v_0, v_1), . . ., c(v_{n−1}, v_n))$ is a directed walk in $H$. In $W$, we will say that there is an obstruction on $v_i$ if $(c(v_{i−1}, v_i), c(v_i, v_{i+1})) ∉ A(H)$ (if $v_0 = v_n$ we will take indices modulo $n$). A subset $N$ of $V(D)$ is said to be an $H$-kernel in $D$ if for every pair of different vertices in $N$ there is no $H$-path between them, and for every vertex $u$ in \(V(D) \backslash N\) there exists an $H$-path in $D$ from $u$ to $N$. Let $D$ be an arc-colored digraph. The color-class digraph of $D,\mathcal{C}_C(D)$, is the digraph such that $V(\mathcal{C}_C(D)) = \{c(a) : a ∈ A(D)\}$ and $(i, j) ∈ A(\mathcal{C}_C(D))$ if and only if there exist two arcs, namely $(u, v)$ and $(v, w)$ in $D$, such that $c(u, v) = i$ and $c(v, w) = j$. The main result establishes that if $D = D_1 ∪ D_2$ is an $H$-colored digraph which is a union of asymmetric quasi-transitive digraphs and $\{V_1, . . ., V_k\}$ is a partition of $V(\mathcal{C}_C(D))$ with a property $P^\ast$ such that 1. $V_i$ is a quasi-transitive $V_i$-class for every i in $\{1, . . ., k\}$, 2. either \(D[\{a ∈ A(D) : c(a) ∈ V_i\}]\) is a subdigraph of $D_1$ or it is a sudigraph of $D_2$ for every $i$ in $\{1, . . ., k\}$, 3. $D_i$ has no infinite outward path for every $i$ in $\{1, 2\}$, 4. every cycle of length three in $D$ has at most two obstructions, then $D$ has an $H$-kernel. Some results with respect to the existence of kernels by monochromatic paths in finite digraphs will be deduced from the main result.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 2; 391-408
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Kernels by Monochromatic Paths and Color-Perfect Digraphs
    Autorzy:
    Galeana-Śanchez, Hortensia
    Sánchez-López, Rocío
    Powiązania:
    https://bibliotekanauki.pl/articles/31340961.pdf
    Data publikacji:
    2016-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    kernel
    kernel perfect digraph
    kernel by monochromatic paths
    color-class digraph
    quasi color-perfect digraph
    color-perfect digraph
    Opis:
    For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) \ N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different color, then a kernel by monochromatic paths is said to be a kernel. Two associated digraphs to an arc-colored digraph are the closure and the color-class digraph C(D). In this paper we will approach an mp-kernel via the closure of induced subdigraphs of D which have the property of having few colors in their arcs with respect to D. We will introduce the concept of color-perfect digraph and we are going to prove that if D is an arc-colored digraph such that D is a quasi color-perfect digraph and C(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 2; 309-321
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-15 z 15

      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