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-6 z 6
    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ł:
    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ł:
    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ł:
    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ł:
    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ł:
    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ł
      Wyświetlanie 1-6 z 6

      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