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

Dostawca treści

Wyrównaj
Wyświetlanie 1-15 z 76
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ł:
A note on kernels and solutions in digraphs
Autorzy:
Harminc, Matúš
Soták, Roman
Powiązania:
https://bibliotekanauki.pl/articles/744158.pdf
Data publikacji:
1999
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
kernel of digraph
solution of digraph
Opis:
For given nonnegative integers k,s an upper bound on the minimum number of vertices of a strongly connected digraph with exactly k kernels and s solutions is presented.
Źródło:
Discussiones Mathematicae Graph Theory; 1999, 19, 2; 237-240
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Kernels by Monochromatic Paths and Color-Perfect Digraphs
Autorzy:
Galeana-Śanchez, Hortensia
Sánchez-López, Rocío
Powiązania:
https://bibliotekanauki.pl/articles/31340961.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
kernel
kernel perfect digraph
kernel by monochromatic paths
color-class digraph
quasi color-perfect digraph
color-perfect digraph
Opis:
For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) \ N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different color, then a kernel by monochromatic paths is said to be a kernel. Two associated digraphs to an arc-colored digraph are the closure and the color-class digraph C(D). In this paper we will approach an mp-kernel via the closure of induced subdigraphs of D which have the property of having few colors in their arcs with respect to D. We will introduce the concept of color-perfect digraph and we are going to prove that if D is an arc-colored digraph such that D is a quasi color-perfect digraph and C(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 309-321
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
k-Kernels and some operations in digraphs
Autorzy:
Galeana-Sanchez, Hortensia
Pastrana, Laura
Powiązania:
https://bibliotekanauki.pl/articles/743109.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
k-kernel
k-subdivision digraph
k-middle digraph and k-total digraph
Opis:
Let D be a digraph. V(D) denotes the set of vertices of D; a set N ⊆ V(D) is said to be a k-kernel of D if it satisfies the following two conditions: for every pair of different vertices u,v ∈ N it holds that every directed path between them has length at least k and for every vertex x ∈ V(D)-N there is a vertex y ∈ N such that there is an xy-directed path of length at most k-1. In this paper, we consider some operations on digraphs and prove the existence of k-kernels in digraphs formed by these operations from another digraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 1; 39-49
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect
Autorzy:
Galeana-Sánchez, Hortensia
García-Ruvalcaba, José
Powiązania:
https://bibliotekanauki.pl/articles/743429.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
kernel
kernel-perfect digraph
m-coloured digraph
Opis:
A digraph D is called a kernel-perfect digraph or KP-digraph when every induced subdigraph of D has a kernel.
We call the digraph D an m-coloured digraph if the arcs of D are coloured with m distinct colours. A path P is monochromatic in D if all of its arcs are coloured alike in D. The closure of D, denoted by ζ(D), is the m-coloured digraph defined as follows:
V( ζ(D)) = V(D), and
A( ζ(D)) = ∪_{i} {(u,v) with colour i: there exists a monochromatic path of colour i from the vertex u to the vertex v contained in D}.
We will denoted by T₃ and C₃, the transitive tournament of order 3 and the 3-directed-cycle respectively; both of whose arcs are coloured with three different colours.
Let G be a simple graph. By an m-orientation-coloration of G we mean an m-coloured digraph which is an asymmetric orientation of G.
By the class E we mean the set of all the simple graphs G that for any m-orientation-coloration D without C₃ or T₃, we have that ζ(D) is a KP-digraph.
In this paper we prove that if G is a hamiltonian graph of class E, then its complement has at most one nontrivial component, and this component is K₃ or a star.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 1; 77-93
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ł:
Kernels in monochromatic path digraphs
Autorzy:
Galeana-Sánchez, Hortensia
Ramírez, Laura
Mejía, Hugo
Powiązania:
https://bibliotekanauki.pl/articles/744174.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
kernel
line digraph
kernel by monochromatic paths
monochromatic path digraph
edge-coloured digraph
Opis:
We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. Let D be an m-coloured digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions:
(i) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them and
(ii) for each vertex x ∈ (V(D)-N) there is a vertex y ∈ N such that there is an xy-monochromatic directed path.
In this paper is defined the monochromatic path digraph of D, MP(D), and the inner m-colouration of MP(D). Also it is proved that if D is an m-coloured digraph without monochromatic directed cycles, then the number of kernels by monochromatic paths in D is equal to the number of kernels by monochromatic paths in the inner m-colouration of MP(D). A previous result is generalized.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 3; 407-417
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs
Autorzy:
Galeana-Sánchez, Hortensia
Rojas-Monroy, R.
Zavala, B.
Powiązania:
https://bibliotekanauki.pl/articles/744398.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
m-coloured digraph
3-quasitransitive digraph
kernel by monochromatic paths
γ-cycle
quasi-monochromatic digraph
Opis:
We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. 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 for every pair of vertices of N there is no monochromatic path between them and for every vertex v ∉ N there is a monochromatic path from v to N. We denote by A⁺(u) the set of arcs of D that have u as the initial vertex. We prove that if D is an m-coloured 3-quasitransitive digraph such that for every vertex u of D, A⁺(u) is monochromatic and D satisfies some colouring conditions over one subdigraph of D of order 3 and two subdigraphs of D of order 4, then D has a kernel by monochromatic paths.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 2; 337-347
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ł:
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ł
Wyświetlanie 1-15 z 76

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