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-15 z 39
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ł:
Radii and centers in iterated line digraphs
Autorzy:
Knor, Martin
Niepel, L'udovít
Powiązania:
https://bibliotekanauki.pl/articles/972028.pdf
Data publikacji:
1996
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
center
digraph
line digraph
radius
Opis:
We show that the out-radius and the radius grow linearly, or "almost" linearly, in iterated line digraphs. Further, iterated line digraphs with a prescribed out-center, or a center, are constructed. It is shown that not every line digraph is admissible as an out-center of line digraph.
Źródło:
Discussiones Mathematicae Graph Theory; 1996, 16, 1; 17-26
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
(K − 1)-Kernels In Strong K-Transitive Digraphs
Autorzy:
Wang, Ruixia
Powiązania:
https://bibliotekanauki.pl/articles/31339493.pdf
Data publikacji:
2015-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraph
transitive digraph
k-transitive digraph
k-kernel
Opis:
Let D = (V (D),A(D)) be a digraph and k ≥ 2 be an integer. A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v) ≥ k; it is l-absorbent if for every u ∈ V (D) − N, there exists v ∈ N such that d(u, v) ≤ l. A (k, l)-kernel of D is a k-independent and l-absorbent subset of V (D). A k-kernel is a (k, k − 1)-kernel. A digraph D is k-transitive if for any path x0x1・・・ xk of length k, x0 dominates xk. Hernández-Cruz [3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219] proved that a 3-transitive digraph has a 2-kernel if and only if it has no terminal strong component isomorphic to a 3-cycle. In this paper, we generalize the result to strong k-transitive digraphs and prove that a strong k-transitive digraph with k ≥ 4 has a (k − 1)-kernel if and only if it is not isomorphic to a k-cycle.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 2; 229-235
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ł:
On the Optimality of 3-Restricted Arc Connectivity for Digraphs and Bipartite Digraphs
Autorzy:
Zhang, Yaoyao
Meng, Jixiang
Powiązania:
https://bibliotekanauki.pl/articles/32361733.pdf
Data publikacji:
2022-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
restricted arc-connectivity
bipartite digraph
optimality
digraph
network
Opis:
Let D be a strong digraph. An arc subset S is a k-restricted arc cut of D if D − S has a strong component D′ with order at least k such that D\V (D′) contains a connected subdigraph with order at least k. If such a k-restricted arc cut exists in D, then D is called λk-connected. For a λk-connected digraph D, the k-restricted arc connectivity, denoted by λk(D), is the minimum cardinality over all k-restricted arc cuts of D. It is known that for many digraphs λk(D) ≤ ξk(D), where ξk(D) denotes the minimum k-degree of D. D is called λk-optimal if λk(D) = ξk(D). In this paper, we will give some sufficient conditions for digraphs and bipartite digraphs to be λ3-optimal.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 321-332
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On arc-coloring of digraphs
Autorzy:
Zwonek, M.
Powiązania:
https://bibliotekanauki.pl/articles/254973.pdf
Data publikacji:
2006
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
arc-coloring
digraph
Opis:
In the paper we deal with the problem of the arc-colouring of some classes of digraphs (tournaments, complete digraphs and products of digraphs).
Źródło:
Opuscula Mathematica; 2006, 26, 1; 185-195
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Toward Wojdas conjecture on digraph packing
Autorzy:
Konarski, J.
Żak, A.
Powiązania:
https://bibliotekanauki.pl/articles/255123.pdf
Data publikacji:
2017
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
packing
digraph
size
Opis:
Given a positive integer m ≤ n/2, Wojda conjectured in 1985 that if D1 and D2 are digraphs of order n such that [formula] and [formula] then D1 and D2 pack. The cases when m = 1 or m = n/2 follow from known results. Here we prove the conjecture for [formula].
Źródło:
Opuscula Mathematica; 2017, 37, 4; 589-595
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A sufficient condition for the existence of k-kernels in digraphs
Autorzy:
Galeana-Sánchez, H.
Rincón-Mejía, H.
Powiązania:
https://bibliotekanauki.pl/articles/744223.pdf
Data publikacji:
1998
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraph
kernel
k-kernel
Opis:
In this paper, we prove the following sufficient condition for the existence of k-kernels in digraphs: Let D be a digraph whose asymmetrical part is strongly conneted and such that every directed triangle has at least two symmetrical arcs. If every directed cycle γ of D with l(γ) ≢ 0 (mod k), k ≥ 2 satisfies at least one of the following properties: (a) γ has two symmetrical arcs, (b) γ has four short chords. Then D has a k-kernel.
This result generalizes some previous results on the existence of kernels and k-kernels in digraphs. In particular, it generalizes the following Theorem of M. Kwaśnik [5]: Let D be a strongly connected digraph, if every directed cycle of D has length ≡ 0 (mod k), k ≥ 2. Then D has a k-kernel.
Źródło:
Discussiones Mathematicae Graph Theory; 1998, 18, 2; 197-204
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code
Autorzy:
Balbuena, Camino
Dalfó, Cristina
Martínez-Barona, Berenice
Powiązania:
https://bibliotekanauki.pl/articles/32222715.pdf
Data publikacji:
2021-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
digraph
identifying code
Opis:
A (1, ≤ ℓ)-identifying code in a digraph D is a subset C of vertices of D such that all distinct subsets of vertices of cardinality at most ℓ have distinct closed in-neighbourhoods within C. In this paper, we give some sufficient conditions for a digraph of minimum in-degree δ− ≥ 1 to admit a (1, ≤ ℓ)-identifying code for ℓ ∈ {δ−, δ− + 1}. As a corollary, we obtain the result by Laihonen that states that a graph of minimum degree δ ≥ 2 and girth at least 7 admits a (1, ≤ δ)-identifying code. Moreover, we prove that every 1-in-regular digraph has a (1, ≤ 2)-identifying code if and only if the girth of the digraph is at least 5. We also characterize all the 2-in-regular digraphs admitting a (1, ≤ ℓ)-identifying code for ℓ ∈ {2, 3}.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 853-872
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Hypercompetition Numbers of Hypergraphs with Maximum Degree at Most Two
Autorzy:
Sano, Yoshio
Powiązania:
https://bibliotekanauki.pl/articles/31339316.pdf
Data publikacji:
2015-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraph
competition hypergraph
hypercompetition number
Opis:
In this note, we give an easy and short proof for the theorem by Park and Kim stating that the hypercompetition numbers of hypergraphs with maximum degree at most two is at most two.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 595-598
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Laplacian spectrum of some digraphs obtained from the wheel
Autorzy:
Su, Li
Li, Hong-Hai
Zheng, Liu-Rong
Powiązania:
https://bibliotekanauki.pl/articles/743220.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraph
Laplacian matrix
eigenvalue
wheel
Opis:
The problem of distinguishing, in terms of graph topology, digraphs with real and partially non-real Laplacian spectra is important for applications. Motivated by the question posed in [R. Agaev, P. Chebotarev, Which digraphs with rings structure are essentially cyclic?, Adv. in Appl. Math. 45 (2010), 232-251], in this paper we completely list the Laplacian eigenvalues of some digraphs obtained from the wheel digraph by deleting some arcs.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 2; 255-261
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A proof of mengers theorem by contraction
Autorzy:
Göring, Frank
Powiązania:
https://bibliotekanauki.pl/articles/743549.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
connectivity
disjoint paths
digraph
Menger
Opis:
A short proof of the classical theorem of Menger concerning the number of disjoint AB-paths of a finite graph for two subsets A and B of its vertex set is given. The main idea of the proof is to contract an edge of the graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 111-112
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Sharp Upper Bounds on the Signless Laplacian Spectral Radius of Strongly Connected Digraphs
Autorzy:
Xi, Weige
Wang, Ligong
Powiązania:
https://bibliotekanauki.pl/articles/31340590.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraph
signless Laplacian spectral radius
Opis:
Let \( G = (V (G),E(G)) \) be a simple strongly connected digraph and \( q(G) \) be the signless Laplacian spectral radius of \( G \). For any vertex \( v_i \in V (G) \), let \( d+i \) denote the outdegree of \( v_i \), \( m_i^+ \) denote the average 2-outdegree of \( v_i \), and \( N_i^+ \) denote the set of out-neighbors of \( v_i \). In this paper, we prove that: (1) \( q(G) = d_1^+ + d_2^+, (d_1^+ \ne d_2^+ ) \) if and only if \( G \) is a star digraph \( \overleftrightarrow{K}_{1,n-1} \), where \( d_1^+ \), \( d_2^+ \) are the maximum and the second maximum outdegree, respectively (\( \overleftrightarrow{K}_{1,n-1} \) is the digraph on \( n \) vertices obtained from a star graph \( K_{1,n−1} \) by replacing each edge with a pair of oppositely directed arcs). (2) \( q(G) \le \text{max} \bigg\{ \frac{1}{2} \left( d_i^+ + \sqrt{ { d_i^+ }^2 + 8d_i^+ m_i^+ } \right) : v_i \in V(G) \bigg\} \) with equality if and only if \( G \) is a regular digraph. (3) \( q(G) \le \text{max} \bigg\{ \frac{1}{2} \left( d_i^+ + \sqrt{ {d_i^+}^2 + \frac{4}{d_i^+} \sum_{v_j \in N_i^+ } d_j^+ ( d_j^+ + m_j^+ ) } \right) : v_i \in V(G) \bigg\} \). Moreover, the equality holds if and only if \( G \) is a regular digraph or a bipartite semiregular digraph. (4) \( q(G) \le \text{max} \big\{ \frac{1}{2} \left( d_i^+ + 2d_j^+ - 1 + \sqrt{ ( d_i^+ - 2d_j^+ + 1 )^2 + 4d_i^+ } \right) : ( v_j, v_i ) \in E(G) \big\} \). If the equality holds, then \( G \) is a regular digraph or \( G \in \Omega \), where \( \Omega \) is a class of digraphs defined in this paper.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 977-988
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 39

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