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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 18
Tytuł:
Packing of three copies of a digraph into the transitive tournament
Autorzy:
Pilśniak, Monika
Powiązania:
https://bibliotekanauki.pl/articles/744566.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
packing of digraphs
transitive tournament
Opis:
In this paper, we show that if the number of arcs in an oriented graph G (of order n) without directed cycles is sufficiently small (not greater than [2/3] n-1), then there exist arc disjoint embeddings of three copies of G into the transitive tournament TTₙ. It is the best possible bound.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 443-456
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Products Of Digraphs And Their Competition Graphs
Autorzy:
Sonntag, Martin
Teichert, Hanns-Martin
Powiązania:
https://bibliotekanauki.pl/articles/31341180.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
competition graph
product of digraphs
Opis:
If D = (V, A) is a digraph, its competition graph (with loops) CGl(D) has the vertex set V and {u, v} ⊆ V is an edge of CGl(D) if and only if there is a vertex w ∈ V such that (u, w), (v, w) ∈ A. In CGl(D), loops {v} are allowed only if v is the only predecessor of a certain vertex w ∈ V. For several products D1 ⚬ D2 of digraphs D1 and D2, we investigate the relations between the competition graphs of the factors D1, D2 and the competition graph of their product D1 ⚬ D2.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 43-58
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Extremum degree sets of irregular oriented graphs and pseudodigraphs
Autorzy:
Dziechcińska-Halamoda, Zyta
Majcher, Zofia
Michael, Jerzy
Skupień, Zdzisław
Powiązania:
https://bibliotekanauki.pl/articles/743975.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
irregular digraphs
degree sequences
degree sets
Opis:
A digraph in which any two vertices have distinct degree pairs is called irregular. Sets of degree pairs for all irregular oriented graphs (also loopless digraphs and pseudodigraphs) with minimum and maximum size are determined. Moreover, a method of constructing corresponding irregular realizations of those sets is given.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 2; 317-333
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
About (k, l)-Kernels, Semikernels and Grundy Functions in Partial Line Digraphs
Autorzy:
Balbuena, C.
Galeana-Sánchez, H.
Guevara, M.
Powiązania:
https://bibliotekanauki.pl/articles/31343207.pdf
Data publikacji:
2019-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraphs
in-domination
kernel
Grundy function
Opis:
Let D be a digraph of minimum in-degree at least 1. We prove that for any two natural numbers k, l such that 1 ≤ l ≤ k, the number of (k, l)-kernels of D is less than or equal to the number of (k, l)-kernels of any partial line digraph ℒD. Moreover, if l < k and the girth of D is at least l +1, then these two numbers are equal. We also prove that the number of semikernels of D is equal to the number of semikernels of ℒD. Furthermore, we introduce the concept of (k, l)-Grundy function as a generalization of the concept of Grundy function and we prove that the number of (k, l)-Grundy functions of D is equal to the number of (k, l)-Grundy functions of any partial line digraph ℒD.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 4; 855-856
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
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ł:
Induced acyclic tournaments in random digraphs: Sharp concentration, thresholds and algorithms
Autorzy:
Dutta, Kunal
Subramanian, C.R.
Powiązania:
https://bibliotekanauki.pl/articles/31232000.pdf
Data publikacji:
2014-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
random digraphs
tournaments
concentration
thresholds
algorithms
Opis:
Given a simple directed graph $D = (V,A)$, let the size of the largest induced acyclic tournament be denoted by $mat(D)$. Let $D ∈ \mathcal{D}(n, p)$ (with $p = p(n)$) be a random instance, obtained by randomly orienting each edge of a random graph drawn from $\mathcal{G}(n, 2p)$. We show that $mat(D)$ is asymptotically almost surely (a.a.s.) one of only 2 possible values, namely either $b^\ast$ or $b^\ast + 1$, where $b^\ast = ⌊2(log_rn) + 0.5⌋$ and $r = p^{−1}$. It is also shown that if, asymptotically, $2(log_rn) + 1$ is not within a distance of $w(n)//(ln n)$ (for any sufficiently slow $w(n) → ∞$) from an integer, then $mat(D)$ is $⌊2(log_rn) + 1⌋$ a.a.s. As a consequence, it is shown that $mat(D)$ is 1-point concentrated for all $n$ belonging to a subset of positive integers of density 1 if $p$ is independent of $n$. It is also shown that there are functions $p = p(n)$ for which $mat(D)$ is provably not concentrated in a single value. We also establish thresholds (on $p$) for the existence of induced acyclic tournaments of size i which are sharp for $i = i(n) → ∞$. We also analyze a polynomial time heuristic and show that it produces a solution whose size is at least $log_rn + Θ(\sqrt{log_rn})$. Our results are valid as long as $p ≥ 1//n$. All of these results also carry over (with some slight changes) to a related model which allows 2-cycles.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 3; 467-495
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Niche Hypergraphs of Products of Digraphs
Autorzy:
Sonntag, Martin
Teichert, Hanns-Martin
Powiązania:
https://bibliotekanauki.pl/articles/32083765.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
niche hypergraph
product of digraphs
competition hypergraph
Opis:
If $ D = (V, A) $ is a digraph, its niche hypergraph \( N \mathcal{H} (D) = (V, \mathcal{E} ) \) has the edge set \( \mathcal{E} = \{ e \subseteq V \ | \ |e| \le 2 \land \exists υ \in V : e = N_D^− (υ) \lor e=N_D^+ (υ) \} \). Niche hypergraphs generalize the well-known niche graphs and are closely related to competition hypergraphs as well as common enemy hypergraphs. For several products \( D_1 \circ D_2 \) of digraphs \( D_1 \) and \( D_2 \), we investigate the relations between the niche hypergraphs of the factors \( D_1 \), \( D_2 \) and the niche hypergraph of their product \( D_1 \circ D_2 \).
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 279-295
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Parallel Digraphs-building Computer Algorithm for Finding a Set of Characteristic Polynomial Realisations of Dynamic System
Autorzy:
Hryniów, K.
Markowski, K. A.
Powiązania:
https://bibliotekanauki.pl/articles/384585.pdf
Data publikacji:
2016
Wydawca:
Sieć Badawcza Łukasiewicz - Przemysłowy Instytut Automatyki i Pomiarów
Tematy:
dynamic system
GPGPU
characteristic polynomial
digraphs
algorithm
Opis:
This paper presents in-depth the parallel computer algorithm for the determination of characteristic polynomial realisations of dynamic system. The main differences between the depicted method and other state of- the-art solutions include finding not few realisations, but a whole set, and the fact that the found realisations are always minimal among all possible. As digraphsbuilding methods used in the algorithm are NP-complete or NP-hard problems, the algorithm is paralleled and GPGPU (General-Purpose computing on Graphics Processor Units) computation is proposed as the only feasible solution. The article describes in detail the proposed method, discusses it’s complexity, presents optimisation solutions and still open problems. The working algorithm is illustrated with a numerical example and compared to results of other known methods.
Źródło:
Journal of Automation Mobile Robotics and Intelligent Systems; 2016, 10, 3; 38-51
1897-8649
2080-2145
Pojawia się w:
Journal of Automation Mobile Robotics and Intelligent Systems
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Cancellation of direct products of digraphs
Autorzy:
Hammack, Richard
Toman, Katherine
Powiązania:
https://bibliotekanauki.pl/articles/744073.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph direct product
graph product cancellation
digraphs
Opis:
We investigate expressions of form A×C ≅ B×C involving direct products of digraphs. Lovász gave exact conditions on C for which it necessarily follows that A ≅ B. We are here concerned with a different aspect of cancellation. We describe exact conditions on A for which it necessarily follows that A ≅ B. In the process, we do the following: Given an arbitrary digraph A and a digraph C that admits a homomorphism onto an arc, we classify all digraphs B for which A×C ≅ B×C.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 4; 575-590
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Frucht’s Theorem for the Digraph Factorial
Autorzy:
Hammack, Richard H.
Powiązania:
https://bibliotekanauki.pl/articles/30146632.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Frucht’s theorem
digraphs
graph automorphisms
digraph factorial
Opis:
To every graph (or digraph) A, there is an associated automorphism group Aut(A). Frucht’s theorem asserts the converse association; that for any finite group G there is a graph (or digraph) A for which Aut(A) ≅ G. A new operation on digraphs was introduced recently as an aid in solving certain questions regarding cancellation over the direct product of digraphs. Given a digraph A, its factorial A! is certain digraph whose vertex set is the permutations of V (A). The arc set E(A!) forms a group, and the loops form a subgroup that is isomorphic to Aut(A). (So E(A!) can be regarded as an extension of Aut(A).) This note proves an analogue of Frucht’s theorem in which Aut(A) is replaced by the group E(A!). Given any finite group G, we show that there is a graph A for which E(A!) ≅ G.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 329-336
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Recognizing weighted directed cartesian graph bundles
Autorzy:
Zmazek, Blaz
Zerovnik, Janez
Powiązania:
https://bibliotekanauki.pl/articles/743682.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph bundles
Cartesian graph product
weighted digraphs
half-convexity
Opis:
In this paper we show that methods for recognizing Cartesian graph bundles can be generalized to weighted digraphs. The main result is an algorithm which lists the sets of degenerate arcs for all representations of digraph as a weighted directed Cartesian graph bundle over simple base digraphs not containing transitive tournament on three vertices. Two main notions are used. The first one is the new relation $^→δ*$defined among the arcs of a digraph as a weighted directed analogue of the well-known relation δ*. The second one is the concept of half-convex subgraphs. A subgraph H is half-convex in G if any vertex x ∈ G∖H has at most one predecessor and at most one successor.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 1; 39-56
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
New classes of critical kernel-imperfect digraphs
Autorzy:
Galeana-Sánchez, Hortensia
Neumann-Lara, V.
Powiązania:
https://bibliotekanauki.pl/articles/744203.pdf
Data publikacji:
1998
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraphs
kernel
kernel-perfect
critical kernel-imperfect
block-cutpoint tree
Opis:
A kernel of a digraph D is a subset N ⊆ V(D) which is both independent and absorbing. When every induced subdigraph of D has a kernel, the digraph D is said to be kernel-perfect. We say that D is a critical kernel-imperfect digraph if D does not have a kernel but every proper induced subdigraph of D does have at least one. Although many classes of critical kernel-imperfect-digraphs have been constructed, all of them are digraphs such that the block-cutpoint tree of its asymmetrical part is a path. The aim of the paper is to construct critical kernel-imperfect digraphs of a special structure, a general method is developed which permits to build critical kernel-imperfect-digraphs whose asymmetrical part has a prescribed block-cutpoint tree. Specially, any directed cactus (an asymmetrical digraph all of whose blocks are directed cycles) whose blocks are directed cycles of length at least 5 is the asymmetrical part of some critical kernel-imperfect-digraph.
Źródło:
Discussiones Mathematicae Graph Theory; 1998, 18, 1; 85-89
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Comparative Case Study on the Social Networking of the Second Year Under Graduate Mathematics Students of the M.D.T. Hindu College, Tirunelveli, Tamil Nadu, India Using Graph Theoretic Parameters
Autorzy:
Petchiammal, S.
Murugan, K.
Powiązania:
https://bibliotekanauki.pl/articles/1193041.pdf
Data publikacji:
2016
Wydawca:
Przedsiębiorstwo Wydawnictw Naukowych Darwin / Scientific Publishing House DARWIN
Tematy:
Sociometry
In-degree
out-degree
Domination
Digraphs
In-domination
Out-domination
Opis:
In this experimental case study, the social relationship of boys and girls studying second year under graduate Mathematics boys in The M.D.T Hindu College, Tirunelveli is compared using sociometry.
Źródło:
World Scientific News; 2016, 58; 1-14
2392-2192
Pojawia się w:
World Scientific News
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Dichromatic number, circulant tournaments and Zykov sums of digraphs
Autorzy:
Neumann-Lara, Víctor
Powiązania:
https://bibliotekanauki.pl/articles/743771.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraphs
dichromatic number
vertex-critical
Zykov sums
tournaments
circulant
covering numbers in hypergraphs
Opis:
The dichromatic number dc(D) of a digraph D is the smallest number of colours needed to colour the vertices of D so that no monochromatic directed cycle is created. In this paper the problem of computing the dichromatic number of a Zykov-sum of digraphs over a digraph D is reduced to that of computing a multicovering number of an hypergraph H₁(D) associated to D in a natural way. This result allows us to construct an infinite family of pairwise non isomorphic vertex-critical k-dichromatic circulant tournaments for every k ≥ 3, k ≠ 7.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 2; 197-207
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On signed arc total domination in digraphs
Autorzy:
Asgharsharghi, L.
Khodkar, A.
Sheikholeslami, S. M.
Powiązania:
https://bibliotekanauki.pl/articles/254811.pdf
Data publikacji:
2018
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
signed arc total dominating function signed arc total domination number domination in digraphs
Opis:
Let D = (V, A) be a finite simple digraph and N(uv) = {u'v' ≠ uv | u = u' or v = v'} be the open neighbourhood of uv in D. A function ƒ : A → { — 1, +1} is said to be a signed arc total dominating function (SATDF) of D if [formula] holds for every arc uv ∈ A. The signed arc total domination number [formula] is defined as [formula]. In this paper we initiate the study of the signed arc total domination in digraphs and present some lower bounds for this parameter.
Źródło:
Opuscula Mathematica; 2018, 38, 6; 779-794
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 18

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