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

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-10 z 10
    Tytuł:
    k-kernels in generalizations of transitive digraphs
    Autorzy:
    Galeana-Sánchez, Hortensia
    Hernández-Cruz, César
    Powiązania:
    https://bibliotekanauki.pl/articles/743887.pdf
    Data publikacji:
    2011
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    digraph
    kernel
    (k,l)-kernel
    k-kernel
    transitive digraph
    quasi-transitive digraph
    right-pretransitive digraph
    left-pretransitive digraph
    pretransitive digraph
    Opis:
    Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.
    A (k,l)-kernel N of D is a k-independent set of vertices (if u,v ∈ N, u ≠ v, then d(u,v), d(v,u) ≥ k) and l-absorbent (if u ∈ V(D)-N then there exists v ∈ N such that d(u,v) ≤ l). A k-kernel is a (k,k-1)-kernel. Quasi-transitive, right-pretransitive and left-pretransitive digraphs are generalizations of transitive digraphs. In this paper the following results are proved: Let D be a right-(left-) pretransitive strong digraph such that every directed triangle of D is symmetrical, then D has a k-kernel for every integer k ≥ 3; the result is also valid for non-strong digraphs in the right-pretransitive case. We also give a proof of the fact that every quasi-transitive digraph has a (k,l)-kernel for every integers k > l ≥ 3 or k = 3 and l = 2.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2011, 31, 2; 293-312
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect
    Autorzy:
    Galeana-Sánchez, Hortensia
    García-Ruvalcaba, José
    Powiązania:
    https://bibliotekanauki.pl/articles/743429.pdf
    Data publikacji:
    2001
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    kernel
    kernel-perfect digraph
    m-coloured digraph
    Opis:
    A digraph D is called a kernel-perfect digraph or KP-digraph when every induced subdigraph of D has a kernel.
    We call the digraph D an m-coloured digraph if the arcs of D are coloured with m distinct colours. A path P is monochromatic in D if all of its arcs are coloured alike in D. The closure of D, denoted by ζ(D), is the m-coloured digraph defined as follows:
    V( ζ(D)) = V(D), and
    A( ζ(D)) = ∪_{i} {(u,v) with colour i: there exists a monochromatic path of colour i from the vertex u to the vertex v contained in D}.
    We will denoted by T₃ and C₃, the transitive tournament of order 3 and the 3-directed-cycle respectively; both of whose arcs are coloured with three different colours.
    Let G be a simple graph. By an m-orientation-coloration of G we mean an m-coloured digraph which is an asymmetric orientation of G.
    By the class E we mean the set of all the simple graphs G that for any m-orientation-coloration D without C₃ or T₃, we have that ζ(D) is a KP-digraph.
    In this paper we prove that if G is a hamiltonian graph of class E, then its complement has at most one nontrivial component, and this component is K₃ or a star.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2001, 21, 1; 77-93
    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ł:
    (k,l)-kernels, (k,l)-semikernels, k-Grundy functions and duality for state splittings
    Autorzy:
    Galeana-Sánchez, Hortensia
    Gómez, Ricardo
    Powiązania:
    https://bibliotekanauki.pl/articles/743799.pdf
    Data publikacji:
    2007
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    state splitting
    line digraph
    kernel
    Grundy function
    duality
    Opis:
    Line digraphs can be obtained by sequences of state splittings, a particular kind of operation widely used in symbolic dynamics [12]. Properties of line digraphs inherited from the source have been studied, for instance in [7] Harminc showed that the cardinalities of the sets of kernels and solutions (kernel's dual definition) of a digraph and its line digraph coincide. We extend this for (k,l)-kernels in the context of state splittings and also look at (k,l)-semikernels, k-Grundy functions and their duals.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2007, 27, 2; 359-371
    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ł:
    Cyclically k-partite digraphs and k-kernels
    Autorzy:
    Galeana-Sánchez, Hortensia
    Hernández-Cruz, César
    Powiązania:
    https://bibliotekanauki.pl/articles/743833.pdf
    Data publikacji:
    2011
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    digraph
    kernel
    (k,l)-kernel
    k-kernel
    cyclically k-partite
    Opis:
    Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.
    A (k,l)-kernel N of D is a k-independent set of vertices (if u,v ∈ N then d(u,v) ≥ k) and l-absorbent (if u ∈ V(D)-N then there exists v ∈ N such that d(u,v) ≤ l). A k-kernel is a (k,k-1)-kernel. A digraph D is cyclically k-partite if there exists a partition ${V_i}_{i = 0}^{k-1}$ of V(D) such that every arc in D is a $V_i V_{i+1}-arc$ (mod k). We give a characterization for an unilateral digraph to be cyclically k-partite through the lengths of directed cycles and directed cycles with one obstruction, in addition we prove that such digraphs always have a k-kernel. A study of some structural properties of cyclically k-partite digraphs is made which bring interesting consequences, e.g., sufficient conditions for a digraph to have k-kernel; a generalization of the well known and important theorem that states if every cycle of a graph G has even length, then G is bipartite (cyclically 2-partite), we prove that if every cycle of a graph G has length ≡ 0 (mod k) then G is cyclically k-partite; and a generalization of another well known result about bipartite digraphs, a strong digraph D is bipartite if and only if every directed cycle has even length, we prove that an unilateral digraph D is bipartite if and only if every directed cycle with at most one obstruction has even length.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2011, 31, 1; 63-78
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-10 z 10

      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