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ę "quasi-transitive digraph" wg kryterium: Wszystkie pola

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-9 z 9
    Tytuł:
    Hamiltonian Cycle Problem in Strong k-Quasi-Transitive Digraphs with Large Diameter
    Autorzy:
    Wang, Ruixia
    Powiązania:
    https://bibliotekanauki.pl/articles/32083906.pdf
    Data publikacji:
    2021-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    quasi-transitive digraph
    k -quasi-transitive digraph
    Hamiltonian cycle
    Opis:
    Let k be an integer with k ≥ 2. A digraph is k-quasi-transitive, if for any path x0x1... xk of length k, x0 and xk are adjacent. Let D be a strong k-quasi-transitive digraph with even k ≥ 4 and diameter at least k +2. It has been shown that D has a Hamiltonian path. However, the Hamiltonian cycle problem in D is still open. In this paper, we shall show that D may contain no Hamiltonian cycle with k ≥ 6 and give the sufficient condition for D to be Hamiltonian.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 2; 685-690
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    3-transitive digraphs
    Autorzy:
    Hernández-Cruz, César
    Powiązania:
    https://bibliotekanauki.pl/articles/743218.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    digraph
    kernel
    transitive digraph
    quasi-transitive digraph
    3-transitive digraph
    3-quasi-transitive digraph
    Opis:
    Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. A digraph D is 3-transitive if the existence of the directed path (u,v,w,x) of length 3 in D implies the existence of the arc (u,x) ∈ A(D). In this article strong 3-transitive digraphs are characterized and the structure of non-strong 3-transitive digraphs is described. The results are used, e.g., to characterize 3-transitive digraphs that are transitive and to characterize 3-transitive digraphs with a kernel.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 2; 205-219
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    4-Transitive Digraphs I: The Structure of Strong 4-Transitive Digraphs
    Autorzy:
    Hernández-Cruz, César
    Powiązania:
    https://bibliotekanauki.pl/articles/30146649.pdf
    Data publikacji:
    2013-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    digraph
    transitive digraph
    quasi-transitive digraph
    4-transitive digraph
    k-transitive digraph
    k-quasi-transitive digraph
    Opis:
    Let D be a digraph, V (D) and A(D) will denote the sets of vertices and arcs of D, respectively. A digraph D is transitive if for every three distinct vertices u, v,w ∈ V (D), (u, v), (v,w) ∈ A(D) implies that (u,w) ∈ A(D). This concept can be generalized as follows: A digraph is k-transitive if for every u, v ∈ V (D), the existence of a uv-directed path of length k in D implies that (u, v) ∈ A(D). A very useful structural characterization of transitive digraphs has been known for a long time, and recently, 3-transitive digraphs have been characterized. In this work, some general structural results are proved for k-transitive digraphs with arbitrary k ≥ 2. Some of this results are used to characterize the family of 4-transitive digraphs. Also some of the general results remain valid for k-quasi-transitive digraphs considering an additional hypothesis. A conjecture on a structural property of k-transitive digraphs is proposed.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 2; 247-260
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Some remarks on the structure of strong $k$-transitive digraphs
    Autorzy:
    Hernández-Cruz, César
    Montellano-Ballesteros, Juan José
    Powiązania:
    https://bibliotekanauki.pl/articles/30148710.pdf
    Data publikacji:
    2014-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    digraph
    transitive digraph
    k-transitive digraph
    quasi-transitive digraph
    k-quasi-transitive digraph
    Laborde-Payan-Xuong Conjecture
    Opis:
    A digraph $D$ is $k$-transitive if the existence of a directed path ($v_0, v_1, . . ., v_k$), of length $k$ implies that ($v_0, v_k) ∈ A(D)$. Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an acyclic transitive digraph. Also, strong 3 and 4-transitive digraphs have been characterized. In this work we analyze the structure of strong $k$-transitive digraphs having a cycle of length at least $k$. We show that in most cases, such digraphs are complete digraphs or cycle extensions. Also, the obtained results are used to prove some particular cases of the Laborde-Payan-Xuong Conjecture.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 4; 651-671
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs
    Autorzy:
    Wang, Ruixia
    Wang, Shiying
    Powiązania:
    https://bibliotekanauki.pl/articles/30146536.pdf
    Data publikacji:
    2013-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph orientation
    3-quasi-transitive digraph
    3-transitive digraph
    Opis:
    A digraph is 3-quasi-transitive (resp. 3-transitive), if for any path x0x1 x2x3 of length 3, x0 and x3 are adjacent (resp. x0 dominates x3). César Hernández-Cruz conjectured that if D is a 3-quasi-transitive digraph, then the underlying graph of D, UG(D), admits a 3-transitive orientation. In this paper, we shall prove that the conjecture is true.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 2; 429-435
    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ł:
    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ł:
    On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
    Autorzy:
    Hell, Pavol
    Hernández-Cruz, César
    Powiązania:
    https://bibliotekanauki.pl/articles/30147225.pdf
    Data publikacji:
    2014-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    kernel
    3-kernel
    NP-completeness
    multipartite tournament
    cyclically 3-partite digraphs
    k-quasi-transitive digraph
    Opis:
    Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in quite restricted families of digraphs. In this paper we analyze the computational complexity of the corresponding 3-kernel problem, restricted to three natural families of digraphs. As a consequence of one of our main results we prove that the kernel problem remains NP-complete when restricted to 3-colorable digraphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 1; 167-185
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    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ł
      Wyświetlanie 1-9 z 9

      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