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

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-13 z 13
    Tytuł:
    Destroying symmetry by orienting edges: complete graphs and complete bigraphs
    Autorzy:
    Harary, Frank
    Jacobson, Michael
    Powiązania:
    https://bibliotekanauki.pl/articles/743450.pdf
    Data publikacji:
    2001
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    oriented graph
    automorphism group
    Opis:
    Our purpose is to introduce the concept of determining the smallest number of edges of a graph which can be oriented so that the resulting mixed graph has the trivial automorphism group. We find that this number for complete graphs is related to the number of identity oriented trees. For complete bipartite graphs $K_{s,t}$, s ≤ t, this number does not always exist. We determine for s ≤ 4 the values of t for which this number does exist.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2001, 21, 2; 149-158
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Every 8-Traceable Oriented Graph Is Traceable
    Autorzy:
    Aardt, Susan A. van
    Powiązania:
    https://bibliotekanauki.pl/articles/31341593.pdf
    Data publikacji:
    2017-11-27
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    oriented graph
    traceable
    hypotraceable
    k-traceable
    generalized tournament
    Opis:
    A digraph of order n is k-traceable if n ≥ k and each of its induced subdigraphs of order k is traceable. It is known that if 2 ≤ k ≤ 6, every k-traceable oriented graph is traceable but for k = 7 and for each k ≥ 9, there exist k-traceable oriented graphs that are nontraceable. We show that every 8-traceable oriented graph is traceable.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 4; 963-973
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Independent Detour Transversals in 3-Deficient Digraphs
    Autorzy:
    van Aardt, Susan
    Frick, Marietjie
    Singleton, Joy
    Powiązania:
    https://bibliotekanauki.pl/articles/30146646.pdf
    Data publikacji:
    2013-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    longest path
    independent set
    detour transversal
    strong digraph
    oriented graph
    Opis:
    In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet [Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173] showed that the conjecture holds for digraphs with independence number two. A digraph is p-deficient if its order is exactly p more than the order of its longest paths. It follows easily from Havet’s result that for p = 1, 2 every p-deficient digraph has an independent detour transversal. This paper explores the existence of independent detour transversals in 3-deficient digraphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 2; 261-275
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Extremal Irregular Digraphs
    Autorzy:
    Górska, Joanna
    Skupień, Zdzisław
    Dziechcińska-Halamoda, Zyta
    Majcher, Zofia
    Michael, Jerzy
    Powiązania:
    https://bibliotekanauki.pl/articles/31342278.pdf
    Data publikacji:
    2018-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    irregular digraph
    oriented graph
    minimal subdigraph
    maximal subdigraph
    asymptotic size
    Opis:
    A digraph is called irregular if its distinct vertices have distinct degree pairs. An irregular digraph is called minimal (maximal) if the removal of any arc (addition of any new arc) results in a non-irregular digraph. It is easily seen that the minimum sizes among irregular n-vertex whether digraphs or oriented graphs are the same and are asymptotic to $ (\sqrt{2} // 3) n^{3//2} $; maximum sizes, however, are asymptotic to $ n^2 $ and $ n^2 // 2 $, respectively. Let s stand for the sum of initial positive integers,$s = 1, 3, 6, .... $ An oriented graph $ H_s $ and a digraph $ F_s $, both large (in terms of the size), minimal irregular, and on any such s vertices, $ s \ge 21 $, are constructed in [Large minimal irregular digraphs, Opuscula Math. 23 (2003) 21–24], co-authored by Z. D-H. and three more of the present co-authors (Z.M., J.M., Z.S.). In the present paper we nearly complete these constructions. Namely, a large minimal irregular digraph $ F_n $, respectively oriented graph $ H_n $, are constructed for any of remaining orders $n$, $n > 21$, and of size asymptotic to $ n^2 $, respectively to $ n^2 // 2$. Also a digraph $ \Phi_n $ and an oriented graph $ G_n $, both small maximal irregular of any order $ n \ge 6 $, are constructed. The asymptotic value of the size of $ G_n $ is at least $ ( \sqrt{2} // 3) n^{3//2} $ and is just the least if $ n = s \rightarrow \infty $, but otherwise the value is at most four times larger and is just the largest if $ n = s − 1 \rightarrow \infty $. On the other hand, the size of $ \Phi_n $ is of the asymptotic order $ \Theta (n^{3//2} ) $.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 3; 791-800
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Signed domination and signed domatic numbers of digraphs
    Autorzy:
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/743935.pdf
    Data publikacji:
    2011
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    digraph
    oriented graph
    signed dominating function
    signed domination number
    signed domatic number
    Opis:
    Let D be a finite and simple digraph with the vertex set V(D), and let f:V(D) → {-1,1} be a two-valued function. If $∑_{x ∈ N¯[v]}f(x) ≥ 1$ for each v ∈ V(D), where N¯[v] consists of v and all vertices of D from which arcs go into v, then f is a signed dominating function on D. The sum f(V(D)) is called the weight w(f) of f. The minimum of weights w(f), taken over all signed dominating functions f on D, is the signed domination number $γ_S(D)$ of D. A set ${f₁,f₂,...,f_d}$ of signed dominating functions on D with the property that $∑_{i = 1}^d f_i(x) ≤ 1$ for each x ∈ V(D), is called a signed dominating family (of functions) on D. The maximum number of functions in a signed dominating family on D is the signed domatic number of D, denoted by $d_S(D)$. In this work we show that $4-n ≤ γ_S(D) ≤ n$ for each digraph D of order n ≥ 2, and we characterize the digraphs attending the lower bound as well as the upper bound. Furthermore, we prove that $γ_S(D) + d_S(D) ≤ n + 1$ for any digraph D of order n, and we characterize the digraphs D with $γ_S(D) + d_S(D) = n + 1$. Some of our theorems imply well-known results on the signed domination number of graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2011, 31, 3; 415-427
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    An Oriented Version of the 1-2-3 Conjecture
    Autorzy:
    Baudon, Olivier
    Bensmail, Julien
    Sopena, Éric
    Powiązania:
    https://bibliotekanauki.pl/articles/31339138.pdf
    Data publikacji:
    2015-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    oriented graph
    neighbour-sum-distinguishing arc-weighting
    complexity
    1-2-3 Conjecture
    Opis:
    The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph $G$ with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of $G$. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph \(\overrightarrow{G}\) can be assigned weights from {1, 2, 3} so that every two adjacent vertices of \(\overrightarrow{G}\) receive distinct sums of outgoing weights. This result is tight in the sense that some oriented graphs do not admit such an assignment using the weights from {1, 2} only. We finally prove that deciding whether two weights are sufficient for a given oriented graph is an $\mathsf{NP}$-complete problem. These results also hold for product or list versions of this problem.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 1; 141-156
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Generations in Bayesian networks
    Generacje w sieciach bayesowskich
    Autorzy:
    Litvinenko, Alexander
    Litvinenko, Natalya
    Mamyrbayev, Orken
    Shayakhmetova, Assem
    Powiązania:
    https://bibliotekanauki.pl/articles/407896.pdf
    Data publikacji:
    2019
    Wydawca:
    Politechnika Lubelska. Wydawnictwo Politechniki Lubelskiej
    Tematy:
    Bayesian network
    AgenaRisk
    oriented graph
    vertices generation
    sieć bayesowska
    graf zorientowany
    generacja wierzchołków
    Opis:
    This paper focuses on the study of some aspects of the theory of oriented graphs in Bayesian networks. In some papers on the theory of Bayesian networks, the concept of “Generation of vertices” denotes a certain set of vertices with many parents belonging to previous generations. Terminology for this concept, in our opinion, has not yet fully developed. The concept of “Generation” in some cases makes it easier to solve some problems in Bayesian networks and to build simpler algorithms. In this paper we will consider the well-known example “Asia”, described in many articles and books, as well as in the technical documentation for various toolboxes. For the construction of this example, we have used evaluation versions of AgenaRisk.
    Niniejszy artykuł koncentruje się na badaniu pewnych aspektów teorii zorientowanych grafów w sieciach bayesowskich. W niektórych artykułach na temat teorii sieci bayesowskich pojęcie „generacji wierzchołków” oznacza pewien zestaw wierzchołków z wieloma rodzicami należącymi do poprzednich generacji. Terminologia tego pojęcia, naszym zdaniem, nie została jeszcze w pełni rozwinięta. Koncepcja „Generacji” w niektórych przypadkach ułatwia rozwiązywanie niektórych problemów w sieciach bayesowskich i budowanie prostszych algorytmów. W tym artykule rozważymy dobrze znany przykład „Azja”, opisany w wielu artykułach i książkach, a także w dokumentacji technicznej różnych zestawów narzędzi. Do budowy tego przykładu wykorzystaliśmy wersje testowe AgenaRisk.
    Źródło:
    Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska; 2019, 9, 3; 10-13
    2083-0157
    2391-6761
    Pojawia się w:
    Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Hamiltonian-colored powers of strong digraphs
    Autorzy:
    Johns, Garry
    Jones, Ryan
    Kolasinski, Kyle
    Zhang, Ping
    Powiązania:
    https://bibliotekanauki.pl/articles/743288.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    powers of a strong oriented graph
    distance-colored digraphs
    Hamiltonian-colored digraphs
    Hamiltonian coloring exponents
    Opis:
    For a strong oriented graph D of order n and diameter d and an integer k with 1 ≤ k ≤ d, the kth power $D^k$ of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of $D^k$ if the directed distance $^{→}d_D(u,v)$ from u to v in D is at most k. For every strong digraph D of order n ≥ 2 and every integer k ≥ ⌈n/2⌉, the digraph $D^k$ is Hamiltonian and the lower bound ⌈n/2⌉ is sharp. The digraph $D^k$ is distance-colored if each arc (u, v) of $D^k$ is assigned the color i where $i = ^{→}d_D(u,v)$. The digraph $D^k$ is Hamiltonian-colored if $D^k$ contains a properly arc-colored Hamiltonian cycle. The smallest positive integer k for which $D^k$ is Hamiltonian-colored is the Hamiltonian coloring exponent hce(D) of D. For each integer n ≥ 3, the Hamiltonian coloring exponent of the directed cycle $^{→}Cₙ$ of order n is determined whenever this number exists. It is shown for each integer k ≥ 2 that there exists a strong oriented graph Dₖ such that hce(Dₖ) = k with the added property that every properly colored Hamiltonian cycle in the kth power of Dₖ must use all k colors. It is shown for every positive integer p there exists a a connected graph G with two different strong orientations D and D' such that hce(D) - hce(D') ≥ p.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 4; 705-724
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Oriented Chromatic Number of Cartesian Products and Strong Products of Paths
    Autorzy:
    Dybizbański, Janusz
    Nenca, Anna
    Powiązania:
    https://bibliotekanauki.pl/articles/31343580.pdf
    Data publikacji:
    2019-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph
    oriented coloring
    grid
    Opis:
    An oriented coloring of an oriented graph G is a homomorphism from G to H such that H is without selfloops and arcs in opposite directions. We shall say that H is a coloring graph. In this paper, we focus on oriented col- orings of Cartesian products of two paths, called grids, and strong products of two paths, called strong-grids. We show that there exists a coloring graph with nine vertices that can be used to color every orientation of grids with five columns. We also show that there exists a strong-grid with two columns and its orientation which requires 11 colors for oriented coloring. Moreover, we show that every orientation of every strong-grid with three columns can be colored by 19 colors and that every orientation of every strong-grid with four columns can be colored by 43 colors. The above statements were proved with the help of computer programs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2019, 39, 1; 211-223
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs
    Autorzy:
    Sopena, Éric
    Powiązania:
    https://bibliotekanauki.pl/articles/743250.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    product graph
    oriented coloring
    oriented chromatic number
    Opis:
    The oriented chromatic number of an oriented graph $^→G$ is the minimum order of an oriented graph $^→H$ such that $^→G$ admits a homomorphism to $^→H$. The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations.
    In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph $^→U$ such that every orientation $^→G$ of G admits a homomorphism to $^→U$. We give some properties of this parameter, derive some general upper bounds on the ordinary and upper oriented chromatic numbers of lexicographic, strong, Cartesian and direct products of graphs, and consider the particular case of products of paths.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 3; 517-533
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Analogues of cliques for oriented coloring
    Autorzy:
    Klostermeyer, William
    MacGillivray, Gary
    Powiązania:
    https://bibliotekanauki.pl/articles/744524.pdf
    Data publikacji:
    2004
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph coloring
    oriented coloring
    clique
    planar graph
    Opis:
    We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2004, 24, 3; 373-387
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Difference labelling of digraphs
    Autorzy:
    Sonntag, Martin
    Powiązania:
    https://bibliotekanauki.pl/articles/744591.pdf
    Data publikacji:
    2004
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph labelling
    difference digraph
    oriented tree
    Opis:
    A digraph G is a difference digraph iff there exists an S ⊂ N⁺ such that G is isomorphic to the digraph DD(S) = (V,A), where V = S and A = {(i,j):i,j ∈ V ∧ i-j ∈ V}.For some classes of digraphs, e.g. alternating trees, oriented cycles, tournaments etc., it is known, under which conditions these digraphs are difference digraphs (cf. [5]). We generalize the so-called source-join (a construction principle to obtain a new difference digraph from two given ones (cf. [5])) and construct a difference labelling for the source-join of an even number of difference digraphs. As an application we obtain a sufficient condition guaranteeing that certain (non-alternating) trees are difference digraphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2004, 24, 3; 509-527
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    L(2, 1)-Labelings of Some Families of Oriented Planar Graphs
    Autorzy:
    Sen, Sagnik
    Powiązania:
    https://bibliotekanauki.pl/articles/30147217.pdf
    Data publikacji:
    2014-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    homomorphism
    planar graph
    girth
    partial k-tree
    outerplanar graph
    cactus
    2-dipath L(2, 1)-labeling
    oriented L(2, 1)-labeling
    Opis:
    In this paper we determine, or give lower and upper bounds on, the 2-dipath and oriented L(2, 1)-span of the family of planar graphs, planar graphs with girth 5, 11, 16, partial k-trees, outerplanar graphs and cacti.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 1; 31-48
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-13 z 13

      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