Temat: 3-quasi-transitive digraph - Katalog OPAC zbiorów

Skocz do pozycji: 1.

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 x₀x₁ x₂x₃ of length 3, x₀ and x₃ are adjacent (resp. x₀ dominates x₃). 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ł

Skocz do pozycji: 2.

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ł

Skocz do pozycji: 3.

Tytuł:: On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
Autorzy:: Hell, Pavol
Hernández-Cruz, César
Powiązania:: https://bibliotekanauki.pl/articles/30147225.pdf
Data publikacji:: 2014-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: kernel
3-kernel
NP-completeness
multipartite tournament
cyclically 3-partite digraphs
k-quasi-transitive digraph
Opis:: Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in quite restricted families of digraphs. In this paper we analyze the computational complexity of the corresponding 3-kernel problem, restricted to three natural families of digraphs. As a consequence of one of our main results we prove that the kernel problem remains NP-complete when restricted to 3-colorable digraphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2014, 34, 1; 167-185
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja